이진 탐색 트리 (Binary Search Tree, BST)

정의

모든 원소는 키를 가지며 동일한 키가 없음

왼쪽 sub tree에 있는 key 값 < root의 key 값

root의 key 값 < 오른쪽 sub tree에 있는 key 값

왼쪽 sub tree와 오른쪽 sub tree 모두 이진탐색트리

 

특징

임의의 한 node를 삽입, 삭제, 탐색하는데 유리

완전 이진 tree가 아닐 경우가 多 → 연결 list로 구현

 

ex)

 

 

BST 탐색

key < root : 왼쪽 sub tree 탐색

key > root : 오른쪽 sub tree 탐색

key == root  : 탐색 완료

 

 

BST 삽입

동일한 key값 가진 원소 있는지 확인 후, 없으면 그 지점에 삽입

 

BST 삭제

leaf node 삭제	1개 child 갖는 non-terminal node 삭제	2개 child 갖는 non-terminal node 삭제
parent의 child field에 0 삽입	삭제된 node의 child를 삭제된 node 자리에 대체	왼쪽 sub tree에서 가장 큰 node로 대체 혹은 오른쪽 sub tree에서 가장 작은 node로 대체

 

 

BST 높이

최악의 경우 h = n

평균           h = O(log n)

 

 

균형 탐색 트리 (Balanced Search Tree)

최악의 경우에도 h = O(log n)

탐색, 삽입, 삭제 모두 O(log n) 소요

ex) AVL 트리