학교에서 진행되는 자료구조 수업을 듣고 중요한 부분 위주로 정리하였습니다. 내용 상에 오류가 있다면 댓글로 피드백 부탁드립니다!

map은 list-based, hash map으로 구현하였고 dictionary는 list-based, hash table, search table로 구현할 수 있었습니다. 이 자료구조들은 모두 선형적이었다는 공통점이 있었습니다. 이번에는 선형적이지 않은 tree 자료구조로 dictionary를 구현하는 방법을 알아보아요.

Search Tree의 종류

• binary search trees
  • AVL(Adelson-Velsky and Landis) trees
• multi-way search trees: binary tree보다 degree가 큰 트리
• red-black trees: binary tree와 multi-way tree의 특징을 모두 지닌 트리

이번 article에서는 AST를 포함한 BST(binary seach tree)를 다루겠습니다.

Binary Search Tree란

binary search tree는 다음을 만족한다.
임의의 노드 v, left subtree에 존재하는 노드 w, right subtree에 노드 w가
$key(u) <= key(v) <= key(w)$

• BST를 inorder traversal하면 키를 오름차순으로 방문한다.
• nonempty proper binary tree이다.
• leaf node는 data를 저장하지 않고 그저 자리를 채우는 역할(placeholder)를 한다.

BST Search Algorithm

의사코드

검색을 위한 의사코드는 다음과 같다.

Algorithm BSTSearch(k, v)
  T.isExternal(v) return v
  if K < key(v) => BSTSearch(k, T.left(v))
  else if K > key(v) => BSTSearch(k, T.right(v))
  else Return v ( k == key(v))

삽입(Insertion)

• k라는 key를 가진 entry를 BST에 삽입하기

1. 이전에 만든 BSTSearch 알고리즘으로 루트부터 key k를 찾기
2. k가 트리에 없으면 serach로 반환되는 leaf node에 k를 저장하고 left child, right child를 추가하여 internal node로 만들기(extend)
3. k가 트리에 있으면
   Insertion: 이미 값이 있으면 key k의 left child나 right child부터 다시 BSTSearch를 하고 도달하는 leaf 노드에 k를 저장한 뒤 extend를 한다.

삭제(Deletion)

1. key k가 트리에 있다고 가정하고 BSTSearch로 key k를 가진 노드를 찾음
2. k를 가진 노드 v의 children이 leaf node라면 한개의 leaf node를 지움
3. 다음 중 하나를 수행

• 2개의 external nodes => leaf 노드 하나 삭제하고 땡겨서 붙임
• 자식이 1개의 internal node(다른 1개는 external node) => empty node를 삭제하고 땡겨서 붙임
• 자식이 2개의 internal node => inorder 순서상 앞에 오는 것 또는 뒤에 오는 internal node를 선택하고 노드 v라 부르자.
  • v의 entry w를 복사한다
  • leaf node 하나 제거하고 땡겨서 붙임

Performance analysis

• BSTSearch
  • 트리의 height(키)를 h라 하면 방문 횟수는 h+1 이내
  • BSTSearch는 O(h)만에 실행된다.
  • skewed tree일 경우, 즉 최악의 상황인 경우 O(n)만에 실행된다.(n: 노드의 개수)
  • 이름만 tree이지 linear search와 같은 경우이다.
• find, insert, remove도 O(h)의 시간이 걸린다. 최악의 경우는 O(n)이다.
• findAll: O(h+s), s는 검색되는 엔트리의 개수
• best case(Complete binary tree)인 경우 : O(logn)만에 실행

Balanced Search Trees

• 트리의 height를 O(logn)으로 제한하기 위해서 rebalancing이나 restructuring과 같은 operation을 정의한다.
• 위의 operation 하는 트리를 balanced binary tree라 부름
• example: AVL trees, (2,4) trees, and Red-black trees
• 이 중 (2, 4) tree는 BST가 아닌 multiway search tree이고 avl과 (2,4)를 합친게 Red-black tree이다.

AVL Trees

다음의 조건을 만족하는 BST를 AVL 트리라고 부른다.
left subtree subtree와 right subtree를 가진 임의의 노드 v는
$|height(left(v)) - height(right(v))| <= 1$를 만족한다.

특징

• n의 entry를 저장하고 있는 AVL tree의 height는 O(logn)이다.
• 증명
  • m(h)를 internal node의 최소 개수라 하자.
  • m(1) = 1, m(2) = 2
  • h > 2이면, m(h) = 1 + m(h-2) + m(h-1)이다.
  • 1은 루트 노드, 나머지 두 개는 합치는 트리

삽입

• 일반적인 BST와 같이 시작한다.
• 추가적인 computation(연산)이 필요할 수도 있다.
• height-balance property를 유지해야 하기 때문이다.

Trinode Restructuring

• 새롭게 삽입된 노드 w부터 루트 노드까지 올라갈 때, 가장 처음 나오는 unbalanced node 를 z라 하자. 올라가는 길목에 있는 이전 두 노드를 x,y라 하자.
• inorder로 세 노드에 a, b, c로 순서롤 매긴다.
• b 노드를 3개의 노드 중 가장 위로 올린다.
• b를 몇 번 올리는지에 따라 single rotation, double rotation으로 나뉜다.
• b = y면 한 번, b = x면 두 번 로테이션 한다.

제거

• 제거 뒤에도 다시 트리가 unbalanced 해질 수도 있다.
• 이번에도 위로 올라가면서
• restructurin이 위에 있는 다른 노드이 balance를 망칠 수도 있다. 따라서 위로 올라가면서 루트가 닿을 때까지 blance 검사를 해야한다.

성능 분석

insert : $O(logn)$
remove : $O(logn)$
find: $O(logn)$
findAll: $O(logn + s)$(s는 entry의 개수)