[자료구조] 8장 BST

1. BST

: 이진 트리 기반 효율적인 탐색 가능

 

2. 이진 탐색 트리 정의

: key(왼쪽 서브트리) =< key(루트 노드) =< key(오른쪽 서브트리)

  왼쪽 -> 루트 -> 오른쪽으로 순회하는 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있음.

 

3. 이진 탐색 트리의 탐색 연산

 

4. 이진 탐색 트리의 삽입 연산

: 탐색을 하다가 실패한 위치가 새로운 노드 삽입의 위치.

 

5. 이진 탐색 트리의 삭제 연산

  case1) 단말 노드 삭제: 부모 노드 찾아서 연결 끊음.

  case2) 자식이 하나인 노드 삭제: 노드 삭제하고 서브트리를 부모 노드에 붙임.

  case3) 두 개의 자식을 가진 노드 삭제: 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴.

 

6. 이진 탐색 트리의 성능

: 이진 탐색 트리에서 탐색, 삽입, 삭제 연산의시간 복잡도는 h에 비례.(트리 높이)

• 최선의 경우: h = log2n, O(logn)
• 최악의경우: h = n, O(n)

 

7. 균형 이진 탐색 트리(AVL Tree)

: 모든 노드의 왼쪽과 오른쪽 서브 트리의 높이 차가 1 이하

  비균형 상태면 스스로 재배치

  평균, 최선, 최악의 시간복잡도: O(log(n))

  - 균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이

    균형 인수가 +-1이하면 AVL 트리

 

8. 균형 이진 탐색트리의 연산

  - 탐색 연산: 이진 탐색 트리와 동일

  - 삽입 연산: 균형 항태 깨질 수도 있으므로 아래와 같이 함.

                    삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드의 서브트리들에 대해 다시 재균형.

                    LL, RR, LR(RR회전 -> LL회), RL(LL회전 -> RR회전) 타입

 

9. AVL Tree의 유효성 검증

• balance factor 확인
• 왼쪽 오른쪽 아이템 순서 확인