이진 검색 트리

이진 검색 트리
이진 검색 트리
유형	트리
발명된	1960
발명자	P.F. 윈들리, A.D. 부스, A.J.T 콜린, T.N. 히바드
빅 O 표기의 시간 복잡도
알고리즘.
알고리즘.
공간
서치
삽입
삭제

그림 1: 크기 9와 깊이 3의 2진수 탐색 트리로, 뿌리는 8이다.잎이 그려지지 않았다.

컴퓨터 과학에서 BST(Binary Search Tree)는 순서 또는 정렬된 이진 트리라고도 불리며, 각 내부 노드의 키가 각 노드의 왼쪽 하위 트리의 모든 키보다 크고 오른쪽 하위 트리의 키보다 작은 루트 이진 트리 데이터 구조입니다.이진 검색 트리의 작업 복잡도는 트리 높이에 정비례합니다.

이진 검색 트리를 사용하면 데이터 항목을 빠르게 검색, 추가 및 제거할 수 있습니다.BST 내의 노드는 각 비교가 나머지 트리의 절반 정도를 건너뛰도록 배치되어 있기 때문에 룩업 퍼포먼스는 바이너리 로그의 퍼포먼스에 비례합니다.BST는 라벨이 부착된 데이터의 효율적인 저장 문제를 위해 1960년대에 고안되었으며 Conway Berners-Lee와 David Wheeler에 기인한다.

바이너리 검색 트리의 성능은 임의의 삽입이 퇴화를 초래할 수 있기 때문에 트리에 노드를 삽입하는 순서에 따라 달라집니다.바이너리 검색 트리의 몇 가지 변형은 최악의 경우 성능을 보증하면서 구축할 수 있습니다.기본 조작에는 검색, 트래버설, 삽입 및 삭제가 포함됩니다.최악의 경우 복잡성이 보장된 BST는 선형 검색 시간이 필요한 정렬되지 않은 배열보다 성능이 우수합니다.

BST의 복잡도 분석에 따르면 삽입, 삭제 및 검색에 평균적으로n개의 $노드$ (\ $displaystyle$ n)에 $n$ $대해$ O $O(\log n)$ n $)(\displaystyle$ O $(\log$ n $))$ 가 $O(\log n)$ 소요됩니다.In the worst case, they degrade to that of a singly linked list: $O(n)$ . To address the boundless increase of the tree height with arbitrary insertions and deletions, self-balancing variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm.AVL 트리는 Georgy Adelson-Velsky와 Evgenii Landis에 의해 1962년에 발명된 최초의 자기 균형 이진 탐색 트리입니다.

이진 검색 트리는 동적 세트, 룩업 테이블 및 priority 큐와 같은 추상 데이터 유형을 구현하기 위해 사용할 수 있으며 트리 정렬과 같은 정렬 알고리즘에 사용할 수 있습니다.

역사

바이너리 검색 트리 알고리즘은 P.F.를 포함한 여러 연구자들에 의해 독립적으로 발견되었다.윈들리, 앤드류 도날드 부스 앤드류 콜린, 토마스 N 히바드^[1]^[2]이 알고리즘은 ^[3]콘웨이 버너스 리와 데이비드 휠러가 1960년 자기테이프에 라벨이 붙은 데이터를 저장하는 데 사용한 것으로 알려져 있다.최초의 인기 있는 바이너리 검색 트리 알고리즘 중 하나는 Hibbard ^[1]알고리즘입니다.

나무 높이와 이진 탐색 트리의 시간 복잡성 증가 무한정으로는 노드는 임의의 순서로 삽입한, 따라서 독자 평균 2분 탐색 나무 O까지의 나무의 키 집합을 제한하려고 도입되었다{O(logn)\displaystyle}(g마다 나는 n).[4]다양한 height-balanced 2분 탐색 나무한테 사기를 치려고 도입되었다.지느러미AVL 트리, 트리프, 레드-블랙 ^[5]트리 등의 트리 높이.

AVL 트리는 정보의 ^[6]^[7]효율적인 구성을 위해 1962년 Georgy Adelson-Velsky와 Evgenii Landis에 의해 발명되었습니다.그것은 최초로 ^[8]발명된 자가 균형 바이너리 검색 트리였다.

개요

바이너리 서치 트리는 노드가 특정 노드보다 큰 키를 가진 노드가 오른쪽 서브트리에 저장되고, 그 이하의 노드가 바이너리 서치 ^[9]^{: 298}^[10]^{: 287}속성을 만족시키는 왼쪽 서브트리에 저장되는 합계 순서로 배치된 루트 바이너리 트리이다.

이진 검색 트리는 정렬 및 검색 알고리즘에서도 효과적입니다.단, BST의 검색 복잡도는 노드의 삽입 및 삭제 순서에 따라 달라집니다.최악의 경우 바이너리 검색 트리에서 연속적으로 조작하면 축퇴가 발생하여 단일 링크 리스트(^[11]^[9]^{: 299-302}또는 "불균형 트리")와 같은 구조를 형성할 수 있기 때문에 최악의 경우 복잡도는 링크 리스트와 동일합니다.

이진 검색 트리는 집합, 멀티셋 및 연관 배열과 같은 추상 데이터 구조를 구축하는 데 사용되는 기본 데이터 구조이기도 합니다.

운용

검색 중

바이너리 검색 트리에서 특정 키를 검색하는 것은 재귀적 또는 반복적으로 프로그래밍할 수 있습니다.

검색은 루트 노드를 검사하는 것으로 시작됩니다.트리가 0 $(\$ 인 경우 검색 중인 키가 트리에 존재하지 않습니다.그렇지 않으면 키가 루트와 동일한 경우 검색이 성공하고 노드가 반환됩니다.키가 루트 키보다 작을 경우 왼쪽 하위 트리를 검사하여 검색이 계속됩니다.마찬가지로 키가 루트 키보다 크면 오른쪽 하위 트리를 검사하여 검색이 계속됩니다.키가 발견되거나 나머지 서브트리가 ${\text{nil}}$ 때까지 이 프로세스를 반복합니다.\ $displaystyle\text{nil}}$ 서브트리에 ${\text{nil}}$ ${\text{nil}}$ 한 후에도 검색된 키가 발견되지 않으면 트리에 ^[10]^{: 290–291}키가 존재하지 않습니다.

재귀 검색

다음 의사 코드는 ^[10]^{: 290}재귀에 의한 BST 검색 절차를 구현합니다.

x = NIL 또는 key = x.key이면 recursive-tree-Search(x, key)를 반환하고, 키 < x.key이면 recursive-tree-Search(x.left, key)를 반환하지 않으면 recursive-tree-Search(x.right, key)를 반환합니다.

재귀 절차는 ${\text{nil}}$ 중인 0 $(\$ 또는 ${\text{nil}}$ $(\$ 가 발생할 때까지 ${\text{key}}$ 계속됩니다.

반복 검색

검색의 재귀 버전을 while loop으로 "언롤"할 수 있습니다.대부분의 기계에서는 반복 버전이 더 ^[10]^{: 291}효율적입니다.

x ≠ NIL 및 key x x.key일 때 반복 트리 검색(x, key)을 실행한 후 키 < x : = x . left이면 x : = x . return x . right end if repeative return x .

검색이 일부 리프 노드까지 진행될 수 있으므로 BST 검색 실행 시간의 복잡도는 O $)\displaystyle$ O $(h)$ 입니다 $O(h)$ . $h$ 서h(\ $displaystyle$ h $)$ 는 $h$ 트리의 높이입니다.단, BST 검색의 최악의 경우는 O $)$ { $displaystyle$ O $(n)}$ 입니다 $O(n)$ . $n$ 서 n ${displaystyle$ n $}$ 은 $n$ BST 내의 노드의 총수입니다.왜냐하면 불균형 BST는 링크 리스트로 전락할 수 있기 때문입니다.단, BST가 높이 밸런스일 경우 높이는 $O(\log n)$ O( $)\displaystyle$ O $(\log$ n $O(\log n)$ ^[10]^{: 290}입니다.

후계자 및 전임자

${\text{x}}$ x $(\$ 에서 특정 작업의 경우 ${\text{x}}$ x $(\displaystyle {x})$ 의 ${\text{x}}$ 후계자 또는 이전 버전을 찾는 것이 중요합니다.BST의 모든 키가 다른 것으로 가정할 때 BST에서 노드 $(\$ 의 ${\text{x}}$ 후속 노드는 x $(\$ 의 ${\text{x}}$ 보다 작은 키를 가진 노드입니다.한편 BST에서 노드 ${\text{x}}$ (\ $displaystyle\text{x})$ 의 ${\text{x}}$ 이전 노드는 x $(\$ 의 ${\text{x}}$ 보다 큰 키를 가진 노드입니다.다음으로 BST에서 ^[12]^[13]^[10]^{: 292–293} ${\text{x}}$ 의 후계자 및 $선행자를$ 찾기 $위한$ 의사코드를 나타냅니다 $.$

x.right가 NIL이면 BST-Successor(x)가 반환되고 y nil NIL 및 x = y.right이면 y:= y:= y.parent 반복 반환 y

x.left가 NIL이면 BST-Predeprocessor(x)가 BST-Maximum(x.left)을 반환하고 y y NIL 및 x = y.left이면 y:= y.parent repeat return y.

BST에서 키가 최대 또는 최소인 노드 검출 등의 조작은 노드의 후계자 및 이전 노드 판별 등 특정 조작에서 중요합니다.다음으로 ^[10]^{: 291–292}동작의 의사코드를 나타냅니다.

BST-Maximum(x)이 x.right nil NIL인 동안 x := x.right 반복 반환 x

BST-Minimum(x)이 x.left then NIL인 동안 x := x.left 반복 반환 x

삽입

삽입 및 삭제 등의 조작에 의해 BST 표현은 동적으로 변경됩니다.BST의 속성이 계속 유지되도록 데이터 구조를 수정해야 합니다.새로운 노드가 BST에 리프 ^[10]^{: 294–295}노드로 삽입됩니다.삽입 ^[10]^{: 294}조작의 반복적인 실장을 다음에 나타냅니다.

1BST-Insert(T, z)2y:)AA는 3x:=T.root 4반면 x≠ AA는니 5y:cmx6z.key<>x.key 7x:\x.left 8 다른 9x:\x.right 10끝 만약 11을 반복하 12z.parent:)y13만약 y)AA는 후 14T.root:)z15 다른 만약 z.key<>y.key 16번 y.left:= z17.   또 다른18 y.right : = z 19 end if

이 절차에서는 x $(\$ 의 부모로서 tracking pointer y $(\$ 를 ${\text{y}}$ 유지합니다.회선 2에서 초기화 후 4-11을 따라 while loop을 실행하면 포인터가 업데이트됩니다.y $(\$ 가 ${\text{y}}$ 0 $(\$ 인 ${\text{y}}$ BST가 비어 ${\text{z}}$ z $(\$ 가 ${\text{z}}$ 바이너리 검색 ${\text{T}}$ (\displaystyle $\$ })의 루트 노드로 삽입됩니다. $T$ 이 $($ $0$ 이 ${\text{nil}}$ 15~19행의 ${\text{y}}$ y $키$ 와 비교하여 ${\text{y}}$ 삽입이 진행되며,^[10]^{: 295} 이에 따라 노드가 삽입은(는 $)$ 삽입됩니다.

삭제

그림 2: 바이너리 검색 트리 특례 삭제 그림

이진 검색 트리 ${\text{T}}$ 에서 노드 $($ 예: $\$ $displaystyle\$ text ${$ ${\text{z}}$ 삭제 $T}}}$ 은 ${\text{T}}$ (는) 다음 세 ^[10]^{: 295}가지 경우를 충족해야 합니다.

z $(\$ 가 ${\text{z}}$ 리프 노드인 ${\text{z}}$ z $(\$ 에 ${\text{z}}$ 대한 부모 노드의 포인터는 0 $(\$ 으로 ${\text{nil}}$ 대체되고 ${\text{z}}$ 으로 z $(\$ 가 ${\text{z}}$ 트리에서 삭제됩니다.
z $(\displaystyle\text{$ z})에 ${\text{z}}$ 단일 ${\text{z}}$ 가 있는 경우 그림 2(a)와 (b)와 같이 BST $내에서$ z(\ $displaystyle$ $\text$ { ${\text{z}}$ $})$ 의 $위치$ 에 $따라$ z $(\$ $displaystyle\$ $text$ ${$ z ${\text{z}}$ ${\text{z}}$ 의 왼쪽 또는 오른쪽 자노드로 자녀가 상승합니다 $.$ 트리에서 }이 ${\text{z}}$ (가) 제거됩니다 $.$
$z(\displaystyle\text{$ z})에 ${\text{z}}$ 왼쪽과 오른쪽 모두 자식이 있는 ${\text{z}}$ , z $(\$ 의 ${\text{z}}$ 는 ${\text{z}}$ 에서 z(\displaystyle\text{ $z})$ 의 ${\text{z}}$ 위치가 됩니다.이는 BST ^[10]^{: 296}내에서 y $(\style\text{$ y})의 ${\text{y}}$ 에 ${\text{y}}$ 따라 달라집니다.
1. y $\$ $\text{$ y $}$ 가 z $\$ text{z $}$ 의 오른쪽 직계 ${\text{z}}$ 일 ${\text{y}}$ y $\$ 가 ${\text{y}}$ ${\text{y}}$ 하여 y $\$ $}$ 가 됩니다. ${\text{y}}$ 의 왼쪽 자녀는 그림 2(c)와 $같이$ z\ $displaystyle\text{$ z ${\text{z}}$ 의 왼쪽 첫 서브트리를 $.$
2. y $(\displaystyle\text{$ y $})$ 가 z ${\text{y}}$ (\ $displaystyle\$ text $z})$ 의 바로 오른쪽 자식이 아닌 ${\text{y}}$ ${\text{y}}$ 삭제는 y(\ $displaystyle$ $\$ $text{$ y})의 ${\text{y}}$ 오른쪽 자식으로 ${\text{y}}$ 되며 y $(\$ {y})는 ${\text{y}}$ 그림과 같이 BST에서 z $(\$ 의 ${\text{z}}$ 위치를 ${\text{z}}$ 합니다.n 그림 2 part (d)

다음으로 바이너리 검색 ^[10]^{: 296-298}트리의 삭제 조작을 위한 의사 코드를 나타냅니다.

1 BST-Delete(T, z) 2 z.left = NIL이면 다른 3개의 Shift-Nodes(T, z, z.right) 4개 z.right = NIL이면 다른 5개의 Shift-Nodes(T, z.left) 6개, 다른 7y= Tree-Successor(z) 8개 z.shift = 부모 Z.Nodes = Nil이면 다른 Z.Nodes.Shift-Nodes(T, z, y) 14 y.left : = z.left 15 y.left.parent : = y 16 end: 다음 경우

1 Shift-Nodes(T, u, v) 2 u.parent = NIL이면 3 T.root : = v 4 else = u.parent.left이면 5 u.parent.left : = v ≠ NIL이면 8 、 9 v : = v 7이 종료됩니다.

$($ 절차에서는 ${\text{Tree-Delete}}$ 위에서 설명한 3가지 특수한 경우를 다룹니다.2-3행은 케이스1을 취급하고, 4-5행은 케이스2를 취급하고, 6-16행은 케이스3을 취급합니다.도우미 ${\text{Shift-Nodes}}$ Shift-Nodes $(Shift-Nodes)$ 는 ${\text{Shift-Nodes}}$ 이진 검색 ${\text{T}}$ T $(\$ \text{v})에서 노드 u $(\$ $displaystyle\text{$ u})를 v(\ $displaystyle\text{v})$ 로 ${\text{u}}$ ${\text{v}}$ 바꾸기 위해 삭제 알고리즘 내에서 사용됩니다. $T$ ^[10]^{: 298} 이 절차에서는 BST에서 사용자의 ${\text{u}}$ (및 치환)를 처리합니다.\ $text{u})$ 의 ${\text{u}}$ ${\text{u}}$ (및 ${\text{u}}$ 치환)를 처리합니다.

트래버설

BST는 순서, 프리오더 및 포스트오더 트리 ^[10]^{: 287}워크의 3가지 기본 알고리즘을 통해 통과할 수 있습니다.

순서 트리 워크:왼쪽 서브트리의 노드가 먼저 접속되고 다음으로 루트노드와 오른쪽 서브트리가 접속됩니다.
트리 워크 예약:루트 노드가 먼저 액세스되고 이어서 왼쪽 및 오른쪽 하위 트리가 표시됩니다.
포스트오더 트리 워크:왼쪽 서브트리의 노드가 먼저 표시되고 오른쪽 서브트리가 그 다음에 마지막으로 루트가 표시됩니다.

다음은 트리 ^[10]^{: 287–289}워크의 재귀 구현입니다.

x가 NIL이면 Inorder-Tree-Walk(x.left)가 노드 Inorder-Tree-Walk(x.right)를 방문합니다.

프리오더 트리 워크(x)가 NIL이면 노드 프리오더 트리 워크(x.left) 프리오더 트리 워크(x.right)가 종료됩니다.

x가 NIL이면 Postorder-Tree-Walk(x), Postorder-Tree-Walk(x.왼쪽) Postorder-Tree-Walk(x.오른쪽)가 노드 종료를 방문한다.

균형 잡힌 이진 검색 트리

균형을 재조정하지 않으면 바이너리 검색 트리에 삽입 또는 삭제하면 트리 $높이$ n $(여기$ 서 $n$ $\displaystyle$ n은트리 $n$ 내의 항목 수)이 저하되어 검색 성능이 선형 ^[14]검색의 값으로 저하될 수 있습니다.검색 트리의 밸런스와 높이를 O $O(\log n)$ n $O(\log n)$ )(\ $displaystyle$ O $(\log$ n $))$ 로 $O(\log n)$ $O(\log n)$ 하는 것은 바이너리 검색 트리의 유용성에 대한 열쇠입니다.이는 트리 높이를 이진 로그 ^[4]^[15]^{: 50}복잡도로 유지하도록 설계된 트리에 대한 업데이트 작업 중에 "셀프 밸런싱" 메커니즘을 통해 달성할 수 있습니다.

높이 균형 트리

왼쪽 서브트리와 오른쪽 서브트리의 높이가 일정한 계수에 의해 관련지어지는 것이 보증되면 트리는 높이 밸런스됩니다.이 속성은 AVL 트리에 의해 도입되어 Red-Black ^[15]^{: 50–51}트리에 의해 계속됩니다.루트에서 수정된 리프 노드까지의 경로 상의 모든 노드의 높이를 관찰하고 ^[15]^{: 52}트리에 대한 삽입 및 삭제 작업을 수행할 때마다 수정해야 합니다.

무게 균형 나무

무게 균형 나무에서 균형 잡힌 나무의 기준은 하위 나무의 잎 수입니다.이후 1{1\displaystyle}의 강력한 균형 조건이 O형인(로그⁡ n){O(n\log)\displaystyle}rebalancing wor가 유지될 수 없을 왼쪽 및 오른쪽 subtrees의 무게에서 가장 1{1\displaystyle}.[16][15]:61 하지만 그 차이점이 무게의 비율α{\displaystyle \alpha}에 의해 바인딩 됩니다에 의해 다르다.k동안 세세한 사항ert 및 삭제 작업을 수행합니다.α $(\displaystyle \alpha)$ - 무게 균형 트리는 $\alpha$ 균형 상태를 제공합니다.여기서 왼쪽과 오른쪽 서브트리는 ^[15]^{: 62}각각 서브트리의 총 무게 중 최소 $\alpha$ α(\ $displaystyle \alpha)$ 의 $\alpha$ $\alpha$ 를 가집니다.

종류들

T 트리,^[17] treap,^[18] red-black 트리,^[19] B 트리,^[20] 2-3 트리,^[21] 스플레이 ^[22]트리 등 여러 가지 자체 균형 바이너리 검색 트리가 있습니다.

응용 프로그램의 예

종류

이진 검색 트리는 트리 정렬과 같은 정렬 알고리즘에 사용됩니다. 이 알고리즘에서는 모든 요소가 한 번에 삽입되고 트리가 순서대로 ^[23]횡단됩니다.BST는 ^[24]퀵소트에서도 사용됩니다.

priority 큐 조작

이진 검색 트리는 노드의 키를 우선순위로 사용하여 priority 큐를 구현하는 데 사용됩니다.큐에 새로운 요소를 추가하는 작업은 통상적인 BST 삽입 조작 후에 이루어지지만 삭제 조작은 priority ^[25]큐의 유형에 따라 달라집니다.

오름차순 priority 큐의 경우 가장 낮은 priority를 가진 요소의 삭제는 BST의 좌측 통과를 통해 이루어집니다.
내림차순 priority 큐의 경우 가장 높은 priority를 가진 요소의 삭제는 BST의 우측 통과를 통해 이루어집니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Culberson, J.; Munro, J. I. (1 January 1989). "Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations". The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.
^ Culberson, J.; Munro, J. I. (28 July 1986). "Analysis of the standard deletion algorithms in exact fit domain binary search trees". Algorithmica. Springer Publishing, University of Waterloo: 297. doi:10.1007/BF01840390.
^ P. F. Windley (1 January 1960). "Trees, Forests and Rearranging". The Computer Journal. 3 (2): 84. doi:10.1093/comjnl/3.2.84.
^ ^a ^b Knuth, Donald (1998). "Section 6.2.3: Balanced Trees". The Art of Computer Programming (PDF). Vol. 3 (2 ed.). Addison-Wesley. pp. 458–481. ISBN 978-0201896855.
^ Paul E. Black, "빨간색-검은색 트리", 알고리즘 및 데이터 구조 사전 [온라인]의 Paul E.블랙, ed. 2019년 11월 12일(2022년 5월 19일)부터 : https://www.nist.gov/dads/HTML/redblack.html
^ Myers, Andrew. "CS 312 Lecture: AVL Trees". Cornell University, Department of Computer Science. Archived from the original on 27 April 2021. Retrieved 19 May 2022.
^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. Myron J. Ricci의 소련 수학 번역 - Doklady, 3:1259–1263, 1962.
^ Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF). University of Toronto, Department of Computer Science. p. 6. Archived (PDF) from the original on 14 February 2019. Retrieved 19 May 2022.
^ ^a ^b Thareja, Reema (13 October 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press. ISBN 0-262-03293-7.
^ R. A. Frost; M. M. Peterson (1 February 1982). "A Short Note on Binary Search Trees". The Computer Journal. Oxford University Press. 25 (1): 158. doi:10.1093/comjnl/25.1.158.
^ Junzhou Huang. "Design and Analysis of Algorithms" (PDF). University of Texas at Arlington. p. 12. Archived (PDF) from the original on 13 April 2021. Retrieved 17 May 2021.
^ Ray Toal. "Binary Search Tree". Loyola Marymount University, Department of Computer Science. Retrieved 17 May 2022.
^ Thornton, Alex (2021). "ICS 46: Binary Search Trees". University of California, Irvine. Archived from the original on 4 July 2021. Retrieved 21 October 2021.
^ ^a ^b ^c ^d ^e Brass, Peter (January 2011). Advanced Data Structure. Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 9780511800191.
^ Blum, Norbert; Mehlhorn, Kurt (1978). "On the Average Number of Rebalancing Operations in Weight-Balanced Trees" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.
^ Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986). A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. ISBN 0-934613-18-4.
^ Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF), Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (second ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.
^ Comer, Douglas (June 1979), "The Ubiquitous B-Tree", Computing Surveys, 11 (2): 123–137, doi:10.1145/356770.356776, ISSN 0360-0300, S2CID 101673
^ Knuth, Donald M (1998). "6.2.4". The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley. ISBN 9780201896855. The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.
^ Sleator, Daniel D.; Tarjan, Robert E. (1985). "Self-Adjusting Binary Search Trees" (PDF). Journal of the ACM. 32 (3): 652–686. doi:10.1145/3828.3835. S2CID 1165848.
^ Narayanan, Arvind (2019). "COS226: Binary search trees". Princeton University School of Engineering and Applied Science. Archived from the original on 22 March 2021. Retrieved 21 October 2021 – via cs.princeton.edu.
^ Xiong, Li. "A Connection Between Binary Search Trees and Quicksort". Oxford College of Emory University, The Department of Mathematics and Computer Science. Archived from the original on 26 February 2021. Retrieved 4 June 2022.
^ Myers, Andrew. "CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps". Cornell University, Department of Computer Science. Archived from the original on 21 October 2021. Retrieved 21 October 2021.

추가 정보

이 문서에는 NIST 문서의 퍼블릭 도메인 자료가 포함되어 있습니다.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "12: Binary search trees, 15.5: Optimal binary search trees". Introduction to Algorithms (2nd ed.). MIT Press. pp. 253–272, 356–363. ISBN 0-262-03293-7.
Jarc, Duane J. (3 December 2005). "Binary Tree Traversals". Interactive Data Structure Visualizations. University of Maryland. Archived from the original on 27 February 2014. Retrieved 30 April 2006.
Knuth, Donald (1997). "6.2.2: Binary Tree Searching". The Art of Computer Programming. Vol. 3: "Sorting and Searching" (3rd ed.). Addison-Wesley. pp. 426–458. ISBN 0-201-89685-0.
Long, Sean. "Binary Search Tree" (PPT). Data Structures and Algorithms Visualization-A PowerPoint Slides Based Approach. SUNY Oneonta.
Parlante, Nick (2001). "Binary Trees". CS Education Library. Stanford University. Archived from the original on 2022-01-30.

외부 링크

Ben Paff: 바이너리 검색 트리 및 균형 트리 소개(PDF; 1675kB) 2004.
Binary Tree Visualizer(다양한 BT 기반 데이터 구조의 JavaScript 애니메이션)

[computer_journal89-1] Culberson, J.; Munro, J. I. (1 January 1989). "Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations". The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.

[2] Culberson, J.; Munro, J. I. (28 July 1986). "Analysis of the standard deletion algorithms in exact fit domain binary search trees". Algorithmica. Springer Publishing, University of Waterloo: 297. doi:10.1007/BF01840390.

[windley60-3] P. F. Windley (1 January 1960). "Trees, Forests and Rearranging". The Computer Journal. 3 (2): 84. doi:10.1093/comjnl/3.2.84.

[Knuth98-4] Knuth, Donald (1998). "Section 6.2.3: Balanced Trees". The Art of Computer Programming (PDF). Vol. 3 (2 ed.). Addison-Wesley. pp. 458–481. ISBN 978-0201896855.

[5] Paul E. Black, "빨간색-검은색 트리", 알고리즘 및 데이터 구조 사전 [온라인]의 Paul E.블랙, ed. 2019년 11월 12일(2022년 5월 19일)부터 : https://www.nist.gov/dads/HTML/redblack.html

[6] Myers, Andrew. "CS 312 Lecture: AVL Trees". Cornell University, Department of Computer Science. Archived from the original on 27 April 2021. Retrieved 19 May 2022.

[7] Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. Myron J. Ricci의 소련 수학 번역 - Doklady, 3:1259–1263, 1962.

[8] Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF). University of Toronto, Department of Computer Science. p. 6. Archived (PDF) from the original on 14 February 2019. Retrieved 19 May 2022.

[reema18-9] Thareja, Reema (13 October 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.

[algo_cormen-10] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press. ISBN 0-262-03293-7.

[11] R. A. Frost; M. M. Peterson (1 February 1982). "A Short Note on Binary Search Trees". The Computer Journal. Oxford University Press. 25 (1): 158. doi:10.1093/comjnl/25.1.158.

[12] Junzhou Huang. "Design and Analysis of Algorithms" (PDF). University of Texas at Arlington. p. 12. Archived (PDF) from the original on 13 April 2021. Retrieved 17 May 2021.

[13] Ray Toal. "Binary Search Tree". Loyola Marymount University, Department of Computer Science. Retrieved 17 May 2022.

[14] Thornton, Alex (2021). "ICS 46: Binary Search Trees". University of California, Irvine. Archived from the original on 4 July 2021. Retrieved 21 October 2021.

[peter11-15] Brass, Peter (January 2011). Advanced Data Structure. Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 9780511800191.

[16] Blum, Norbert; Mehlhorn, Kurt (1978). "On the Average Number of Rebalancing Operations in Weight-Balanced Trees" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.

[17] Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986). A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. ISBN 0-934613-18-4.

[18] Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees" (PDF), Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1

[Cormen2001-19] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (second ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.

[20] Comer, Douglas (June 1979), "The Ubiquitous B-Tree", Computing Surveys, 11 (2): 123–137, doi:10.1145/356770.356776, ISSN 0360-0300, S2CID 101673

[21] Knuth, Donald M (1998). "6.2.4". The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley. ISBN 9780201896855. The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.

[22] Sleator, Daniel D.; Tarjan, Robert E. (1985). "Self-Adjusting Binary Search Trees" (PDF). Journal of the ACM. 32 (3): 652–686. doi:10.1145/3828.3835. S2CID 1165848.

[23] Narayanan, Arvind (2019). "COS226: Binary search trees". Princeton University School of Engineering and Applied Science. Archived from the original on 22 March 2021. Retrieved 21 October 2021 – via cs.princeton.edu.

[24] Xiong, Li. "A Connection Between Binary Search Trees and Quicksort". Oxford College of Emory University, The Department of Mathematics and Computer Science. Archived from the original on 26 February 2021. Retrieved 4 June 2022.

[25] Myers, Andrew. "CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps". Cornell University, Department of Computer Science. Archived from the original on 21 October 2021. Retrieved 21 October 2021.

[1]

[2]

[3]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[4]

[15]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

v t 트리 데이터 구조
트리 검색 (다이나믹 세트/어소시에이션 어레이)	2–3 2–3–4 AA (a, b) AVL B B+ B* B^x. (최적) 바이너리 검색 춤추다 HTree 간격 주문통계 (좌향) 레드-블랙 희생양 스플라이 T 나무 UB 무게 밸런스
수북이	바이너리 이항 브로달 피보나치 좌파 페어링 스큐 판 엠데 보아스 약한
시도하다	Ctrie C-trie(압축 ADT) 해시 기수 서픽스 삼진수 검색 X-Fast 고속
공간 데이터 파티션 트리	공 BK BSP 데카르트어 힐베르트 R k-d(표준 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 부분 부사장 X
기타 트리	덮다 지수 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시 캘린더 i디스턴스 K-ary 좌측자녀 우측자매 링크/컷 로그 구조화 결합 머클 p q. 범위 SPQR 정상

v t 잘 알려진 데이터 구조
종류들	수집 컨테이너.
추상적인	연관 배열 멀티맵 데이터 구조 검색 목록. 스택 큐 더블 엔드 큐 priority 큐 이중 엔드 priority 큐 세트 멀티셋 디조인트 세트
어레이	비트 배열 순환 버퍼 다이내믹 어레이 해시 테이블 해시 어레이 트리 희박 행렬
링크되어 있다	어소시에이션리스트 링크 리스트 스킵 리스트 언롤링된 링크 리스트 XOR 링크 리스트
나무들	B-트리 이진 검색 트리 AA나무 AVL 트리 붉은색-검은색 셀프밸런싱 트리 스플레이 트리 히프 이진 힙 이항 힙 피보나치 힙 R 트리 R* 트리 R+ 트리 힐베르트 R-트리 트리 해시 트리
그래프	이항 결정도 방향 비순환 그래프 지시 비순환 단어 그래프
데이터 구조 목록

Search

이진 검색 트리

네임스페이스

더

목차

역사

개요

운용

검색 중

재귀 검색

반복 검색

후계자 및 전임자

삽입

삭제

트래버설

균형 잡힌 이진 검색 트리

높이 균형 트리

무게 균형 나무

종류들

응용 프로그램의 예

종류

priority 큐 조작

「」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

Search

이진 검색 트리

역사

개요

운용

검색 중

재귀 검색

반복 검색

후계자 및 전임자

삽입

삭제

트래버설

균형 잡힌 이진 검색 트리

높이 균형 트리

무게 균형 나무

종류들

응용 프로그램의 예

종류

priority 큐 조작

「 」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

「」를 참조해 주세요.