Binary Search Tree (이진 탐색 트리)

Binary Search Tree

Binary Search Tree Representation

• 이진탐색과 연결리스트를 결합한 자료구조이다.
• 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 있어야한다. 
• 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 있어야한다. 
• operation : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE
• average case : O(log n) (평균 높이 : log n)
• worst case : O(n)

 

Search

• 루트에서 시작. k를 찾을 때

        key[x]>k 이면 x의 왼쪽 subtree에서 search

        key[x]<k 이면 x의 오른쪽subtree에서 search

        key[x]가 k와 같으면 search 성공!

        x가 없으면 NIL반환

• Runnimg time : O(h), h: 트리 높이

 

 

최댓값(최솟값) 찾기

• TREE-MAXIMUM(x) :

        while right [x] 이 NIL이 아니면

            do x ← right [x]

        return x

 

• TREE-MAXIMUM(x) :

        while right [x] 이 NIL이 아니면

            do x ← left [x]

        return x

• Runnimg time : O(h)

 

Successor(Predecessor) 찾기

• successor : x 바로 위

    Case1: x의 오른쪽이 존재할 때

        successor (x) = x의 오른쪽 중 가장 작은 값

    Case2: x의 오른쪽이 비어있을 때

        현재 노드가 부모노드의 왼쪽 자식일 때 까지 올라간다.

        successor (x) = 현재 노드의 부모노드

    더 갈 수 없다면 x가 트리의 최대값이다. 

 

• predecessor : x 바로 아래
•  

• Runnimg time : O(h)

 

Insertion

• 이진 트리의 구조를 만족하도록 값을 삽입
• key[x]가 삽입할 값보다 작으면 왼쪽 자식으로 이동
• key[x]가 삽입할 값보다 크면 오른쪽 자식으로 이동
• x가 NIL이면 그곳에 삽입

 

• Runnimg time : O(h)

Deletion

Case1: 삭제할 노드의 자식노드가 없을 때 -> 그냥 삭제

Case2: 삭제할 노드에 자식노드가 1개 있을 때 -> 해당 노드를 지우고 해당 노드의 자식과 부모를 연결

Case3: 자식노드가 2개일 때 -> 해당 노드의 successor을 삭제된 자리에 삽입한다. 

 

Summary

• 모든 연산의 시간복잡도 : O(h)
• 높이가 작은 트리에 대해서는 빠르다. 
• 그러나 노드가 다 한쪽으로 치우쳐있어 h=n이 되는 경우 O(n)으로 비효율적이다.
• 이를 개선하기 위해 AVL 트리가 제안되었다.