feat: initial release

1 files changed, 189 insertions, 0 deletions

diff --git a/bst.cc b/bst.cc
new file mode 100644
index 0000000..e66756f
--- /dev/null
+++ b/bst.cc
@@ -0,0 +1,189 @@
+#include <cstddef>
+#include <iostream>
+#include <memory>
+#include <optional>
+
+template <typename T> class bst {
+public:
+  using size_type = std::size_t;
+
+private:
+  T _key;
+  std::optional<std::shared_ptr<bst>> _left;
+  std::optional<std::shared_ptr<bst>> _right;
+
+public:
+  bst(T key) : _key(key) {}
+
+  auto key() -> T { return this->_key; }
+  auto key(T key) -> void { this->_key = key; }
+
+  auto left() -> std::optional<T> { return this->_left; }
+  auto left(T left) -> void { this->_left = left; }
+
+  auto right() -> std::optional<T> { return this->_right; }
+  auto right(T right) -> void { this->_right = right; }
+
+  auto insert(T key) -> void {
+    // A BST is structured in a way that values larger than the root node sit
+    // right of the node, while values smaller sit left of it.
+    //
+    // If the key is greater than than this node's key, it will sit to the right
+    // of it.
+    if (key > this->_key) {
+      // If this node already has a right value, we must tack it onto the end of
+      // that node ...
+      if (this->_right.has_value()) {
+        std::cout << "inserting as right: " << key << "\n";
+
+        // or keep trying until an empty branch is found.
+        this->_right.value()->insert(key);
+      } else {
+        // If this branch was hit, that must mean that an empty right branch was
+        // found, so we set it.
+        this->_right = std::make_shared<bst<T>>(bst(key));
+
+        std::cout << "set as right: " << key << "\n";
+      }
+    } else {
+      // This is the same operation is above, but for values smaller than the
+      // current BST node.
+      if (this->_left.has_value()) {
+        std::cout << "inserting as left: " << key << "\n";
+
+        this->_left.value()->insert(key);
+      } else {
+        this->_left = std::make_shared<bst<T>>(bst(key));
+
+        std::cout << "set as left: " << key << "\n";
+      }
+    }
+  }
+
+  auto size() -> bst::size_type {
+    return
+        // If the left value of the current node has a value, add one to
+        // the accumulator (the +1 below), and continue down the branch
+        (this->_left.has_value() ? this->_left.value()->size() : 0) +
+        // The same as above, but for the right branch
+        (this->_right.has_value() ? this->_right.value()->size() : 0) +
+        // Additionally account for the root node itself
+        1;
+  }
+
+  auto depth() -> bst::size_type {
+    // Account for the root node, but also serve as the accumulator for the
+    // below `depth` calls, similar as to the above `size` function
+    return 1 +
+           std::max(this->_left.has_value() ? this->_left.value()->depth() : 0,
+                    this->_right.has_value() ? this->_right.value()->depth()
+                                             : 0);
+  }
+
+  auto minimum() -> T {
+    // Start with the root key as the base minimum, since the left branch may be
+    // empty
+    T minimum = this->_key;
+
+    // If the left branch has a value, and the value is smaller than the root
+    // node, consider it as a minimum
+    if (this->_left.has_value() && this->_key > this->_left.value()->key()) {
+      // Attempt to obtain the valid left branch value's left branch, otherwise,
+      // minimum will return the top-level minimum of the left branch
+      minimum = this->_left.value()->minimum();
+    }
+
+    return minimum;
+  }
+
+  auto maximum() -> T {
+    // Identical to the `minimum` implementation, but considers the right-hand
+    // branch
+    T maximum = this->_key;
+
+    if (this->_right.has_value() && this->_key < this->_right.value()->key()) {
+      maximum = this->_right.value()->maximum();
+    }
+
+    return maximum;
+  }
+
+  auto _remove(std::optional<std::shared_ptr<bst>> bst,
+               T key) -> std::optional<std::shared_ptr<class bst>> {
+    // If the current BST being evaluated has no value, it could not possibly be
+    // considering for child removal
+    if (!bst.has_value()) {
+      return std::nullopt;
+    }
+
+    // If the current BST's key is smaller than the target key, it must be on
+    // the right-hand side, this additionally means that it is not the target
+    // value
+    if (bst.value()->_key < key) {
+      bst.value()->_right = this->_remove(bst.value()->_right, key);
+
+      return bst;
+    } else if (bst.value()->_key > key) {
+      bst.value()->_left = this->_remove(bst.value()->_left, key);
+
+      return bst;
+    }
+
+    // At this point, the BST value has been found if available through a series
+    // of greater than, less than evaluations
+
+    if (!bst.value()->_left.has_value()) {
+      auto temporary_bst = bst.value()->_right;
+
+      bst.value().reset();
+
+      return temporary_bst;
+    } else if (!bst.value()->_right.has_value()) {
+      auto temporary_bst = bst.value()->_left;
+
+      bst.value().reset();
+
+      return temporary_bst;
+    }
+
+    auto next_parent = bst.value()->_right;
+    auto next = bst.value()->_right;
+
+    while (next.value()->_left.has_value()) {
+      next_parent = next;
+      next = next.value()->_left;
+    }
+
+    next_parent.value()->_left = next.value()->_right;
+    bst.value()->_key = next.value()->_key;
+
+    next.value().reset();
+
+    return bst;
+  }
+
+  auto remove(T key) -> void {
+    // `remove` is easier with recursion, so its wrapped
+    this->_remove(std::make_shared<bst<T>>(*this), key);
+  }
+};
+
+auto main() -> int {
+  bst<int> bst(2);
+
+  bst.insert(3);
+  bst.insert(4);
+  bst.insert(5);
+  bst.insert(1);
+
+  std::cout << "size: " << bst.size() << '\n';
+  std::cout << "depth: " << bst.depth() << '\n';
+  std::cout << "minimum: " << bst.minimum() << '\n';
+  std::cout << "maximum: " << bst.maximum() << '\n';
+
+  bst.remove(5);
+
+  std::cout << "size: " << bst.size() << '\n';
+
+  return 0;
+}