2. 찾고자 한 값이 중간값과 같으면 성공, 만약 값이 하나밖에 남지 않았을때 찾는 값과 중간값이 다르면 실패한 것이다.
3. 만약 찾는 값 < 중간값 이면, 중간값의 왼쪽 list로 가 위 과정을 반복한다.
4. 만약 찾는 값 > 중간값 이면, 중간값의 오른쪽 list로 가 위 과정을 반복한다.
2. Binary Search Tree
위 Binary Search를 Tree로 구현한 것이 Binary Search Tree이다. 정렬된 Binary Tree는 항상 Left < Root < Right를 만족해야한다. 전체 Tree로 보았을 때 한 root의 left SubTree의 key값들은 root보다 항상 작아야 하고 right SubTree는 root보다 항상 커야한다.
위 Tree처럼 100을 기준으로 left SubTree의 key값들은 전부 100보다 적고 right SubTree의 key값들은 100보다 크다.
그럼 Binary Search Tree에서 값을 insert, delete하는 방법은 무엇일까?
Insert insert 80을 할때, 80의 위치를 찾아주어야 한다.
80<100 이므로, 100의 left child로 이동
↓
80 >75 이므로, 75의 right child로 이동
↓
80<90 이므로, 90의 left child로 이동
↓
90의 left_child는 NULL이므로 90의 left_child에 80을 넣어준다.
insert 80을 한 결과값
delete node를 delete할때 세가지 경우의 수가 있다.
- delete leaf node : 이 경우 delete할 node를 찾고 NULL로 바꿔주면 된다.
예를 들어 위 binary tree에서 delete 50을 할 때, 50은 leaf node이므로 노드를 삭제하고, 대신NULL을 넣으면 된다.
- delete interior node that has a child node : delete할 노드가 한 child node를 가지고 있다면 삭제한 노드대신 child 노드를 넣어주면 된다.
예를 들어 위 delete에 이어서 delete 75를 할 때 75는 하나의 child node를 가지고 있으므로 75를 삭제한 후 75의 자리에 90을 넣어주면 된다.
- delete interior node that has two child nodes : delete할 노드가 두 child nodes를 가지고 있다면 1) delete할 노드의 right subtree의 가장 작은 node를 올리거나 2) delete할 노드의 left subtree의 가장 큰 node를 올린다.
예를들어 위 delete에 이어서 delete 150을 할 때 150은 두개의 child nodes를 가지고 있다. 때문에 150의 left subtree에서 가장 큰 수인 120을 올리거나 또는 right subtree에서 가장 작은 수인 160을 올리면 된다.
3. Big O notation of binary tree
그럼 binary tree에서 key값을 찾을때 얼마만큼의 시간이 드는지 알아보자.
일단 Big O notation이란, 알고리즘의 효율성을 나타내 준다. n개의 자료가 있을 때 기본 횟수를 의미하는데, 보통 상수항이나 개수를 무시하고 가장 영향값이 큰 부분만 나타낸다.
1) 정렬이 안되어 있거나, 한쪽으로 쏠린 Binary Tree인 경우 n개의 자료가 있을 때 보통 n번의 연산이 필요하다. : O(n)
2) 잘 정렬된 Binary Tree나, height-balanced binary Tree인 경우 : O(log2 n)
이때 search연산은 tree의 height에 따라 값이 변화한다. log2 n = h라고 할때 n은 전체 노드의 개수 이다. 어떤 key값을 찾을 때 level마다 비교를 함으로 최대 높이 만큼의 연산을 한다. 때문에 높이가 h일때 최대 노드의 개수는 2^h-1이므로 h는 BigO로 나타냈을 때 O(log2 n)이라고 할 수 있다. 최악의 경우 (정렬이 안된 binary Tree, degenerate binary Tree) BigO는 O(n)이다.
