1 files changed, 109 insertions, 0 deletions
diff --git a/impls/btree.cpp b/impls/btree.cpp
new file mode 100644
index 0000000..4067aad
--- /dev/null
+++ b/impls/btree.cpp
@@ -0,0 +1,109 @@
+/* btree.cpp
+ * Date: 2021-11-22
+ * Author: Aryadev Chavali
+ */
+
+#include <iostream>
+
+enum Order
+{
+  LT,
+  GT,
+  EQ
+};
+
+template <typename T>
+struct BinaryTree
+{
+  T value;
+  BinaryTree<T> *left, *right;
+  enum Order (*compare)(T, T);
+  BinaryTree(T val, BinaryTree<T> *l, BinaryTree<T> *r, enum Order (*cmp)(T, T))
+  {
+    value   = val;
+    left    = l;
+    right   = r;
+    compare = cmp;
+  }
+
+  ~BinaryTree()
+  {
+    delete left;
+    delete right;
+  }
+};
+
+template <typename T>
+BinaryTree<T> *insert(BinaryTree<T> *tree, T value)
+{
+  BinaryTree<T> **node = &tree;
+  switch (tree->compare(value, tree->value))
+  {
+  case LT:
+    node = &tree->left;
+    break;
+  case EQ:
+  case GT:
+    node = &tree->right;
+    break;
+  }
+  *node = *node ? insert(*node, value)
+                : new BinaryTree<T>(value, nullptr, nullptr, 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;
+}
+
+int main(void)
+{
+  auto cmp = [](int x, int y)
+  {
+    if (x < y)
+      return LT;
+    else if (x > y)
+      return GT;
+    else
+      return EQ;
+  };
+  auto tree = new BinaryTree<int>(5, NULL, NULL, cmp);
+  for (int i = 0; i <= 5; ++i)
+    tree = insert(tree, i * 2);
+
+  leftRotate(&tree);
+  std::cout << tree << std::endl;
+
+  delete tree;
+  return 0;
+}