PS/PS 일반
이진 검색 트리 구현
푸르른강물을먹이를찾아어슬렁거리는연어처럼
2020. 10. 7. 23:18
typedef int KeyType;
struct Node {
KeyType key;
Node* left, *right;
int priority;
int size;
Node(const KeyType& _key) :key(_key), left(NULL), right(NULL), priority(rand()), size(1), {
}
void setLeft(Node *newLeft) {
left=newLeft;
countSize();
}
void setRight(Node* newRight) {
right = newRight;
countSize();
}
void countSize() {
size = 1;
size += left->size;
size += right->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->left = splitted.first;
node->right = splitted.second;
return node;
}
else if (node->key < root->key)
root->setLeft(insert(root->left, node));
else
root->setRight(insert(root->right, node));
return node;
}
//max(a) < min(b) 일 경우 합침.
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(b, a->right));
return a;
}
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);
}
종만북에 그대로 있는 코드들을 합쳐놓은 코드이다.
정리를 위해 여러 코드를 통합해놓았다.
Tree와 heap을 합친
트립
이라는 자료구조를 구현해놓은 것이다.