자료구조 Binary Search Tree (이진탐색트리)

- 이진 탐색 트리 Binary Search Tree

 

왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진트리이다.

 

각 노드의 자식이 2개 이하이며 탐색 효율이 높은 편이며

중복된 키를 허용하지 않는다.

삽입은 루트에서 시작해서 비교한다.

 

중간에 있는 노드를 삭제할 경우 해당 자식 노드를 삭제할 노드 위치로 옮기고,

 

자식이 두 개인 노드의 경우는 오른쪽 서브 트리 최솟값 또는 왼쪽 트리 최댓값 중 하나를 삭제 노드 위치로 옮긴다.

 

 

 

 

- 시간 복잡도

삽입, 검색, 삭제가 모두 트리의 높이이다

 

트리가 균형상태인 경우 O(logN)

 

불균형 상태인경우 O(N) 만큼의 시간 복잡도를 갖는다.

트리가 편향되지 않기 위해서는 자가균형트리를 사용해야 한다.