2 files changed, 49 insertions, 17 deletions

diff --git a/Makefile b/Makefile
index 7112d2f..5a4e524 100644
--- a/Makefile
+++ b/Makefile
@@ -1,17 +1,11 @@
 CC=clang++
 CFLAGS=-pedantic -Wall -ggdb
 VFLAGS=--show-leak-kinds=all --leak-check=full
+OUT=
 
-list: list.cpp
+$(OUT): $(OUT).cpp
 	$(CC) $(CFLAGS) $^ -o $@
 
-.PHONY: memcheck_list
-memcheck_list: list
-	valgrind $(VFLAGS) ./$^;
-
-btree: btree.cpp
-	$(CC) $(CFLAGS) $^ -o $@
-
-.PHONY: memcheck_btree
-memcheck_btree: btree
+.PHONY: memcheck
+memcheck: $(OUT)
 	valgrind $(VFLAGS) ./$^;
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;
 }