이진 탐색 트리, 트립

보통 c++의 set이나 map을 이진탐색트리로 구현한다. (avl트리나 레드블랙 트리)

 

하지만 set이나 map은 k번째로 큰 원소가 무엇인지 알 수없다.

 

이런 기능을 가능하게 하는 구조로 '트립'이 있다.

 

stl에서 사용하는 구조보단 느리지만 확률적으로 최악의 경우 로그시간에 동작한다.

 

<트립>

노드에 값 외에 우선순위를 추가로 갖는다. 우선순위는 생성시 랜덤하게 부여된다.

 

트립은 다음 두가지 속성 (bs tree + heap)을 만족해서 treap이라고 부른다.

1. 모든 노드에 대해 왼쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 작고, 오른쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 크다.

 

2. 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같다.

 

<코드>

typedef long long ll;
typedef int KeyType;
typedef pair<int, int> P;
const int MAX = 2e5 + 4;

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;
	}
};
typedef pair<Node*, Node*> NodePair;

Node* lowerBound(Node* root, KeyType key) {
	if (root == NULL) return NULL;
	if (root->key < key) return lowerBound(root->right, key);
	Node* ret = lowerBound(root->left, key);
	if (!ret) ret = root;
	return ret;
}

bool exists(Node* root, KeyType key) {
	Node* node = lowerBound(root, key);
	return node != NULL && node->key == key;
}

//root를 루트로 하는 트립을 key미만의 값과 이상의 값을 갖는
// 두개의 트립으로 분리
NodePair split(Node* root, KeyType key) {
	if (root == NULL) return NodePair(NULL, NULL);

	//루트가 key미만이면 오른쪽 서브트리를 쪼갠다.
	if (root->key < key) {
		NodePair rs = split(root->right, key);
		root->setRight(rs.first);
		return NodePair(root, rs.second);
	}
	else {
		NodePair ls = split(root->left, key);
		root->setLeft(ls.second);
		return NodePair(ls.second, 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; //node가 이 서브트리의 노드가 된다.
	}
	else if (node->key < root->key) //node가 추가된 root->left를 지금 root의 left로 설정
		root->setLeft(insert(root->left, node));
	else
		root->setRight(insert(root->right, node));
	return 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;
	}
	else {
		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;
}

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

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

int main() {
	FAST;
    /*
    Node * root = NULL;
    root->insert(root, val)
    root->erase(root, new Node(val))
    */
}

 

<추가>

https://www.acmicpc.net/problem/14463

구간 [l,r]이 여러개 주어질 때 서로 교차하는 쌍의 수를 구하는 문제. nlogn에 풀어야 함

 

https://suuntree.tistory.com/112

여기서 사용한 로직과 트립을 이요해서 풀어보려고 했지만 실패함. 나중에 해보자

 

https://www.acmicpc.net/submit/14463/17541570

실패했던 코드