Skip to content

Instantly share code, notes, and snippets.

@mtao
Last active September 30, 2017 17:21
Show Gist options
  • Save mtao/9482d9df9f2a44e1dfe8b464055de040 to your computer and use it in GitHub Desktop.
Save mtao/9482d9df9f2a44e1dfe8b464055de040 to your computer and use it in GitHub Desktop.
contiguous binary tree implementation someone was curious to see
#ifndef CONTIGUOUS_BINARY_TREE_HPP
#define CONTIGUOUS_BINARY_TREE_HPP
#include <cmath>
#include <vector>
template <typename T>
struct CBinaryTree: public std::vector<T> {
public:
using BaseType = std::vector<T>;
using BaseType::operator[];
using value_type = typename BaseType::value_type;
using BaseType::begin;
using BaseType::end;
struct Node {
public:
Node(CBinaryTree<T>* t, int idx): m_tree(t), m_index(idx) {}
const CBinaryTree<T>& tree() const { return *m_tree; }
int index() const { return m_index; }
value_type& operator()() { return (*m_tree)[m_index]; }
const value_type& operator()() const { return (*m_tree)[m_index]; }
operator bool() const { return m_index < m_tree->size(); }
int depth() const { return std::floor(std::log2(m_index+1)); }
Node left() const { return Node(m_tree,m_tree->left(m_index));}
Node right() const { return Node(m_tree,m_tree->right(m_index));}
Node parent() const { return Node(m_tree,m_tree->parent(m_index));}
private:
CBinaryTree<T>* m_tree;
int m_index;
};
CBinaryTree(int depth): BaseType(std::exp2(depth)-1), m_depth(depth) {}
Node node(int idx=0) { return Node{this,idx}; }
int depth() const { return m_depth; }
#ifdef USE_BITSHIFTS
static int left(int idx) { return (idx<<1)+1; }
static int right(int idx) { return (idx<<1)+2; }
static int parent(int idx) { return (idx-1)<<1; }
#else
static int left(int idx) { return 2*idx+1; }
static int right(int idx) { return 2*idx+2; }
static int parent(int idx) { return (idx-1)/2; }
#endif
private:
int m_depth;
};
#endif//CONTIGUOUS_BINARY_TREE_HPP
#include "contiguous_bin_tree.hpp"
#include <iostream>
using Tree = CBinaryTree<int>;
using Node = Tree::Node;
void traverse(const Node& n) {
if(!n) { return; }
for(int i = 0; i < n.depth(); ++i) {
std::cout << ">";
}
std::cout << n() << std::endl;
traverse(n.left());
traverse(n.right());
};
int main() {
Tree cbt(4);
for(int i = 0; i < cbt.depth(); ++i) {
int base = std::exp2(i)-1;
for(int j = 0; j < std::exp2(i); ++j) {
int idx = base + j;
cbt[idx] = i * 100 + j;
std:: cout << cbt[idx] << " = " << cbt.node(idx)() << std::endl;
}
}
auto n = cbt.node();
traverse(cbt.node());
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment