노드
루트
이진 검색 트리
다진 검색 트리
K진 검색 트리
라고도 하며 K개로 분기가 가능하다.내장 검색 트리
외장 검색 트리
서브 트리
__root
🠔 이진 검색 트리의 루트 노드
search(x)
🠔 이진 검색 트리에서 원소 x를 검색한다.insert(x)
🠔 이진 검색 트리에 원소 x를 삽입한다.delete(x)
🠔 이진 검색 트리에서 원소 x를 삭제한다.isEmpty()
🠔 이진 검색 트리에 키가 하나도 없이 비어 있는가?clear()
🠔 이진 검색 트리를 깨끗이 비운다.
search(t, x): 🠔 t: (서브) 트리의 루트 노드 레퍼런스, x: 검색하고자 하는 키 if (t = null || t.item = x) return t else if (x < t.item) return search(t.left, x) 🠔 t.left: t의 왼자식 else return search(t.right, x) 🠔 t.right: t의 오른자식
insertSketch(t, x): 🠔 t: (서브) 트리의 루트 노드 레퍼런스, x: 검색하고자 하는 키 if (t = null) x를 키로 하는 노드를 t의 부모 밑에 매달고 끝낸다. else if (x < t.item) insertSketch(t.left, x) else insertSketch(t.right, x)
deleteSketch(r): 🠔 r: 삭제하고자 하는 노드 if (r이 리프 노드) 그냥 r을 버린다. else if (r의 자식이 하나만 있음) r의 부모가 r의 자식을 직접 가리키도록 한다. else r의 오른쪽 서브 트리의 최소 원소 노드 s를 찾는다. s를 r자리로 복사하고 s를 삭제한다.
1. 정수 h≥1에 대해, 높이 h인 포화 이진 트리의 리프 노드의 총 수 l(h)는 2ᵸ⁻¹이다.
2. 정수 h≥0에 대해, 높이 h인 포화 이진 트리의 총 노드 수 n(h)는 2ᵸ⁻¹이다.
3. 정수 h≥0에 대해, 높이 h인 이진 트리는 2ᵸ⁻¹개 이하의 노드를 갖는다.
4. 총 n개의 노드를 가진 이진 트리의 높이는 적어도 h≥ ⌈log₂(n+1)⌉이다.
5. 총 n개의 노드를 가진 이진 트리의 최대 높이는 n이다.
6. 이진 검색 트리의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
7. n개의 노드를 가진 이진 검색 트리의 점근적 평균 검색 시간은 Θ(logn)이다.
전위 순회
preOrder(r): if (r != null) r.visited = true preOrder(r.reft) preOrder(r.right)
중위 순회
inOrder(r): if (r != null) inOrder(r.reft) r.visited = true inOrder(r.right)
후위 순회
postOrder(r): if (r != null) postOrder(r.reft) postOrder(r.right) r.visited = true