트리 검색과 재귀호출입니다.

lovejin0309의 이미지

하나의 트리가 있습니다. 우리가 일반적으로 배운 그런 형태가 아니라
중구난방으로 만들어져 있는 트리입니다. B+ 트리 형태와 비슷합니다.

이 트리에서 원하는 노드를 찾아서 그 노드를 리턴해 주는 함수를 작성하는데 좀 막히네요.

제가 원하는 건 다음 형태입니다.

노드 *Search_NODE(char *text, 노드 *트리)

text 에는 원하는 문자열을 놓고, 트리에는 원본 트리를 입력합니다.

노드를 찾으면 그 노드의 주소를 return 해 주어야 합니다.

재귀함수에서 막히고 있습니다.

ㅎㅎ.

지금은 전역 변수를 사용해서 노드를 찾으면 전역변수에 그 노드의 주소를 넣고, return 값을 0으로 줘서 return 값이 0이면 무조건 리턴하는 재귀함수로 짝습니다. ㅎㅎ

노드 자체를 리턴시키고 싶은데... 힌트 부탁드립니다.

eminency의 이미지

search_func (key, tree)
{
    if (key == current_val)
        return current_node;
    ret = search_func(key, lchild);

    if (ret != -1) return ret;

    return search_func(key, rchild);
}

대충 이런 식.. 너무 생각 나는대로 썼더니..-_-
왼쪽 자식 값이 현재 노드보다 작고 오른쪽 자식 값이 현재보다 크다는 식의 보장이 있다면 더욱 간단하게 짤 수 있겠지요.

그리고 개인적인 질문입니다만 질문 내용에 ㅎㅎ는 왜 들어간건지요?

노루가 사냥꾼의 손에서 벗어나는 것 같이, 새가 그물치는 자의 손에서 벗어나는 것 같이 스스로 구원하라 -잠언 6:5

kimsk99의 이미지

binary 트리라고 할 때 아래와 같이 재귀호출을 사용해서 원하는 노드를 찾습니다.

struct node{
  string value;
  node * left;
  node * right;
};

////

node * find(string v, node * n){
  if( n == NULL ){
    return NULL;
  }
  if( n->value == v ){
     return n;
  }
  node * left = find(v, n->left);
  if( left != null ){
    return left;
  }else{
    return find(v, n->right);
  }
}
오호라의 이미지

lovejin0309 wrote:
하나의 트리가 있습니다. 우리가 일반적으로 배운 그런 형태가 아니라
중구난방으로 만들어져 있는 트리입니다. B+ 트리 형태와 비슷합니다.

이 트리에서 원하는 노드를 찾아서 그 노드를 리턴해 주는 함수를 작성하는데 좀 막히네요.

M-way 트리 ( 한개의 노드가 M개의 데이터로 이루어짐 )라면 윗분들의 의사코드에 노드에 M개를 검색하는 부분이 추가되어야 합니다.

M개를 검색하는 가장 단순한 방법은 순차검색( for~ ), 이진검색을 추가하셔야 합니다.

결정적으로 B+tree 구조와 흡사하다면 B+tree와 흡사한 어려움이 있을 법합니다.

우선, 재귀호출은 Depth가 깊어지면 오버플로우의 문제점이 있습니다. 복잡도도 매우 높아집니다. ( 단, M이 작을 경우 )

B+tree 특성상 스택이 꼭 필요합니다.
재귀호출 사용해서 암묵적으로 프로세스의 스택을 사용하던가. 직접 또는 라이브러리 스택을 사용하셔야 합니다.

한마디로 미로찾기처럼 스택을 이용해서 지나왔던 노드를 스택에 쌓아야 리프노드( 자식없는 노드 )까지 들어갔다. 올라오면서 노드를 정리( Delete, Merge )해줘야 합니다.

또한, B+tree같은 경우 삭제시에는 최적화를 위해서 추가적인 부분이 필요합니다. D. Knuth의 원조 B+tree에는 없습니다.(정확하지 않음. ^^; )

윗분의 Tail Recursive ( 꼬리호출 )을 그대로 쓰시기에는 문제가 좀 있을듯합니다.

Hello World.

익명 사용자의 이미지

다음은 제가 짠 소스입니다.

int Serch_DEVICE(char *text, Struct NODE *NODE)
{
   int INDEX = 0;
   int error   = 0;

   if(strcmp(NODE->Name, text) != 0){ //  찾는 노드가 아니라면 계속 검색
        if(NODE->Count_of_child !=0{  // Leaf 노드가 아니라면
            for(INDEX = 0; INDEX <NODE->Count_of_child ; INDEX++){
                error = Search_DEVICE(text, NODE->child[INDEX]);
                if (error ==1) return error;
            }
            return 0;
        }else{ // Leaf 노드 라면
             return 0;
    }
   }else{ //  찾는 노드라면 계속 리턴
        printf("%s 노드를 찾았습니다. \n", text);
        STACK[Stack_TOP] = NODE;
        return 1;
    }

    return 0;
}
only2sea의 이미지

만약에 따로 스택을 사용하고 싶지 않으시다면
재귀를 사용하되 자식 노드를 보는 것이 아니라 손자 노드를 보는 방식으로 하면 내부적으로는 어차피 스택이 사용되겠지만 따로 스택 구현 없이 짜는 방법도 있습니다. NULL 포인터 검사 좀 더 해야겠지만요.

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.