Binary Search Trees

// bench.cpp: insert and find cost, random vs sorted IDs.
// Build: g++ -std=c++20 -O2 bench.cpp sensor_index.cpp
#include "sensor_index.hpp"
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <numeric>
#include <random>
using Clock = std::chrono::steady_clock;
static double ns_per(Clock::time_point a, Clock::time_point b,
                     std::size_t n) {
    std::chrono::duration<double, std::nano> d = b - a;
    return d.count() / n;
}
int main(int argc, char** argv) {
    if (argc < 2) return 1;
    const std::size_t n = std::strtoul(argv[1], nullptr, 10);
    const bool sorted = argc > 2 && argv[2][0] == 's';
    std::vector<std::uint32_t> ids(n);
    std::iota(ids.begin(), ids.end(), 1000u);  // 1000, 1001...
    std::mt19937 rng(2026);
    if (!sorted) std::shuffle(ids.begin(), ids.end(), rng);
    std::vector<std::uint32_t> probes = ids;  // each ID once,
    std::shuffle(probes.begin(), probes.end(), rng);  // mixed
    stn::SensorIndex idx;
    auto t0 = Clock::now();
    for (std::uint32_t id : ids) idx.insert({id, 0, 1.0, 1});
    auto t1 = Clock::now();
    std::size_t hits = 0;
    for (std::uint32_t id : probes)
        hits += idx.find(id) != nullptr;
    auto t2 = Clock::now();
    std::map<std::uint32_t, stn::Reading> m;  // red-black tree
    for (std::uint32_t id : ids) m[id] = {id, 0, 1.0, 1};
    auto t3 = Clock::now();
    for (std::uint32_t id : probes) hits += m.count(id);
    auto t4 = Clock::now();
    std::printf("%zu %s h=%d bst %.0f %.0f map %.0f %.0f %zu\n",
                n, sorted ? "sorted" : "random", idx.height(),
                ns_per(t0, t1, n), ns_per(t1, t2, n),
                ns_per(t2, t3, n), ns_per(t3, t4, n), hits);
}

#include <cstdint>
#include <cstdio>
#include <memory>
struct Node {
    std::uint32_t id;
    double value;
    std::unique_ptr<Node> left;   // keys smaller than id
    std::unique_ptr<Node> right;  // keys larger than id
};
void insert(std::unique_ptr<Node>& link, std::uint32_t id,
            double value) {
    if (!link)                      // empty spot: key goes here
        link = std::make_unique<Node>(id, value);
    else if (id < link->id)
        insert(link->left, id, value);
    else if (id > link->id)
        insert(link->right, id, value);
    else
        link->value = value;        // same key: overwrite
}
const Node* search(const Node* n, std::uint32_t id,
                   int& steps) {
    while (n != nullptr) {
        ++steps;
        if (id == n->id) return n;
        n = (id < n->id) ? n->left.get() : n->right.get();
    }
    return nullptr;
}
int main() {
    std::unique_ptr<Node> root;
    for (unsigned id : {1004, 1002, 1006, 1001, 1003, 1005})
        insert(root, id, id / 100.0);
    for (unsigned id : {1003, 1007}) {
        int steps = 0;
        const Node* hit = search(root.get(), id, steps);
        std::printf("%u: %s after %d comparisons\n", id,
                    hit ? "found" : "absent", steps);
    }
}

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
struct Node {
    std::uint32_t id;
    std::unique_ptr<Node> left, right;
};
int main(int argc, char** argv) {
    const std::uint32_t n =
        (argc > 1) ? std::strtoul(argv[1], nullptr, 10) : 1000;
    std::unique_ptr<Node> root;
    Node* last = nullptr;        // sorted: each key goes right
    for (std::uint32_t id = 1; id <= n; ++id) {
        auto fresh = std::make_unique<Node>(id);
        Node* raw = fresh.get();
        if (last == nullptr) root = std::move(fresh);
        else last->right = std::move(fresh);
        last = raw;
    }
    std::printf("built a chain of %u nodes; freeing it\n", n);
    return 0;                    // root is destroyed here
}

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
struct Node { std::uint32_t id; std::unique_ptr<Node> left, right; };
void insert(std::unique_ptr<Node>& link, std::uint32_t id) {
    if (!link) link = std::make_unique<Node>(Node{id, nullptr, nullptr});
    else if (id < link->id) insert(link->left, id);
    else if (id > link->id) insert(link->right, id);
}
int main(int, char** argv) {
    const std::uint32_t n = std::strtoul(argv[1], nullptr, 10);
    std::unique_ptr<Node> root;
    for (std::uint32_t id = 1; id <= n; ++id) {
        insert(root, id);
        if (id % 20000 == 0) std::printf("inserted %u\n", id);
    }
    std::printf("insert done\n");
    root.release();   // deliberately leak to skip the recursive destructor
}

#include <cstdint>
#include <cstdio>
#include <memory>
#include <utility>
struct Node {
    std::uint32_t id;
    double value;
    std::unique_ptr<Node> left, right;
};
void insert(std::unique_ptr<Node>& link, std::uint32_t id,
            double value) {
    if (!link) link = std::make_unique<Node>(id, value);
    else if (id < link->id) insert(link->left, id, value);
    else if (id > link->id) insert(link->right, id, value);
    else link->value = value;
}
// Remove id from the subtree owned by 'link'.
bool erase(std::unique_ptr<Node>& link, std::uint32_t id) {
    if (!link) return false;               // not present
    if (id < link->id) return erase(link->left, id);
    if (id > link->id) return erase(link->right, id);
    if (!link->left) {                     // leaf or right only
        link = std::move(link->right);     // old node freed
    } else if (!link->right) {             // left child only
        link = std::move(link->left);
    } else {                               // two children
        Node* succ = link->right.get();    // successor: the
        while (succ->left)                 // leftmost node of
            succ = succ->left.get();       // the right subtree
        link->id = succ->id;
        link->value = succ->value;
        erase(link->right, succ->id);      // succ has no left
    }
    return true;
}
void print(const Node* n) {
    if (!n) return;
    print(n->left.get());
    std::printf(" %u", n->id);
    print(n->right.get());
}
int main() {
    std::unique_ptr<Node> root;
    for (unsigned id : {1004, 1002, 1006, 1001, 1003, 1005})
        insert(root, id, 0.0);
    for (unsigned id : {1001, 1002, 1004, 1009}) {
        bool removed = erase(root, id);
        std::printf("erase %u: %s; root %u; in-order:", id,
                    removed ? "yes" : "no", root->id);
        print(root.get());
        std::printf("\n");
    }
}

#include <cstdint>
#include <cstdio>
#include <initializer_list>
struct Node {
    std::uint32_t id;
    Node* left = nullptr;
    Node* right = nullptr;
};
Node* insert(Node* n, std::uint32_t id) {
    if (n == nullptr) return new Node{id};
    if (id < n->id) n->left = insert(n->left, id);
    else if (id > n->id) n->right = insert(n->right, id);
    return n;
}
Node* erase(Node* n, std::uint32_t k) {
    if (n == nullptr) return nullptr;
    if (k < n->id) { n->left = erase(n->left, k); return n; }
    if (k > n->id) { n->right = erase(n->right, k); return n; }
    if (!n->left && !n->right) { delete n; return nullptr; }
    if (!n->left) return n->right;
    if (!n->right) return n->left;
    Node* s = n->right;
    while (s->left != nullptr) s = s->left;
    n->id = s->id;
    n->right = erase(n->right, s->id);
    return n;
}
void destroy(Node* n) {
    if (n == nullptr) return;           // post-order:
    destroy(n->left);                   // children first,
    destroy(n->right);
    delete n;                           // then the node
}
int main() {
    Node* root = nullptr;
    for (unsigned id : {1004, 1002, 1006, 1001, 1003, 1005})
        root = insert(root, id);
    for (unsigned id : {1001, 1002, 1004})
        root = erase(root, id);
    destroy(root);
    std::puts("done");
}

#include <cstdint>
#include <cstdio>
#include <initializer_list>
struct Node {
    std::uint32_t id;
    Node* left = nullptr;
    Node* right = nullptr;
};
Node* insert(Node* n, std::uint32_t id) {
    if (n == nullptr) return new Node{id};
    if (id < n->id) n->left = insert(n->left, id);
    else if (id > n->id) n->right = insert(n->right, id);
    return n;
}
Node* erase(Node* n, std::uint32_t k) {
    if (n == nullptr) return nullptr;
    if (k < n->id) { n->left = erase(n->left, k); return n; }
    if (k > n->id) { n->right = erase(n->right, k); return n; }
    if (n->left == nullptr || n->right == nullptr) {
        Node* child = n->left ? n->left : n->right;
        delete n;                        // free what you unlink
        return child;
    }
    Node* s = n->right;
    while (s->left != nullptr) s = s->left;
    n->id = s->id;
    n->right = erase(n->right, s->id);
    return n;
}
void destroy(Node* n) {
    if (n == nullptr) return;           // post-order:
    destroy(n->left);                   // children first,
    destroy(n->right);
    delete n;                           // then the node
}
int main() {
    Node* root = nullptr;
    for (unsigned id : {1004, 1002, 1006, 1001, 1003, 1005})
        root = insert(root, id);
    for (unsigned id : {1001, 1004, 1002})
        root = erase(root, id);
    destroy(root);
    std::puts("done");
}

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
struct Node { std::uint32_t id; std::unique_ptr<Node> left, right; };
void insert(std::unique_ptr<Node>& link, std::uint32_t id) {
    if (!link) link = std::make_unique<Node>(Node{id, nullptr, nullptr});
    else if (id < link->id) insert(link->left, id);
    else if (id > link->id) insert(link->right, id);
}
int main(int, char** argv) {
    const std::uint32_t n = std::strtoul(argv[1], nullptr, 10);
    std::unique_ptr<Node> root;
    Node* last = nullptr;
    for (std::uint32_t id = 1; id <= n; ++id) {
        auto f = std::make_unique<Node>(Node{id, nullptr, nullptr});
        Node* raw = f.get();
        if (!last) root = std::move(f); else last->right = std::move(f);
        last = raw;
    }
    insert(root, n + 1);               // one recursive insert, depth n
    std::printf("ok\n");
    root.release();                    // skip recursive destructor
}

#include <cstdint>
#include <cstdio>
#include <initializer_list>
struct Node {
    std::uint32_t id;
    Node* left = nullptr;
    Node* right = nullptr;
};
Node* insert(Node* n, std::uint32_t id) {
    if (n == nullptr) return new Node{id};
    if (id < n->id) n->left = insert(n->left, id);
    else if (id > n->id) n->right = insert(n->right, id);
    return n;
}
Node* erase(Node* n, std::uint32_t k) {
    if (n == nullptr) return nullptr;
    if (k < n->id) { n->left = erase(n->left, k); return n; }
    if (k > n->id) { n->right = erase(n->right, k); return n; }
    if (n->left == nullptr) return n->right;  // splice out
    if (n->right == nullptr) return n->left;
    Node* s = n->right;
    while (s->left != nullptr) s = s->left;
    n->id = s->id;
    n->right = erase(n->right, s->id);
    return n;
}
void destroy(Node* n) {
    if (n == nullptr) return;           // post-order:
    destroy(n->left);                   // children first,
    destroy(n->right);
    delete n;                           // then the node
}
int main() {
    Node* root = nullptr;
    for (unsigned id : {1004, 1002, 1006, 1001, 1003, 1005})
        root = insert(root, id);
    for (unsigned id : {1001, 1004, 1002})
        root = erase(root, id);
    destroy(root);
    std::puts("done");
}

// orders.cpp: adversarial insert orders and their heights
#include "sensor_index.hpp"
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <random>
#include <utility>
using Ids = std::vector<std::uint32_t>;
// Append s[lo, hi) in median-first order.
void median_first(const Ids& s, std::size_t lo, std::size_t hi,
                  Ids& out) {
    if (lo >= hi) return;
    std::size_t mid = lo + (hi - lo) / 2;
    out.push_back(s[mid]);
    median_first(s, lo, mid, out);
    median_first(s, mid + 1, hi, out);
}
int height_of(const Ids& order) {
    stn::SensorIndex idx;
    for (std::uint32_t id : order) idx.insert({id, 0, 0.0, 0});
    return idx.height();
}
int main() {
    const std::size_t n = 1023;
    Ids s(n);
    std::iota(s.begin(), s.end(), 1000u);   // IDs 1000..2022
    std::mt19937 rng(7);
    Ids rev(s.rbegin(), s.rend()), zig, rnd = s, near = s, mf;
    for (std::size_t i = 0, j = n - 1; i <= j; ++i, --j) {
        zig.push_back(s[i]);                // low, high, low...
        if (i != j) zig.push_back(s[j]);
    }
    std::shuffle(rnd.begin(), rnd.end(), rng);
    for (int k = 0; k < 10; ++k)
        std::swap(near[rng() % n], near[rng() % n]);
    median_first(s, 0, n, mf);
    const std::pair<const char*, const Ids*> cases[] = {
        {"sorted", &s}, {"reverse sorted", &rev},
        {"zigzag low/high", &zig}, {"sorted, 10 swaps", &near},
        {"random shuffle", &rnd}, {"median first", &mf}};
    for (const auto& [name, order] : cases)
        std::printf("%-18s height %4d\n", name,
                    height_of(*order));
}

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <memory>
#include <vector>
struct Node {
    std::uint32_t id;
    std::unique_ptr<Node> left, right;
};
void insert(std::unique_ptr<Node>& link, std::uint32_t id) {
    if (!link) link = std::make_unique<Node>(id);
    else if (id < link->id) insert(link->left, id);
    else if (id > link->id) insert(link->right, id);
}
void in_order(const Node* n) {          // left, node, right
    if (n == nullptr) return;
    in_order(n->left.get());
    std::printf("%u ", n->id);
    in_order(n->right.get());
}
int height(const Node* n) {         // levels: empty 0, leaf 1
    if (n == nullptr) return 0;
    return 1 + std::max(height(n->left.get()),
                        height(n->right.get()));
}
void show(const Node* n, int depth) {  // root at left margin
    if (n == nullptr) return;
    show(n->right.get(), depth + 1);
    std::printf("%*s%u\n", 6 * depth, "", n->id);
    show(n->left.get(), depth + 1);
}
int main() {
    const std::vector<std::vector<std::uint32_t>> orders = {
        {1003, 1005, 1001, 1004, 1002, 1006},
        {1006, 1001, 1005, 1002, 1004, 1003},
        {1002, 1001, 1005, 1003, 1004, 1006}};
    for (const auto& order : orders) {
        std::unique_ptr<Node> root;
        for (std::uint32_t id : order) insert(root, id);
        std::printf("in-order: ");
        in_order(root.get());
        std::printf("\nheight: %d\n", height(root.get()));
        show(root.get(), 0);
    }
}

#include <cstdint>
#include <cstdio>
#include <initializer_list>
struct Node {
    std::uint32_t id;
    Node* left = nullptr;
    Node* right = nullptr;
};
Node* insert(Node* n, std::uint32_t id) {
    if (n == nullptr) return new Node{id};
    if (id < n->id) n->left = insert(n->left, id);
    else if (id > n->id) n->right = insert(n->right, id);
    return n;
}
Node* erase(Node* n, std::uint32_t k) {
    if (n == nullptr) return nullptr;
    if (k < n->id) { n->left = erase(n->left, k); return n; }
    if (k > n->id) { n->right = erase(n->right, k); return n; }
    if (n->left == nullptr || n->right == nullptr) {
        Node* child = n->left ? n->left : n->right;
        delete n;                        // free what you unlink
        return child;
    }
    Node* s = n->right;
    while (s->left != nullptr) s = s->left;
    n->id = s->id;
    n->right = erase(n->right, s->id);
    return n;
}
void destroy(Node* n) {
    if (n == nullptr) return;
    delete n;                           // WRONG: node first
    destroy(n->left);
    destroy(n->right);
}
int main() {
    Node* root = nullptr;
    for (unsigned id : {1004, 1002, 1006, 1001, 1003, 1005})
        root = insert(root, id);
    for (unsigned id : {1001, 1004, 1002})
        root = erase(root, id);
    destroy(root);
    std::puts("done");
}

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <numeric>
#include <random>
#include <vector>
struct Node { std::uint32_t id; std::unique_ptr<Node> left, right; };
void insert(std::unique_ptr<Node>& link, std::uint32_t id) {
    if (!link) link = std::make_unique<Node>(Node{id, nullptr, nullptr});
    else if (id < link->id) insert(link->left, id);
    else if (id > link->id) insert(link->right, id);
}
int main(int, char** argv) {
    const std::uint32_t n = std::strtoul(argv[1], nullptr, 10);
    std::vector<std::uint32_t> ids(n);
    std::iota(ids.begin(), ids.end(), 1u);
    std::mt19937 rng(1);
    std::shuffle(ids.begin(), ids.end(), rng);
    std::unique_ptr<Node> root;
    for (auto id : ids) insert(root, id);
    std::printf("insert done\n");
}

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
struct Node { std::uint32_t id; Node* left = nullptr; Node* right = nullptr; };
int height(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + std::max(height(n->left), height(n->right));
}
int main(int, char** argv) {
    const std::uint32_t n = std::strtoul(argv[1], nullptr, 10);
    Node* root = new Node{1};
    Node* last = root;
    for (std::uint32_t id = 2; id <= n; ++id) { last->right = new Node{id}; last = last->right; }
    std::printf("height %d\n", height(root));
    while (root) { Node* next = root->right; delete root; root = next; }
}

// sensor_index.hpp: sensor ID -> latest reading, as a BST
#pragma once
#include <cstddef>
#include <cstdint>
#include <memory>
#include <vector>
namespace stn {
struct Reading {
    std::uint32_t sensor_id;
    std::int64_t time_s;
    double value;
    std::uint8_t flags;
};
class SensorIndex {
public:
    SensorIndex() = default;
    ~SensorIndex();                   // frees without recursion
    SensorIndex(const SensorIndex&) = delete;
    SensorIndex& operator=(const SensorIndex&) = delete;
    SensorIndex(SensorIndex&& other) noexcept;
    SensorIndex& operator=(SensorIndex&& other) noexcept;
    bool insert(const Reading& r);    // true if the ID was new
    const Reading* find(std::uint32_t id) const;  // or nullptr
    bool erase(std::uint32_t id);     // true if one was removed
    void clear();
    std::size_t size() const { return size_; }
    int height() const;               // levels; empty tree is 0
    std::vector<std::uint32_t> ids_in_order() const;
private:
    struct Node {
        Reading r;                    // key is r.sensor_id
        std::unique_ptr<Node> left, right;  // owns its children
    };
    std::unique_ptr<Node> root_;      // owns the whole tree
    std::size_t size_ = 0;
};
}  // namespace stn

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <memory>
#include <vector>
struct Node {
    std::uint32_t id;
    std::unique_ptr<Node> left, right;
};
void insert(std::unique_ptr<Node>& link, std::uint32_t id) {
    if (!link) link = std::make_unique<Node>(id);
    else if (id < link->id) insert(link->left, id);
    else if (id > link->id) insert(link->right, id);
}
void in_order(const Node* n) {          // left, node, right
    if (n == nullptr) return;
    in_order(n->left.get());
    std::printf("%u ", n->id);
    in_order(n->right.get());
}
int height(const Node* n) {         // levels: empty 0, leaf 1
    if (n == nullptr) return 0;
    return 1 + std::max(height(n->left.get()),
                        height(n->right.get()));
}
void show(const Node* n, int depth) {  // root at left margin
    if (n == nullptr) return;
    show(n->right.get(), depth + 1);
    std::printf("%*s%u\n", 6 * depth, "", n->id);
    show(n->left.get(), depth + 1);
}
int main() {
    const std::vector<std::vector<std::uint32_t>> orders = {
        {1004, 1002, 1006, 1001, 1003, 1005},
        {1001, 1002, 1003, 1004, 1005, 1006}};
    for (const auto& order : orders) {
        std::unique_ptr<Node> root;
        for (std::uint32_t id : order) insert(root, id);
        std::printf("in-order: ");
        in_order(root.get());
        std::printf("\nheight: %d\n", height(root.get()));
        show(root.get(), 0);
    }
}