aboutsummaryrefslogtreecommitdiff
path: root/btree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'btree.cpp')
-rw-r--r--btree.cpp52
1 files changed, 45 insertions, 7 deletions
diff --git a/btree.cpp b/btree.cpp
index 741c8f7..3319aea 100644
--- a/btree.cpp
+++ b/btree.cpp
@@ -45,13 +45,51 @@ BinaryTree<T> *insert(BinaryTree<T> *tree, T value)
*node = insert(*node, value);
return tree;
}
- *node = new BinaryTree<T>;
- (*node)->value = value;
- (*node)->left = (*node)->right = nullptr;
- (*node)->compare = tree->compare;
+ *node = new BinaryTree<T>;
+ (*node)->value = value;
+ (*node)->left = nullptr;
+ (*node)->right = nullptr;
+ (*node)->compare = tree->compare;
return tree;
}
+template <typename T>
+void rightRotate(BinaryTree<T> **tree)
+{
+ auto left = *tree->left;
+ *tree->left = left->right;
+ left->right = *tree;
+ *tree = left;
+}
+
+template <typename T>
+void leftRotate(BinaryTree<T> **tree)
+{
+ auto right = (*tree)->right;
+ (*tree)->right = right->left;
+ right->left = *tree;
+ *tree = right;
+}
+
+template <typename T>
+std::ostream &operator<<(std::ostream &ostream, const BinaryTree<T> *btree)
+{
+ if (!btree)
+ return ostream;
+ ostream << btree->value << "(";
+ if (btree->left)
+ ostream << btree->left;
+ if (btree->left && btree->right)
+ ostream << ", ";
+ if (btree->right)
+ ostream << btree->right;
+ ostream << ")";
+ return ostream;
+}
+
+void test()
+{}
+
int main(void)
{
auto tree = new BinaryTree<int>;
@@ -69,9 +107,9 @@ int main(void)
for (int i = 0; i <= 5; ++i)
tree = insert(tree, i * 2);
- std::cout << tree->left->value << ", "
- << tree->value << ", "
- << tree->right->value << std::endl;
+ leftRotate(&tree);
+ std::cout << tree << std::endl;
+
delete tree;
return 0;
}