자료구조 - Tree
Binary Tree
root를 중심으로 두 개의 서브 트리를 가지고 있는 tree를 말한다.
각각의 서브 트리 또한 binary tree여야 한다.
각 층별로 숫자를 매겨 이를 tree의 level이라 하며 루트 노드의 level은 0, 최고 level은 해당 트리의 height라고 한다.
BST(Binary Search Tree)
이진 탐색 트리(binary search tree)는 데이터를 저장하는 규칙을 가진 이진 트리의 일종이다.
- 이진 탐색 트리의 노드에 저장된 키는 유일하다.
- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진 탐색 트리의 탐색 연산은 O(log n)=O(h) 의 시간 복잡도를 갖는다.
탐색의 worst case는 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 편향 트리(skewed tree)일 경우 시간이며 복잡도가 O(n)이 된다.
이를 해결하기 위해 트리의 균형을 잡기 위한 재조정 기법인 Rebalancing이 등장했다.
이 기법을 구현한 트리 중 가장 유명한 것이 red-black tree이다.
Binary Heap
자료구조의 일종으로 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 Complete Binary Tree이며 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작된다.
Max Heap이란, 각 노드의 값이 해당 children 의 값보다 크거나 같은 complete binary tree를 말한다. ( Min heap 은 그 반대이다.)
Max heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도가 O(1)이다.
그리고 complete binary tree이기 때문에 random access가 가능하고 배열을 사용하여 효율적으로 관리할 수 있다.
public class MinHeap {
private int[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 1;
public MinHeap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
// Function to return the position of
// the parent for the node currently
// at pos
private int parent(int pos)
{
return pos / 2;
}
// Function to return the position of the
// left child for the node currently at pos
private int leftChild(int pos)
{
return (2 * pos);
}
// Function to return the position of
// the right child for the node currently
// at pos
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
// Function that returns true if the passed
// node is a leaf node
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size) {
return true;
}
return false;
}
// Function to swap two nodes of the heap
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
// Function to heapify the node at pos
private void minHeapify(int pos)
{
// If the node is a non-leaf node and greater
// than any of its child
if (!isLeaf(pos)) {
if (Heap[pos] > Heap[leftChild(pos)]
|| Heap[pos] > Heap[rightChild(pos)]) {
// Swap with the left child and heapify
// the left child
if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}
// Swap with the right child and heapify
// the right child
else {
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
// Function to insert a node into the heap
public void insert(int element)
{
if (size >= maxsize) {
return;
}
Heap[++size] = element;
int current = size;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}
// Function to print the contents of the heap
public void print()
{
for (int i = 1; i <= size / 2; i++) {
System.out.print(" PARENT : " + Heap[i]
+ " LEFT CHILD : " + Heap[2 * i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]);
System.out.println();
}
}
// Function to build the min heap using
// the minHeapify
public void minHeap()
{
for (int pos = (size / 2); pos >= 1; pos--) {
minHeapify(pos);
}
}
// Function to remove and return the minimum
// element from the heap
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
// Driver code
public static void main(String[] arg)
{
System.out.println("The Min Heap is ");
MinHeap minHeap = new MinHeap(15);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
minHeap.minHeap();
minHeap.print();
System.out.println("The Min val is " + minHeap.remove());
}
}
Output
The Min Heap is
PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6
PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84
PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17
PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10
The Min val is 3
Red Black Tree
- 각 노드는 Red or Black이라는 색깔을 갖는다.
- Root node 의 색깔은 Black이다.
- 각 leaf node 는 black이다.
- 어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다.
- 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다.
red black tree는 BST이므로 BST의 특징을 모두 갖는다.
Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node 로 간주한다.(Black)
Red-Black Tree 에 데이터를 저장하게되면 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요된다.
회전
삽입과 삭제는 n개의 키로 이루어진 레드블랙 트리에 대해서 O(log n) 시간에 수행된다.
이들은 트리를 수정하기 때문에 레드블랙 특성을 위반할 수 있으므로 트리 내의 일부 노드들의 색깔과 포인터를 변경해야 한다.
포인터를 변경하기 위해서 두 종류의 회전, 즉 좌회전과 우회전을 한다.
삽입
우선 BST 의 특성을 유지하면서 노드를 삽입을 하고 삽입된 노드의 색깔을 RED 로 지정한다.
Red 로 지정하는 이유는 Black-Height 변경을 최소화하기 위함이다.
삽입 결과 RBT 의 특성 위배(violation)시 노드의 색깔을 조정하고, Black-Height 가 위배되었다면 rotation 을 통해 height 를 조정한다.
이러한 과정을 통해 RBT 의 동일한 height 에 존재하는 internal node 들의 Black-height 가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.
삭제
삭제도 삽입과 마찬가지로 BST 의 특성을 유지하면서 해당 노드를 삭제한다.
삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라지게 된다.
그리고 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정한다.
지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지된다.