알고리즘 문제 해결 전략 2 6장 트리 (4)

22.6 균형 잡힌 이진 검색 트리 직접 구현하기:트립
문제는 AVL트리나 레드 블랙 트리 등 교과서에 실리는 대부분의 균형 잡힌 이진 검색 트리들은 구현이 매우 까다로움. 구현이 간단한 이진 검색 트리를 사용함. 대표적인 것은 트립(treap).

 

트립의 정의 
트립은 입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 일종의 랜덤화 된 이진 검색 트리임. 트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고 난수에 의해 임의대로 결정됨. 이와 같은 속성을 유지하기 위해 트립은 새 노드를 추가될 때마다 해당 노드에 우선순위를 부여함. 트립은 항상 부모의 우선순위가 자식의 우선순위보다 높은 이진 검색 트리를 만듭니다. 트립의 조건을 다음 두 가지로 정리할 수 있음. 트립을 이해하는 또 다른 방법은 노드들을 우선순위가 높은 것부터 순서대로 추가한 이진 검색 트리라고 생각하는 것임. 

 

트립의 높이

랜덤화가 의미가 있으려면 노드의 순서를 임의로 바꾸었을 때 트리 높이의 기대치가 O(N) 보다 작아야 함. 이것을 증명하는 한 가지 방법은 트리를 한 단계 내려갈 때마다 후보가 되는 원소의 수가 선형으로 줄어드는 것이 아니라 지수적으로 줄어든다는 점을 보이는 것임. 우선수위를 임의로 부여하기 때문에 모든 값은 루트가 될 가능성이 같고, 따라서 1부터 ㅇN까지의 모든 r의 출현 확률이 같음. 따라서 모든 r에 대한 값의 평균을 취하도록 함. 다시 말해 한 단계 내려갈 때마다 후보의 수가 평균적으로 2/3으로 줄어든다는 것임. 

 

트립의 구현

typedef int KeyType;
struct Node {
	KeyType key;
	int priority, size;
	Node* left, * right;
	Node(const KeyType& _key) :key(_key), priority(rand()), size(1), left(NULL), right(NULL) {}
	void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
	void setRight(Node* newRight) { right = newRight; calcSize(); }
	void calcSize() {
		size = 1;
		if (left) size += left->size;
		if (right) size += right->size;
	}
};

트립의 노드 객체는 포함하는 원소 key 외에도 우선순위 priority를 가진다는 점임. 또 하나 유의할 점은 자신을 루트로 하는 서브트리에 포함된 노드의 수를 저장하는 size멤버임. 

 

노드의 추가와 '쪼개기' 연산

typedef pair<Node*, Node*> NodePair;
NodePair split(Node* root, KeyType key) {
	if (root == NULL) return NodePair(NULL, NULL);
	if (root->key < key) {
		NodePair rs = split(root->right, key);
		root->setRight(rs.first);
		return NodePair(root, rs.second);
	}

	NodePair ls = split(root->left, key);
	root->setLeft(ls.second);
	return NodePair(ls.first, root);
}

Node* insert(Node* root, Node* node) {
	if (root == NULL) return node;
	if (root->priority < node->priority) {
		NodePair splitted = split(root, node->key);
		node->setLeft(splitted.first);
		node->setRight(splitted.second);
		return node;
	}
	else if (node->key < root->key)
		root->setLeft(insert(root->left, node));
	else
		root->setRight(insert(root->right, node));
	return root;
}

 

노드의 삭제와 '합치기'연산

merge() 내부에서 두 노드 중 하나가 NULL인지 확인하기 때문에 root가 한쪽 자손만 갖고 있는 경우, 그리고 root가 자손이 없는 경우 등을 모두 별도의 예외 처리 없이 처리할 수 있음.

Node* merge(Node* a, Node* b) {
	if (a == NULL) return b;
	if (b == NULL) return a;
	if (a->priority < b->priority) {
		b->setLeft(merge(a, b->left));
		return b;
	}
	a->setRight(merge(a->right, b));
	return a;
}

Node* erase(Node* root, KeyType key) {
	if (root == NULL) return root;
	if (root->key == key) {
		Node* ret = merge(root->left, root->right);
		delete root;
		return ret;
	}
	if (key < root->key)
		root->setLeft(erase(root->left, key));
	else
		root->setRight(erase(root->right, key));
	return root;
}

 

K번째 원소 찾기

주어진 서브트리의 노드들을 포함한 원소의 크기 순으로 나열했을 때 번째로 오는 노드를 찾는 연산임. 왼쪽 서브트리의 크기가 l이라고 할 때, 다음과 같이 세 개의 경우로 나눌 수 있음.

k<=l : k번째 노드는 왼쪽 서브트리에 있음

k = l +1 : 루트가 k번째 노드임

k > l + 1 : k번째 노드는 오른쪽 서브트리에서 k-l-1번째 노드가 됨.

kth() 함수의 시간 복잡도는 트리의 높이에 비례하기 때문에, 트립 등의 균형 잡힌 이진 검색 트리에 적용해야만 O(lgN) 시간에 수행할 수 있음.

Node* kth(Node* root, int k) {
	int leftSize = 0;
	if (root->left != NULL) leftSize = root->left->size;
	if (k <= leftSize) return kth(root->left, k);
	if (k == leftSize + 1) return root;
	return kth(root->right, k - leftSize - 1);
}

 

X보다 작은 원소 세기

int countLessThan(Node* root, KeyType key) {
	if (root == NULL) return 0;
	if (root->key >= key)
		return countLessThan(root->left, key);
	int ls = (root->left ? root->left->size : 0);
	return ls + 1 + countLessThan(root->right, key);
}