Implementations
C++
#include <cstddef>
#include <iterator>
#include <memory>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
template <typename T> class BST {
private:
struct Node {
T val;
std::unique_ptr<Node> left, right; // uptr = nullptr on a default int,
// impl is overloaded to support that
};
static_assert(std::is_aggregate_v<Node>); // NOTE: i missed the _v earlier
// you either have it or use the ::value
std::unique_ptr<Node> root_;
std::size_t size_ = 0; // NOTE: rem this, this isn't java
// using Node* wherever an ownership transfer is not needed
bool erase(std::unique_ptr<Node> &node, const T &value) {
Node *cur = node.get();
if (!cur)
return false;
if (value < cur->val) {
return erase(cur->left, value);
}
if (value > cur->val) {
return erase(cur->right, value);
}
size_--; // can delete now and no more rec
// one child cases
if (!cur->left) {
node = std::move(
cur->right); // note that cur is Node* but right is still a uptr
return true;
}
if (!cur->right) {
node = std::move(cur->left);
return true;
}
// two child case
// need to find inorder successor aka next larger than current val in
// the subtree aka in right subtree go left till you can
std::unique_ptr<Node> *succ = &cur->right; // -> has higher precedence
while ((*succ)->left) {
succ = &((*succ)->left);
}
// note that this inorder successor will ONLY have a right child ( if
// any ) - by defn
//
// WARN: now we swap the values on the nodes instead of
// moving the uptrs themselves, this'll be expensive if copy assignment
// on T is expensive and we don't have a move, this below would then
// copy instead it also would just plain fail compile if no copy or move
// exists
cur->val = std::move((*succ)->val);
*succ = std::move((*succ)->right);
// uptr move = destroy succ, then succ
// takes ownership of the right subtree
return true;
}
public:
std::size_t size() const { return size_; }
bool erase(const T &value) { return erase(root_, value); }
bool insert(const T &value) {
// the idea is simple you go left and right ( checking if eq and ret
// false in case that happens ) and put in the value at the first null
// node
// NOTE: I used auto here earlier but that doesn't quite work
std::unique_ptr<Node> *cur = &root_;
// NOTE: ptr to the unique ptr, no ctor is called above
// NOTE: cheatsheet
// cur is pointer to the uptr
// *cur is the uptr
// (*cur).get() or cur -> get() returns a ptr to the data held
// unique ptr implements a bool overload so can do this
// *cur is the uptr root one first itr, on later itrs it becomes the
// uptrs to the left and right of those so this'll call the bool
// overload on those uptrs which in turn check if the data exists akak
// uptr is not null
while (*cur) {
auto &cur_val = (*cur)->val;
if (value == cur_val) {
return false;
}
if (value < cur_val) {
cur = &((*cur)->left);
} else {
cur = &((*cur)->right);
}
}
// INFO: in fact you can use raw ptrs for traversal as well
// and onlyy do the following line where OWNERSHIP needs to change
// the syntax allow to give args to the ctor directly
// so make_unique<Node>(value) is same as make_unique<Node>(Node(value))
// so it CANNOT inver the T from the value as at all, you need to give
*cur = std::make_unique<Node>(value); // passes value to do agg init
size_++;
return true;
}
// INFO: use uniq ptrs only when you are modifying the tree as that's when u
// alloc or dealloc - for cases like iterators or contains here which don't
// modify anything. you can use raw pointers and mark them const as well
// while at it
bool contains(const T &value) const {
const Node *cur = root_.get();
while (cur) {
auto &cur_val = cur->val;
if (value == cur_val)
return true;
if (value < cur_val)
cur = cur->left.get();
else
cur = cur->right.get();
}
return false;
}
// NOTE: this makes clear so so so much easier to write
// you also don't need a dtor to call this clear
void clear() {
root_.reset();
size_ = 0;
}
// iterator, in a traversal either you have parent or keep a stack of
// parents so if I have no left or right, I go to parent it that's exhaused
// then another parent up the stack
// meant to be public
// uses raw ptrs but that's expected as iterators can be dangling and that's
// standard in cpp
class iterator {
private:
std::vector<Node *> stack_;
// WARN: private mem funcs don't need an _ at the end that I've been
// adding so far - that's an incorrect convention
void push_left(Node *cur) {
// go all the way bottom of a cur node
while (cur) {
stack_.push_back(cur);
cur = cur->left.get();
}
}
public:
// NEEDED for ranges
// these basically make it so that it has concept that ranges uses
// instead of SOME class that HAPPENS to have begin end etc
// there is no general "iterable" trait in cpp
using value_type = T;
using difference_type = std::ptrdiff_t;
using reference = T &;
using pointer = T *;
using iterator_concept = std::forward_iterator_tag;
using iterator_category = std::forward_iterator_tag;
// NEEDED for ranges
iterator() = default;
explicit iterator(Node *root) {
// this time instead of uptrs, I have another copy of the pointer
push_left(root);
}
// INFO: note the & and *, you do this as you want to raw object
// it is const because it you modify it via this it breaks the tre
T &operator*() const { return stack_.back()->val; }
// rem that * works on a pointer
T *operator->() const { return &(stack_.back()->val); }
// &iterator to support ++semantics like ++++++it
iterator &operator++() {
// stack contains all the MAX lefts
Node *cur = stack_.back();
stack_.pop_back();
// I reached cur, on the next stack pop I want the leftmost from
// this
if (cur->right) {
push_left(cur->right.get());
// INFO: -> and . have same prec and
// work left to right
}
return *this; // NOW retunr the next left on stack calls the func
// above
}
// WARN:so when using a postfix iterator, it'll return a copy
// the copy ctor will create a copy of the vector
// this is why for iterators and in general USE PREFIX
// cpp uses this dummy int do distinguish prefix from postfix
iterator operator++(int) {
// WARN: you need to ret the old value here
auto old = *this;
++(*this);
return old;
}
bool operator==(const iterator &other) const {
// NOTE: this op1 == op2 is a check I often forget and look for xor
// and what not instead
return (stack_.empty() == other.stack_.empty()) &&
(stack_.empty() || stack_.back() == other.stack_.back());
}
bool operator!=(const iterator &other) const {
return !(*this == other);
}
};
iterator begin() { return iterator(root_.get()); }
iterator end() {
// NOTE: how things move to being end()
// when you do the last pop the stacks become empty
// this default ctor too will make the stack empty
// this is why you need to = default the default ctor since we have
// another one because of which it won't be defaulted
return iterator();
}
};
// INFO: you cannot check for a generic T instead of the class
// can only do specialisations
static_assert(std::ranges::range<BST<int>>);
int main() {
BST<int> bt;
bt.insert(4);
auto a = bt.begin();
*a; // NEEDED this for lsp to work
}Java
import java.util.NoSuchElementException;
import java.util.Iterator;
import java.util.ArrayDeque;
// ? super T = some class parent to T
// T is something that can be compared to another T or something super to T
final class BST<T extends Comparable<? super T>> implements Iterable<T> {
private static class Node<T> {
T value;
Node<T> left;
Node<T> right;
// rem that classes are init to null
Node(T value) {
this.value = value;
}
}
private Node<T> root;
private int size;
public int size() {
return size;
}
public boolean add(T value) {
if (root == null) {
root = new Node<T>(value);
size++;
return true;
}
var cur = root;
Node<T> par = null;
// INFO: rem that if you are only null you are not
// on a pointer like cpp, you MUST stop before null
while (cur != null) {
var comp = value.compareTo(cur.value);
if (comp == 0) {
return false;
}
par = cur;
cur = comp < 0 ? cur.left : cur.right;
}
// par CANNOT be null at this stage
var node = new Node<>(value);
if (value.compareTo(par.value) < 0) {
par.left = node;
} else {
par.right = node;
}
size++;
return true;
}
public boolean remove(T value) {
// first find where to remove
var cur = root;
Node<T> par = null;
while (cur != null) {
var comp = value.compareTo(cur.value);
if (comp == 0)
break;
par = cur;
cur = comp < 0 ? cur.left : cur.right;
}
if (cur == null)
return false; // not found
size--;
// in java doing the two child first is easier
if (cur.left != null && cur.right != null) {
var succPar = cur;
var succ = cur.right; // go right sub then max left
while (succ.left != null) {
succPar = succ;
succ = succ.left;
}
// INFO: I keep on missing that a local assignment
// changes nothing, it changes the local pointer
// but when you do, it changes the actual mem
// to keep cur.left same we use the same just change the
// value - similar to cpp impl
cur.value = succ.value;
// we work with these new set of nodes
// in case it's 1 child case we use the original cur, par pair
par = succPar;
cur = succ;
}
// find the NEXT of succ, there's only one
var next = cur.left != null ? cur.left : cur.right;
// attach in the direction of current
if (par == null) {
// this only happens when root is removed and 0/1 child on root
root = next;
} else if (par.left == cur) {
par.left = next;
} else {
par.right = next;
}
return true;
}
public boolean contains(T value) {
var cur = root;
while (cur != null) {
var cmp = value.compareTo(cur.value);
if (cmp == 0) {
return true;
}
cur = cmp < 0 ? cur.left : cur.right;
}
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
// NOTE: you can only use <> on right side
private ArrayDeque<Node<T>> deque = new ArrayDeque<>();
private void pushLeft(Node<T> node) {
while (node != null) {
deque.push(node);
node = node.left;
}
}
{
// ctor in this case
pushLeft(root);
}
@Override
public boolean hasNext() {
return !deque.isEmpty();
}
@Override
public T next() {
if (!hasNext())
throw new NoSuchElementException();
var ret = deque.pop();
if (ret.right != null) {
pushLeft(ret.right);
}
return ret.value;
}
};
}
}Notes
unbalanced
- use the pointer impl as unbalaned trees bad not complete tree so using arrays like segtree is a lot of data wastage
lang
auto*andautois just for checks. You can use either except first will throw if rhs is not a pointer.- templates, as far as clang is concerned, are not checked for if you don’t use them. And even then the functions that aren’t used are not in the final class in the compiled code. So you need this small int main hack.
the → overload
When you do →, it checks if the object under it is a class object or a pointer. In case it’s a class it’ll call the operator→() overload.
Now with unique ptrs, this gets a bit tricky.
uptr<data> root;
auto* cur = &root; // ptr to uptr
*cur is the uptr
cur -> sees that cur is a ptr and exposes the uptr's methods
(*cur) -> val sees that *cur is an object and uses the overloaded on uptr which gives u
a reference to the actual val field inside of the data
similarly **cur gives you the reference to the nodeaggregates
if no private members or ctors or virtual stuff a struct or class becomes an aggregate
a class can be an agg as well
No ctors are called for aggregates. Node(a,b,c) or Node{a,b,c} assign the values in order
An agg init is basically same as {.val = value} way