[Tree] 탐색 트리, Search Tree

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 탐색 트리 (Search Tree) 

• 저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조

 

- 이진 탐색 (Binary search)

• 정렬된 데이터에서 중간값(median)을 기준으로 데이터를 두 부분으로 나눠가며 항목을 탐색하는 방법
• 이진 탐색의 수행 시간 : O(log(n))

 

- 이진 탐색 트리 (Binary Search Tree)

• 이진 탐색의 개념을 이진 트리에 표현한 자료구조
  • 노드에는 (key, value)를 저장
  • 임의의 노드 u와 왼쪽 서브트리의 노드 v, 오른쪽 서브트리의 노드 w에 대하여 다음의 성질을 만족 : key(v) <= key(u) <= key(w)
  • 이진 탐색 트리에 대한 Inorder traversal의 결과는 정렬된 순서대로

 

- 이진 탐색 트리의 연산

• Search : 탐색하고자 하는 키가 k라면, 루트의 키와 k를 비교하는 것으로 탐색을 시작
  
  • k가 루트의 키보다 작은 경우 -> 루트의 왼쪽 서브트리에서 k를 찾음
  • k가 루트의 키보다 큰 경우 -> 루트의 오른쪽 서브트리에서 k를 찾음
  • k가 루트의 키와 같은 경우 -> 탐색 성공, 해당 노드의 value를 리턴
  • 최솟값은 루트 노드로부터 왼쪽 자식을 따라 내려가며 None을 만났을 때 None의 부모가 가진 value임
• Insertion : (key, value)를 이진 탐색 트리에 삽입, search(key) 수행하되 None을 리턴하지 않음
  
  • 같은 key를 발견하는 경우 -> value를 갱신
  • 같은 key를 발견하지 못하는 경우 -> 새로운 노드를 만들어서 삽입
• Minimum deletion : 최솟값을 가진 노드 n을 찾아낸 뒤, n의 부모 노드 p의 왼쪽에 n의 오른쪽 자식 c를 연결
• Deletion : 삭제하고자 하는 노드 n의 key를 가진 노드를 찾은 후 이진 탐색 트리 조건을 만족하도록 삭제된 노드의 부모와 자식들을 연결
  • 삭제되는 노드의 자식이 없는 경우 : n의 부모 노드가 n을 가리키던 레퍼런스를 None으로 변경
  • 삭제되는 노드의 자식이 하나인 경우 : n의 부모 노드와 n의 자식 노드를 직접 연결
  • 삭제되는 노드의 자식이 둘인 경우 : n의 자리의 이진 탐색 트리를 중위 순회하며 n의 중위 후속자(Inorder successor) t를 n의 자리로 옮긴 후 n의 왼쪽 자식을 t의 왼쪽 자식으로, n의 오른쪽 자식에서 Minimum deletion을 수행하여 t의 오른쪽 자식으로 연결

 

- 수행 시간

• 연산의 수행 시간은 이진 탐색 트리의 높이에 비례, 즉 O(h) [log(n))(완전 이진 트리) <= h <= n(편향 이진 트리)]