[자료구조] 이진 탐색 트리(Binary Search Tree) (feat. red-black tree)

트리

: node, branch를 사용한 자료구조

이진트리

: branch가 최대 2개인 트리(=최대 2개의 자식노드를 갖는 트리)

 

배열과 연결리스트로 구현할 수 있지만, 일반적으로 연결리스트로 이진트리를 구현한다.
(노드 - 1.데이터 2.왼쪽 자식 포인터 3.오른쪽 자식 포인터)

 

이진 탐색 트리 (BST)

: 부모노드보다 작은 값은 왼쪽 자식노드, 큰 값은 오른쪽 자식노드에 위치시키는 특성을 가진 이진트리.

  같은 값을 같는 노드가 없다는 특징이 있다.

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리의 용도 : 데이터 탐색
시간복잡도 : O(log N)

장단점

장점 : 탐색속도 O(log N)으로 개선
단점 : 균형이 무너진 최악의 경우, O(N)까지 시간복잡도가 증가할 수 있다.

EX) 4라는 데이터를 탐색할 때, O(N)의 시간복잡도가 걸릴 수 있다..

worst case

---

레드 블랙 트리(red-black tree)

red-black tree

: 각 노드의 색을 레드 혹은 블랙으로 구분하여 데이터를 빠르고, 쉽게 찾을 수 있는 구조의 이진트리이며,
'self-balancing binary search tree'라고도 불린다.

레드 블랙 트리의 특성 : 데이터를 추가하거나 삭제할 때 데이터를 밸런스있게 맞춘다.

시간복잡도 : O(log N)

장단점

장점 : 데이터 검색, 삽입, 삭제 시 최악의 경우에서도 모두 O(log N)이 보장되는 자료 구조
단점 : balace를 맞춰야하기 때문에 데이터 추가, 삭제 과정이 복잡하다.