트리 검색과 재귀호출입니다.
글쓴이: lovejin0309 / 작성시간: 금, 2006/02/24 - 3:33오후
하나의 트리가 있습니다. 우리가 일반적으로 배운 그런 형태가 아니라
중구난방으로 만들어져 있는 트리입니다. B+ 트리 형태와 비슷합니다.
이 트리에서 원하는 노드를 찾아서 그 노드를 리턴해 주는 함수를 작성하는데 좀 막히네요.
제가 원하는 건 다음 형태입니다.
노드 *Search_NODE(char *text, 노드 *트리)
text 에는 원하는 문자열을 놓고, 트리에는 원본 트리를 입력합니다.
노드를 찾으면 그 노드의 주소를 return 해 주어야 합니다.
재귀함수에서 막히고 있습니다.
ㅎㅎ.
지금은 전역 변수를 사용해서 노드를 찾으면 전역변수에 그 노드의 주소를 넣고, return 값을 0으로 줘서 return 값이 0이면 무조건 리턴하는 재귀함수로 짝습니다. ㅎㅎ
노드 자체를 리턴시키고 싶은데... 힌트 부탁드립니다.
Forums:
[code:1]search_func (key, tree)
대충 이런 식.. 너무 생각 나는대로 썼더니..-_-
왼쪽 자식 값이 현재 노드보다 작고 오른쪽 자식 값이 현재보다 크다는 식의 보장이 있다면 더욱 간단하게 짤 수 있겠지요.
그리고 개인적인 질문입니다만 질문 내용에 ㅎㅎ는 왜 들어간건지요?
노루가 사냥꾼의 손에서 벗어나는 것 같이, 새가 그물치는 자의 손에서 벗어나는 것 같이 스스로 구원하라 -잠언 6:5
binary 트리라고 할 때 아래와 같이 재귀호출을 사용해서 원하는 노드
binary 트리라고 할 때 아래와 같이 재귀호출을 사용해서 원하는 노드를 찾습니다.
Re: 트리 검색과 재귀호출입니다.
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.
다음은 제가 짠 소스입니다. [code:1]int Serch_DE
다음은 제가 짠 소스입니다.
자식의 자식...
만약에 따로 스택을 사용하고 싶지 않으시다면
재귀를 사용하되 자식 노드를 보는 것이 아니라 손자 노드를 보는 방식으로 하면 내부적으로는 어차피 스택이 사용되겠지만 따로 스택 구현 없이 짜는 방법도 있습니다. NULL 포인터 검사 좀 더 해야겠지만요.
블로그: http://turtleforward.blogspot.com
댓글 달기