[자료구조](10)[이진탐색트리]

이진 탐색 트리(BST)

모든 노드가 다음의 규칙을 만족하는 이진트리
    왼쪽 subtree의 모든 값들은 현재 노드보다 작고
    오른쪽 subtree의 모든 값들은 현재 노드보다 크다.
(단, 보통은 중복 허용 안함)

 

BST의 탐색
    찾으려는 값에 따라 작으면 왼쪽, 크면 오른쪽으로 가기
    만약 leaf에 도달해도 못 찾았다면 해당 요소가 없다

BST의 삽입
    적당히 탐색하고 알맞은 위치에 넣기

BST의 삭제

• 만약 leaf 노드라면 그냥 삭제
• 만약 leaf 노드가 아니라면
  해당 노드 기준 왼쪽 subtree의 제일 큰 값
  또는 노드 기준 오른쪽 subtree의 제일 작은 값을 선택해 노드 삭제한 자리에 넣기

연산의 시간 복잡도

	최선	평균	최악
탐색	O(1)	O(logN)	O(N)
삽입	O(1)	O(logN)	O(N)
삭제	O(1)	O(logN)	O(N)

최선일 땐 뿌리 노드가 원하는 값일때
최악일 땐 편향 이진트리라 선형 자료구조에서 연산을 진행하는 것과 동일하게 O(n)

 

AVL

 

스스로 균형을 잡는 이진 탐색 트리
    BST에서 편향 이진트리처럼 치우쳐 있다면, 트리를 쓰는 장점 없이 선형 자료구조와 비슷해진다.
    따라서 효율을 위해 스스로 균형을 잡는 AVL을 사용
    -> 모든 subtree들은 균형 이진트리다.
BF: 한 노드를 기준으로 왼쪽의 height - 오른쪽의 height
    균형을 잡는 척도로 BF(Balance Factor)을 사용한다.
    모든 노드의 BF는 -1, 0, 1 중 1개여야 한다.
균형 잡는 방법
    문제가 발생한 가장 leaf에 가까운 노드를 기준으로 순서를 바꿔준다.

• LL (or RR) case: 문제가 발생한 원인이 왼쪽 노드의 왼쪽 노드일 때, (RR일 땐 반대)
  가운데 값을 root 노드로 옮긴다

      a                    b
     /                    / \
    b          ->        a   c
   /
  c

• LR (or RL) case: 문제가 발생한 원인이 왼쪽 노드의 오른쪽 노드일 때, (RL일 땐 반대)
  LR에 있는 노드를 올려서 LL로 바꾸고 처리한다.

     a                    a              b
    /                    /              / \
   c          ->        b         ->   a   c
    \                  /
     b                c