이진탐색트리(균형, 트립) 정리

이진 탐색 트리(BST; Binary Search Tree)

• 이진 트리 : 각 노드가 왼쪽, 오른쪽. 최대 두개의 자식 노드만 가질 수 있는 트리
• 왼쪽 가지를 따라 내려가면 더 작은 수
• 오른쪽 가지를 따라 내려가면 더 큰 수를 만남
• 이진 검색트리를 중위 순회하면 크기 순서로 정렬된 원소를 얻을 수 있다.

정렬된 배열의 특징

• 루트부터 왼쪽으로 쭉 내려가면 최소 값이 나온다.
• 루트부터 오른쪽으로 쭉 내려가면 최대값이 나온다.
• 루트가 배열의 중앙값은 아니다(트리가 불균형하게 생길수도 있다.)
  • 이걸 원하면 다른 트리 써야 함
• 부모 노드가 항상 나보다 한 등수 높은 것도 아니다. (오른쪽 리프를 생각해보자)

정렬된 배열보다 뛰어난 점

• 특정 원소가 존재 하는지 빠르게 확인할 수 있다
  • 노드의 값을 기준으로 다음 검색을 어떤 서브트리에서 해야하는지 결정
  • 검색을 반씩 줄여나갈 수 있음 (logN)
• 특정 원소보다 작은 값 찾기 쉽다. → 원소를 찾은 뒤 그 오른쪽 서브트리는 전부 작은 원소
  • k보다 작은 원소 몇 개인지
  • 크기 순일 때 앞에서부터 k번째 원소는 무엇인지
  • 위 연산이 필요하면 트리를 직접 구현해야 한다. → 트립 이용해 쉽게 구현하자
• 원소의 추가 삭제가 쉽다.
  • 삽입
    • 정렬된 배열은 삽입할 위치를 이진 검색으로 찾고, 이후 원소들을 한 칸씩 옮겨야 한다.
    • 이진 검색 트리는 삽입할 위치를 찾고, 참조만 걸어주면 된다.
  • 삭제 - 합치기 연산으로 구현
    • t 삭제 시 t 아래 두 서브 트리를 합치고,t 자리에 넣음
    • 합치기 연산
      • 두 서브 트리에서 A < B 성립
      • 이 점을 이용해 A의 오른쪽 서브트리와, B를 재귀적으로 합침

균형 이진 탐색 트리(BBST;Balanced Binary Search Tree)

• 이진 트리의 시간 복잡도는 높이(h)와 같다.
• 1,2,3 순으로 추가되는 것처럼 한쪽으로 기울면(skewed) 연결 리스트와 다를 바가 없다.
  • 높이도 자료의 수와 같아진다.
• 고루 평평해져(balanced)야 이진 검색이 의미가 있고 검색 효율이 최대 O(lgN) 이 나온다.

종류

• Red-Black Tree: 표준 라이브러리는 대부분 이 트리
• AVL 트리
• 트립

트립(Treap; Tree+ Heap)

• 균형을 만들기 위해 랜덤화된 이진 검색 트리
• Red-Black Tree, AVL Tree는 구현이 까다롭다.
• 트립은 비교적 구현이 간단하다.
• 정의
  • 이진 검색 트리의 조건 - 노드의 왼쪽 서브트리는 노드보다 항상 작고, 오른쪽 서브트리는 노드보다 항상 크다
  • 힙의 조건 - 모든 노드의 우선 순위는 각자의 자식 노드보다 크거나 같다.(우선순위가 높은 것부터 상위 노드가 된다.)
• 만드는 법
  • 각 노드에 대응 되는 우선순위 배열을 만든다.(난수로)
  • 우선순위가 높은 것부터 트리에 추가한다.
• 활용
  • k보다 작은 원소 몇 개인지
  • 크기 순일 때 앞에서부터 k번째 원소는 무엇인지