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

1. 개념

: 계층적인 구조를 가지는 트리중에서 각 노드의 자식이 최대 2개인 이진 트리이며, 정렬된 데이터를 빠르게 검색, 삽입, 삭제 할 수 있도록 설계된 자료구조

 

2. 구조와 특징

1) 각 노드의 왼쪽 서브트리에는 "현재 노드보다 작은 값"이 저장됨

2) 각 노드의 오른쪽 서브트리에는 "현재 노드보다 큰 값"이 저장됨

3) 각 서브트리도 위의 규칙을 만족해야 함

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

 

3. 이진 탐색 트리의 연산

1) 검색

- 탐색과정

① 루트에서 시작해서 찾고자 하는 값 X가 현재 노드 값보다 작으면 왼쪽으로 이동

② 크다면 오른쪽으로 이동

③ 탐색

---

 

2) 삽입

- 삽입과정

① 루트에서 시작해서 삽입할 값 X가 현재 노드보다 작으면 왼쪽으로 이동

② 크면 오른쪽으로 이동

③ 자식노드가 없는 비어있는 곳에 X를 삽입

 

---

 

3) 삭제

- 삭제과정

① 자식이 없는 노드 삭제 -> 그냥 삭제

② 자식이 하나인 노드 삭제 -> 부모 노드와 자식 노드를 연결

③ 자식이 둘인 노드 삭제 -> 후계자 또는 전임자로 대체

• 후계자(successor) : 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값
• 전임자(predecessor) : 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값

---

연산	평균 시간 복잡도	최악 시간 복잡도
검색	O(log N)	O(N)
삽입	O(log N)	O(N)
삭제	O(log N)	O(N)