summaryrefslogtreecommitdiffstats
path: root/libdimension/kD_splay_tree.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2009-10-05 19:40:02 +0000
committerTavian Barnes <tavianator@gmail.com>2009-10-05 19:40:02 +0000
commita80c569bf790a546da8d35b33ff8f18758358a31 (patch)
tree10de3f94c22f49d0a95acbfb4327ac4c7c3d7793 /libdimension/kD_splay_tree.c
parentf3ca60606f557f24b615860e1142c70c93802fc5 (diff)
downloaddimension-a80c569bf790a546da8d35b33ff8f18758358a31.tar.xz
Implement splay operation for kD splay trees.
Diffstat (limited to 'libdimension/kD_splay_tree.c')
-rw-r--r--libdimension/kD_splay_tree.c59
1 files changed, 58 insertions, 1 deletions
diff --git a/libdimension/kD_splay_tree.c b/libdimension/kD_splay_tree.c
index 24987c4..043be8a 100644
--- a/libdimension/kD_splay_tree.c
+++ b/libdimension/kD_splay_tree.c
@@ -51,8 +51,10 @@ dmnsn_kD_splay_node *dmnsn_kD_splay_copy(dmnsn_kD_splay_node *root)
if (root) {
node = dmnsn_new_kD_splay_node();
*node = *root;
- node->left = dmnsn_kD_splay_copy(node->left);
+ node->left = dmnsn_kD_splay_copy(node->left);
node->right = dmnsn_kD_splay_copy(node->right);
+ node->left->parent = node;
+ node->right->parent = node;
}
return node;
}
@@ -66,3 +68,58 @@ dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_node *root)
dmnsn_delete_kD_splay_node(root);
}
}
+
+/* Tree rotations */
+static void dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node);
+
+void
+dmnsn_kD_splay(dmnsn_kD_splay_node *node)
+{
+ while (node->parent) {
+ if (!node->parent->parent) {
+ /* Zig step - we are a child of the root node */
+ dmnsn_kD_splay_rotate(node);
+ return;
+ } else if ((node == node->parent->left
+ && node->parent == node->parent->parent->left)
+ || (node == node->parent->right
+ && node->parent == node->parent->parent->right)) {
+ /* Zig-zig step - we are a child on the same side as our parent */
+ dmnsn_kD_splay_rotate(node->parent);
+ dmnsn_kD_splay_rotate(node);
+ } else {
+ /* Zig-zag step - we are a child on a different side than our parent is */
+ dmnsn_kD_splay_rotate(node);
+ dmnsn_kD_splay_rotate(node);
+ }
+ }
+}
+
+static void
+dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node)
+{
+ dmnsn_kD_splay_node *pivot;
+ if (node == node->parent->left) {
+ /* We are a left child */
+ pivot = node->right;
+
+ node->right = node->parent;
+ node->right->parent = node;
+
+ node->right->left = pivot;
+ pivot->parent = node->right;
+
+ node->parent = node->parent->parent;
+ } else {
+ /* We are a right child */
+ pivot = node->left;
+
+ node->left = node->parent;
+ node->left->parent = node;
+
+ node->left->right = pivot;
+ pivot->parent = node->left;
+
+ node->parent = node->parent->parent;
+ }
+}