Search Trees

Binary Search Trees

• Binary Tree
  : Map 항목을 저장할 수 있는 우수한 데이터 구조 -> key에 정의된 order relation
• Binary Search Tree
  : 각 위치 p가 key-value 쌍 (k, v)을 저장하는 이진 트리 T (p의 왼쪽은 k보다 작고, 오른쪽은 k보다 크다)
• Sorted Map
  • 항목은 key에 따라 순서대로 저장됨 -> 가장 가까운 이웃 query 지원 가능

Navigating a Binary Search Tree

• Recall
  : 이진 검색 트리 순서대로 이동 (왼쪽 서브트리 먼저 방문, 그 후 루트 방문, 그 후에 오른쪽 서브트리 방문)

• 이진 검색 트리 순서대로 순회하면 키 순서가 증가하는 위치 방문

• tree에 저장된 키 특성에 기초한 이진 검색 트리에 대한 추가 네비게이션 방법

Searches

• 이진 검색 트리에서 키 'k'를 찾기 위해 각 위치 p에서 질문함
  • 'k'는 top.key((p에 저장된 키)와 같음. 검색이 성공적으로 종료
• 최악의 running time은 O(h), T경로의 위치에서 T(T, p, k)가 루트에서 시작하여 한 단계씩 내려가는 위치에서 트리 검색 (T, p, k)호출
  

Insertion. M[k]=v

Deletion

: 삭제할 키 'k'로 항목을 저장하는 위치 p를 찾음, 검색 성공 시 노드 삭제

• Leaf Node
  

• one child node
  

• two children node