C 이진 트리 삽입에서 매개변수를 이중포인터로 받는 이유를 모르겠습니다.

flrpf13의 이미지

//---------- 이진 트리 삽입 ----------//
void setTreenode(Treenode *ThisNode, int data, Treenode *L, Treenode *R)
{
	ThisNode->key = data;
	ThisNode->left = L;
	ThisNode->right = R;
}
 
void insert_treenode(Treenode **root, int key) //이중 포인터가 왜 필요하지?
{
	Treenode
		*p = NULL, //부모 노드, NULL 초기화
		*t = *root,	//현재 노드, 
		*n; //새 노드
 
	while (t != NULL)
	{
		if (key == t->key) return;
		p = t;
		if (key < p->key)
			t = p->left;
		else
			t = p->right;
	}
 
	n = (Treenode *)malloc(sizeof(Treenode));
 
	if (n == NULL) return;
	n->key = key;
	n->left = n->right = NULL;
 
	if (p != NULL)
	{
		if (key < p->key)
			p->left = n;
		else
			p->right = n;
	}	
	else
		*root = n;
}
 
main()
{
	Treenode
		*n0 = (Treenode*)malloc(sizeof(Treenode)),
		*n1 = (Treenode*)malloc(sizeof(Treenode)),
		*n2 = (Treenode*)malloc(sizeof(Treenode)),
		*n3 = (Treenode*)malloc(sizeof(Treenode)),
		*n4 = (Treenode*)malloc(sizeof(Treenode)),
		*n5 = (Treenode*)malloc(sizeof(Treenode)),
		*n6 = (Treenode*)malloc(sizeof(Treenode));
 
	setTreenode(n0, 30, n1, n2);
	setTreenode(n1, 20, n3, n4);
	setTreenode(n2, 10, n5, n6);
	setTreenode(n3, 15, NULL, NULL);
	setTreenode(n4, 25, NULL, NULL);
	setTreenode(n5, 8, NULL, NULL);
	setTreenode(n6, 15, NULL, NULL);
 
	insert_treenode(&n0, 4);
}

다음은 이진 트리를 크기별로 부모노드보다 작은 값은 좌측 자식노드로, 큰것은 우측 자식 노드로 구성하고
이 트리에다가 4를 추가하는 코드입니다.

30
/ |
20 10
/ | / |
15 25 8 15
이런 구조입니다.

그런데 위 insert_treenode매개변수를 Treenode* 가아닌 Treenode**로 받는 이유를 모르겠습니다.
책에서도 루트노드의 포인터를 바꾸기 위함이다 하는데,

저코드를 디버깅해서 insert_treenode함수의 *t 가 가리키는 것을 추적해보았는데
결국 t는 루트 노트(위 모양에서 30)을 가리킵니다.

그런데 저 매개변수를 이중이 아닌 일중 포인터 Treenode*식으로 바꾸고
한 4줄 밑에?

Treenode *t = *root를 Treenode *t = root로,

함수 마지막 else *root = n을 root = n으로,

main함수에서 insert_treenode(&n0, 4)를
insert_treenode(n0, 4)로.

이런식으로 주소의 단계? 깊이? 를 1단계씩 낮춰줘도

전-혀 문제가 없고 알고리즘을 읽고 분석해봐도 문제가 없는데,
대체 왜 이중포인터로 전달해서 처리할까요?

Lipi의 이미지

main() {
  Treenode *root = NULL;
  insert_treenode(&root, 4);
}
익명 사용자의 이미지

간단합니다.

tree의 모든 노드(Treenode)는 다른 Treenode의 child입니다. left이거나, right이거나.

아, 딱 한 가지 경우만 빼고요. root는 어느 Treenode의 child도 아니죠.
보통 Tree 밖의 누군가가 Treenode * 포인터로 root를 가리킵니다.

문제를 아시겠나요? 트리 내부의 어딘가에 Treenode를 추가할 땐, 추가할 위치의 parent만 변경하면 됩니다.
이 때는 Treenode *만 전달해 주어도 충분합니다.

딱 한 가지 예외, root를 추가할 때, 예컨대 텅 빈 Tree에 Treenode를 추가할 때는 parent가 없습니다.
외부에서 들고 있던 Treenode *를 바꾸어서 root를 가리키게 해야 합니다. 그래서 Treenode **를 전달해 주어야 합니다.

이런 "딱 한 가지 경우의 예외"로 코드가 번잡해지는 경우는 각종 자료구조/알고리즘 구현에서 종종 찾을 수 있습니다. 간결하고 일관성 있고 아름다운 코드를 좋아하시는 분들에게 골칫거리죠. 대체로 workaround가 있기는 한데, 그것도 사람에 따라 "아름다움"과는 거리가 좀 있습니다.

예컨대, Tree에 항상 "가짜 root node"가 들어있게 하여, 모든 "의미 있는 노드"는 항상 Parent node를 갖는다는 성질을 부여해 줄 수 있지요. 이러면 parent node가 없는 node를 추가할 일이 절대 없기 때문에 인터페이스가 간단해집니다. 이런 구조가 차라리 더 낫겠다고 생각하신다면, 그렇게 하세요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.