[Algorithm] 6-2. Binary Search Tree

저번 시간에는 어려운 개념인 amortized analysis라는 알고리즘 분석 방법에 대한 내용에 대해 알아보았다.

이번 시간에는 binary search tree, 그 중에서도 Red-Black Tree에 대해 알아보도록 하겠다.

 

 

 

 

 

 

 

● Binary Search Trees

- binary search tree는 주로 dictionary라는 추상 자료형을 표현하기 위해 주로 사용된다. 임의의 key를 가진 원소를

  삽입, 삭제, 탐색할 수 있고, 최악수행시간은 O(n)이다.

- 하지만 balanced binary search tree일 경우에는 최악수행시간이 O(log(n))일 것이다.

- 순서가 있는 집합에서의 key를 가지는 노드를 가진 트리이고, 자식은 최대 2개이다.

- 왼쪽 서브트리의 모든 키들은 현재 노드의 키보다 클 것이다.

- 오른쪽 서브트리의 모든 키들은 현재 노드의 키보다 작을 것이다.

- 이 경우에 중위 순회(inorder traverse)로 노드들의 키를 정렬하면 키가 오름차순으로 정렬되어 나올 것이다.

 

 

 

 

 

 

 

 

● Binary Search Tree의 모양

- 같은 키들을 가진 노드들로 binary search tree를 만든다고 하더라도 모양이 서로 다를 수 있다.

 

- 검은색 점들은 empty tree, 즉 leaf, 끝을 나타내고 external node에 해당한다.

- 키를 가지고 있는 노드들은 다 internal node이다.

- 왼쪽 트리든 오른쪽 트리든 중위 순회를 하면 20, 30, 40, 50, 60, 80으로 오름차순 순서대로 수가 나올 것이다.

- 루트에서부터 50까지 가려면 왼쪽 트리는 3단계를 거쳐야하고, 오른쪽 트리는 5단계를 거쳐야한다.

  → 똑같은 원소들이라도 어떻게 트리를 그리느냐에 따라 다르다.

 

 

 

 

 

 

 

 

● Binary Search Tree Retrieval

Element bstSearch(BinTree bst, Key K)
	Element found
    if (bst == nil)
    	found = null;
    else
    	Element root = root(bst);
        If(K == root.key)
        	found = root;
        else if (K < root.key)
        	found = bstSearch(leftSubtree(bst), K);
        else
        	found = bstSearch(rightSubtree(bst), K);
   return found;

- binary search tree에서 특정 키를 가진 노드를 찾는 의사코드이다.

 

- 특정 키를 가진 노드를 찾는동안 트리의 internal node들의 수를 사용한다.

- 한 줄로 길게 노드가 연결된 경우라면, 최악의 경우이겠고, O(n)의 시간이 걸릴 것이다.

- full binary tree나 complete binary tree와 같이 balanced된 트리의 경우에는 최선의 경우일 것이고,

  O(logn)의 시간이 걸릴 것이다.

  → 이것은 각 트리의 높이에 binary search tree의 탐색 시간이 비례함을 나타낸다. O(h)

- 효율적인 알고리즘을 위해서는 트리를 최대한 균형있게 만들어야 h가 작아질 것이다.

- 그런데 이렇게 bast case를 위해서는 트리의 균형을 계속 잘 유지하는 것이 중요하겠고, Binary Tree Rotation이

   중요할 것이다.

  → 많이들 배운 AVL tree는 왼쪽과 오른쪽 sub tree의 높이가 기껏해야 1 차이나는 것이고, 여러 rotation으로 tree를

     균형 있게 유지한다.

 

 

 

 

 

 

 

 

다음 시간에는 balanced search tree 중 하나인 Red-Black Tree에 대해 자세히 살펴보도록 하겠다.