|
|
||||||||
| 경고! 게시물 작성자의 사전 허락없는 메일주소 추출행위 절대 금지 |
|
RBTree라고 해서 BTree와 크게 다를 건 없죠. 다만 RBTree의 경우 노드 체인이 밸런스를 유지하는 구조이기 때문에, 트리의 모든 경로가 다른 경로의 두배 이상 길어지지 않아서 트리탐색 시간을 O(log n)으로 보장 받을 수 있다는 정도만 다를 뿐이죠. 리누스 커널의 경우를 예로 들면... 스케쥴러에서 RBTree를 사용하는데. 프로세스 요구가 높은 항목들을 RBTree의 왼쪽에 두고서, 맨 왼쪽 노드를 다음에 실행할 노드로 선택하면 프로세스들 간에 전체적인 실행 밸런스가 자연스럽게 유지되는 효과를 얻을 수 있기 때문에 RBTree를 이용하기도 하고요. 노드 체인이 밸런스를 유지하는 구조라는 게 다를 뿐, BTree와 크게 다를 게 없습니다. RBTree도 일반적인 자료구조 중에 하나일 뿐입니다.
음... 용어의 정리가 필요할 거 같은데요,
일반적으로 전산학에서 BTree라고 하면 Binary Tree를 뜻하지는 않습니다. Binary Tree는 Retrieve를 할 때 이분법적으로 나아 가지만 BTree에서는 n분법(사용자가 정하는 대로)으로 분기하며 검색을 하는 큰 차이점이 있습니다. 또한 BTree는 뭉태기(block) 단위의 검색에 효율적으로 사용되어 질 수 있는 기법이기 때문에 DB 검색(Primay or Secondary Key)에 주로 사용되어 지는 기법이죠. BTree는 이를 응용한 B+Tree, B*Tree 등이 있는데 대부분 Database 와 관련된 곳에서 사용이 되는 기법입니다. 반면에 RBTree(red block tree)는 bancing binary tree를 유지하기 위한 방법 중의 하나이구요. http://en.wikipedia.org/wiki/B-tree 에서 자세히 나와 있으니 참고하시면 좋을 것 같습니다. ^^ RBTree와 B-Tree에 관한 얘기군요.
RBTree는 B-Tree의 특수한 케이스라고 할 수 있습니다. 즉, B-Tree중에서 order가 4인 Tree, 보통 2-3-4 Tree라고 합니다. 이 2-3-4 Tree가 RBTree와 동일한 Tree입니다. 이것을 잘 보여주는 예제가 다음 링크에 있습니다. http://people.ksp.sk/~kuko/bak/ RB-Tree의 탭에서 2-3-4모드를 체크해 보시면 어떻게 동일한 지를 보여줍니다. 아무래도 눈으로 보는 것이 가장 이해하기가 쉽겠지요. 참고하시기 바랍니다. 관련 글 리스트
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Copyright © 1999-2015, borlandforum.com. All right reserved. |
디스크샷,VirtualFDD,ezBackTO... 모두 한국사람이 만든 매니악한 시스템 프로그램들이죠...
이 프로그램들의 핵심코어에는 BTree가 있습니다. 당연히 RBTree와 같은 BTree를 원류로 하는 것들도 한자리 하고 있겠죠?
저도 요즘 땀흘리며 공부중인데... 20년전 드난시 했던 BTree가 이렇게 절실하게 필요할 줄이야... ㅠ.ㅠ