Bst

BST

BST 는 최악의 경우 선형시간을 갖는다고 까인다. 하지만 평균적으로 O\((\log N)\) 의 높이를 유지하기 때문에 quick sort 와 비슷하다고 볼 수 있다.

이러한 랜덤성을 보장해주는 자료구조로는 Treap 이 있다.

Red Black Tree

Tree 는 Node 는 최대 두 Child 를 갖고 없다면 null 로 되어 있다. Leaf Node 는 null 인 Node 이다.

Red Black Tree 는 다음 3가지 속성을 만족시키는 BST 이다.

1. Root and the Leaves are Black.
2. Every child of Red node are Black.
3. The Black Height of a node must be well defined at any node of the tree, which is the number of black nodes on any path from a node to a leaf (not included the node itself).

Proof for Nearly Balanced

Black Node 만 생각하면 RBT 는 balanced BST 임을 알 수 있다. 그러므로 다음이 성립한다.

\[n \geq 2^{b_h} -1\]

Red Node 는 Black Node 보다 많을 수 없으므로 실제 sub tree 의 높이 차이는 두배 이상이 될 수 없다. 그럼 다음이 성립한다.

\[h_b \geq \frac{h}{2}\]

이 둘을 통해 우리는 다음을 알 수 있다.

\[n \geq 2^{b_h} - 1 \geq 2^{h/2}-1\]

즉 \(2\log{n+1} \geq h\) 이므로 \(h\) 는 O(\({\log{n}}\)) Complexity 를 갖음을 알 수 있다.

Insert / Delete

가능한 경우의 수가 한정되어 있어서 각각에 맞추어 RBT 조건이 맞도록 작업을 수행하는 것이 핵심이다. 세세한 디테일은 이해할 필요가 없고 재귀적으로 수행되기 때문에 O(\({\log{n}}\)) Complexity 를 갖는다고 우선 이해하면 된다.

삽입/삭제 한 노드를 x, 부모노드를 y, 조부모 노드를 z, 부모(y) 의 형제 노드를 w 라고 하자.

삽입할 때 3번 조건을 위해서 x 를 Red 로 지정한다.

• y 가 Black 이면 할일이 없다.
• y 가 Red w 가 Red 이면 둘다 black 으로 하고 z 를 Red 로 바꾼다. z 의 부모가 Red 이면 재귀적으로 이 작업을 수행한다. 만약 Root 를 Red 로 바꾸는 경우 그냥 Black 으로 둔다. z 의 Black Height 는 1 증가하지만 z 의 부모노드의 Black Height 는 바뀌지 않는다.
• y 가 Red w 가 Black 이면 y 가 z 의 Left/Right Child 인지에 따라 아래의 서술의 좌우방향이 바뀐다. 아래는 Left Child 기준이다.
  • x 가 y 의 right child 이면 회전을 해서 y 가 x 의 left child 가 되도록 한다. 그리고 y 를 x 로 간주하고 아래를 진행한다.
  • x 가 y 의 left child 이면 x 와 z 가 형제가 되도록 Tree Rotation 을 수행한다. 그리고 y 를 Black, w 를 Red 로 바꾼다.

Skip List

Insert, Search, Delete, Iterate(Sorted Order), Min/Max 모두 가능한 Heap, BST 를 대체 가능한 자료구조이다. 성능은 probabilistic gaurantees 상 BST 와 비슷하다. 최악의 경우 무한루프도 가능하지만 이는 0 에 수렴한다. 장점은 BST 와 달리 Min/Max 가 상수 시간에 구할 수 있다는 점이다.

동작

시작점과 끝이 -inf, inf 인 sorted list 를 Layer 라고 하자. 가장 하위 Layer 에는 모든 값이 있고 상위 Layer 는 하위 Layer 의 일부만 존재한다. 상위 Layer 와 하위 Layer 는 같은 Key 를 같는 Node 끼리 연결되어 있다.

검색은 가장 상위 Layer 의 -inf Node 에서 시작된다. 선형탐색 중에 다음 Node 의 Key 가 현재 Key 를 넘어서면 하위 Layer 로 넘어간다. 상위 Layer 보다 하위 Layer 에 더 많은 Node 가 있기 때문에 선형탐색과 비교해 Skip 이 많이 일어나게 된다.

삽입은 검색을 우선 수행한다. 그러면 가장 하위 Layer 에 도착하게 되는데 여기서 Node 를 추가한다. 그리고 코인을 던져서 상위 Layer 에도 Node 를 추가할지를 결정한다. 이때 Layer 당 마지막 탐색 Node 를 저장해서 빠르게 상위 Layer 로 넘어간다. 그리고 코인을 던지기를 반복한다.

평균 성능

상위 Node 를 만들 확률을 \(p\) 라고 하면 임의의 Key 의 평균 높이는 뭘까?

\[\sum_{i=1}^{i\rightarrow \infty}{p^{i-1}(1-p)} = \alpha = 1\] \[\sum_{i=1}^{i\rightarrow \infty}{i p^{i-1}(1-p)} = \alpha + \alpha p + \alpha p^2 + ... = 1/(1-p)\]

geometric series 의 기댓값인 \(1/(1-p)\) 이 된다.

그러면 한 layer 에서 선형탐색을 하는 평균적인 횟수는 어떻게될까? 이는 위와 비슷하게 구해서 1 임을 얻을 수 있다.

이를 합치면 평균적으로 O(\(1/(1-p)\)) 임을 알 수 있다.

최악의 성능

그럼 적어도 하나의 Node 가 높이가 \(h\) 이상인 확률은 얼마나 될까?

하나의 Key 에서의 높이가 \(h\) 이상인 확률은 \(p^h \alpha = p^h\) 이다. 그러면 적어도 하나의 Key 에서의 높이가 \(h\) 이상일 확률은 단순한 확률합인 \(np^h\) 보단 작게 된다.

이정도의 Boundary 만으로도 우리는 무한한 \(h\) 일 확률은 0 에 수렴함을 알 수 있다. 그렇다면 Balanced BST 보다 성능이 안좋을 확률은 어떨까?

\(h\) 를 \(c \log n\) 로 대체하고 \(p = 0.5\) 라고 가정하면 다음과 같다.

\[n / 2^{c\log{n}} = 1/n^{c-1}\]

이는 매우 작은 확률임을 알 수 있다.

참고자료

Trees and Graphics:Basic, University of Colorado Boulder, Cousera