11. Balanced Search Tree

1. 2-3 search trees

2-3 search tree는 2-node(1 key, 2 children), 3-node(2 key, 3 children)을 가질 수 있는 추상적 search tree이다.
일반적인 binary search tree와는 다르게 root node부터 시작하게 recursive하게 탐색하고 더 이상 탐색할 수 없는
null link를 만나는 경우, node를 새로 생성하는 것이 아닌 마지막으로 탐색한 node에 key값을 넣은 뒤, 
node내부의 key갯수가 3개가 되면 node를 분리시켜 tree를 성장시킨다.

2-node에서 left children은 parent의 key보다 작고, right children은 parent의 key보다 크다.
3-node에서 left children은 3-node의 left key(right보다 작음)보다 작고, middle children은 left key와 right key사이에
있으며, right children은 right key보다 크다.

4-node는 key가 3개일때 임시적으로 만들어지고, middle key를 parent로 해서 left children은 left key로 
right children은 right key로 하여 분리된다.
따라서, tree의 기하학적 구조를 변경시키는 것은 4-node의 transformation밖에 없는데,
이것은 하부에 존재하는 subtree의 구조를 그대로 유지하며 진행된다.
따라서, 초기에 대칭적인 구조를 가지고 transformation이 해당 구조를 변경시키지 않으면서 진행되므로,
2-3 tree는 perfect balance를 유지시킨다.

따라서, 하나의 node에 더 많은 key들을 담을 수 있고, tree의 balance가 보장되기 때문에
Binary search tree(BST)과 비교했을 때 성능이 보장되고, 더 뛰어나다.
성능은 worst case에서 logN정도이고, best case에서 0.631logN정도이다.
삭제 연산의 경우도 logarithmic time의 성능을 보여준다.


2. Left leaning red-black BSTs (LLRB tree)

2-3 tree를 BST를 이용하여 구현한 것이다. BST와 차이점이 있다면, link들이 red/black의 색깔을 가지고,
red link로 연결된 node들은 2-3 tree에서 하나의 node를 의미한다. 하지만 red link는 항상 left-leaning이여야 한다.
만약 insert시 right leaning이 생성될 경우 rotate하여 바꿔주어야 한다.
만약 3개의 node가 red link로 연결되어 있을 경우, 4-node를 의미하므로 하나의 parent node와
두개의 children node로 분리되며 black link로 연결된다, parent node는 그것의 parent node와 red link로 연결된다.
이 때, 일시적으로 right rotate를 할 수도 있다.

search는 BST의 방식과 동일하고, insert는 BST와 동일하게 삽입하고 red link로 연결한다.
Black link의 생성은 4-node의 분리에서만 생성된다.
또한, LLRB tree는 BST에서 left roate, right rotate, flip color만 추가 된 것으로 볼 수 있다.

2-3 tree는 balanced tree이므로, 이를 구현한 LLRB또한 balanced tree이다.
성능은 평균적으로 1logN 정도의 성능이며, worst case에서도 2logN정도의 성능이 나온다.
삭제연산의 경우도 마찬가지이다.

한가지 재밌는 스토리는 예전에 어떤 DB 회사에서 Hibbard deletion(BST에서 삭제연산 sqrt(N)의 성능이 나옴)을
Red-black BST에서 사용한 것이다. 당연히 이럴 경우에는 성능이 보장되지 않았고, 그 회사는
특정 height를 초과하면 error-recovery가 되는 방식으로 해결하려고 하였다.
하지만, 이것은 height limit을 초과해버리는 문제를 낳았고, DB회사는 고소를 당했다.
올바른 알고리즘을 쓰는 것이 중요하다...

3. B-trees

메모리의 페이지 구조에서 한가지 중요한 점은 메모리의 페이지들을 탐색하는 속도가
메모리 페이지 내의 데이터를 탐색하는 것 보다 훨씬 느리다는 것이다.

B-tree를 사용하면 이러한 문제를 해결할 수 있다. B-tree는 2-3 tree를 일반화한 것인데,
size가 M이며, M-1개의 key를 갖을 수 있는 node를 생성한다. M은 메모리에서는 page의 size가 될 수 있다.
key가 M-1개까지 가능하므로, children은 M개까지 가능하다.
2-3 tree와 다른점은 key갯수가 M이 될 경우 node의 분리가 일어난다.
따라서, root node를 제외한 모든 internal node는 M/2와 M-1개 사이의 key를 갖는다.
이것은 B-tree가 log<M-1>N 과 log<M/2>N 사이의 성능을 갖게 된다는 것을 말한다.
이것은 매우 뛰어난 성능을 보여주게 되는데 만약, M = 1024 이고 N = 62billion 이라면, 최대 탐샛횟수는 4에 불과하다.
항상 root page를 메모리에 상주시킴으로서 불과 몇번의 탐색만으로 시스템상의 모든 데이터를 찾을 수 있다는 의미이다..!

이런 red-black BST나 B-tree는 실제로도 수많은 운영체제, DB 등에서 많은 응용으로 사용되고 있다.