Select Git revision
splay_operation_test.py
-
Ondřej Mička authoredOndřej Mička authored
splay_operation.h 4.54 KiB
// A node of the tree
class Node {
public:
int key;
Node* left;
Node* right;
Node* parent;
// Constructor
Node(int key, Node* parent=nullptr, Node* left=nullptr, Node* right=nullptr) {
this->key = key;
this->parent = parent;
this->left = left;
this->right = right;
if (left) left->parent = this;
if (right) right->parent = this;
}
};
// Binary tree
class Tree {
public:
// Pointer to root of the tree; nullptr if the tree is empty.
Node* root;
Tree(Node* root=nullptr) {
this->root = root;
}
// Rotate the given `node` up. Perform a single rotation of the edge
// between the node and its parent, choosing left or right rotation
// appropriately.
virtual void rotate(Node* node) {
if (node->parent) {
if (node->parent->left == node) {
if (node->right) node->right->parent = node->parent;
node->parent->left = node->right;
node->right = node->parent;
} else {
if (node->left) node->left->parent = node->parent;
node->parent->right = node->left;
node->left = node->parent;
}
if (node->parent->parent) {
if (node->parent->parent->left == node->parent)
node->parent->parent->left = node;
else
node->parent->parent->right = node;
} else {
root = node;
}
Node* original_parent = node->parent;
node->parent = node->parent->parent;
original_parent->parent = node;
}
}
// Look up the given key in the tree, returning the
// the node with the requested key or nullptr.
Node* lookup(int key) {
// TODO: Utilize splay suitably.
Node* node = root;
while (node) {
if (node->key == key) {
return node;
}
if (key < node->key)
node = node->left;
else