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

이진 탐색 트리 목적:

이진 탐색: O(logN)이다. But 삽입과 삭제가 불가능하다. 

연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간 복잡도가 O(N)이다.

이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리'이다.

 

특징: 

- 각 노드의 자식이 2개 이하

- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼

- 중복된 노드가 없어야 함

중복이 있다면 굳이 이진검색트리를 사용하게 할 필요가 없다. 차라리 중복개수를 저장할 수 있게 노드의 구조를 바꾸는게 효율적이다. 

삽입과, 삭제가 이루어져도 위의 구조를 유지하는것이 핵심이다. 

 

시간복잡도:

탐색, 삽입, 삭제 모두 시간복잡도가 O(h)가 된다.  h = logN, worst h= N이다. 

이를 해결 하기 위해  AVL Tree와 Red Black Tree, B트리, B+트리가 생겼다.

 

삭제의 3가지 Case

1. 자식이 없는 leaf 노드일 때 -> 삭제

2. 자식이 1개 있는 노드일때 -> 지워진 자리에 자식 올리기. 

3. 자식이 2개인 노드일 때 -> 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기. 

 

AVL 트리의 경우 삭제 or 삽입이 이루어 질 때마다, Rotate을 통해서 높이차가 2이상 나지 않게 균형을 유지하는 트리이다. 

레드 블랙 트리는 자가 균형 이진 탐색 트리이다. AVL에서 자가라는 말이 붙은것.