이진트리 (Binary Tree)

각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만 가질 수 있는 트리.

이때 트리 내에 있는 모든 값들은 루트를 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값이 위치하는 것이 원칙이다. 이렇게 만들어진 이진트리를 중위 순회하면 가장 작은 값부터 가장 큰 값까지 쉽게 구할 수 있다.

이진트리로 구성된 자료구조에서 특정 값을 검색하는 로직을 구현할 때, 최악의 경우 연결리스트처럼 한쪽으로 기울어진 이진트리일 때, 노드의 개수만큼 값을 검색하는 코드를 반복해야하는 것이다.

이러한 단점을 개선하여 **균형 이진 검색 트리 (balanced binary search tree)**를 예시로 들 수 있다.

문제 : 너드인가? 너드가 아닌가?

균형 잡힌 이진검색트리 구현하기 : 트립(treap)

입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 단점을 해결하기 위해 고안된 랜덤화된 이진 검색 트리이다.

트리의 형태는 원소들의 추가 순서가 아니라 임의로 설정된다. 새 노드가 추가될 때 우선순위를 부여하는데, 이 우선순위가 난수로 생성되는 것이다.

트립은 항상 부모의 우선순위가 자식의 우선순위보다 높도록 설계하며, 난수로 생성되기 때문에 트리의 높이의 기대치는 항상 동일하다.

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(); }

	// size 멤버를 갱신한다.
	void calcSize() {
		size = 1; 
		if (left) size += left->size;
		if (right) size += right->size;
	}
};

트립은 위와 같이 구현할 수 있다.

트립에 새 노드(node)를 추가하기 위해서, 기존에 있는 트립에서의 root와 node의 우선순위를 고려해야한다.

이때 priority가 node > root인 경우에는 기존의 트리를 node가 가진 key를 기준으로 쪼갠다. 그 결과 우리는 node의 key보다 작은 원소들로 구성된 서브 트리 하나, node의 key보다 큰 원소들로 구성된 서브트리 하나를 만들어 node의 양쪽 서브트리로 놓을 수 있다.