Skip to content

Instantly share code, notes, and snippets.

@cjxgm

cjxgm/avl.cc

Last active March 3, 2017 07:56
Show Gist options
  • Save cjxgm/71d9c7fbc7c172579d78fcc3106cdcfc to your computer and use it in GitHub Desktop.
Save cjxgm/71d9c7fbc7c172579d78fcc3106cdcfc to your computer and use it in GitHub Desktop.
Download ZIP
AVL Tree Implementation with 3+4 Reshaping
Raw
avl.cc
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#ifdef _NDEBUG
# define DDD(X...)
#else
# define DDD(X...) X
#endif
template <class T>
struct NewAllocator
{
template <class U>
using rebind = NewAllocator<U>;
using value_type = T;
using pointer = value_type*;
template <class ...Ts>
pointer alloc(Ts &&... args)
{
return new T{std::forward<Ts>(args)...};
}
};
template <class T, class Allocator=NewAllocator<void>>
struct AvlTree
{
using value_type = T;
using depth_type = int;
using depth_diff = depth_type;
struct Node;
using allocator = typename Allocator::template rebind<Node>;
using node_pointer = typename allocator::pointer;
using node_type = typename allocator::value_type;
struct Node
{
Node(value_type value)
: value{std::move(value)}
, depth{1}
, childs{}
{}
value_type value;
depth_type depth;
node_pointer childs[2];
};
void insert(value_type value)
{
auto node = ator.alloc(std::move(value));
insert(root, node);
}
void inspect()
{
print(root, 0);
}
value_type & root_value() const
{
return root->value;
}
private:
allocator ator;
node_pointer root{};
static void insert(node_pointer & root, node_pointer const& node)
{
if (root) {
auto cs = root->childs;
auto& child = (node->value < root->value ? cs[0] : cs[1]);
insert(child, node);
update_depth(root);
if (std::abs(balance_factor(root)) == 2) rebalance(root);
} else {
root = node;
}
}
static void update_depth(node_pointer & root)
{
auto cs = root->childs;
root->depth = std::max(depth_of(cs[0]), depth_of(cs[1])) + 1;
}
static depth_type depth_of(node_pointer const& root)
{
return (root ? root->depth : depth_type{});
}
static depth_diff balance_factor(node_pointer const& root)
{
auto cs = root->childs;
return depth_of(cs[0]) - depth_of(cs[1]);
}
static void rebalance(node_pointer & root)
{
DDD(std::cerr << "Unbalanced\n");
DDD(print(root, 2));
switch (balance_factor(root)) {
case +2: {
auto& z = root;
auto& child = z->childs[0];
switch (balance_factor(child)) {
case +1: {
auto& y = child;
auto& x = y->childs[0];
auto& a = x->childs[0];
auto& b = x->childs[1];
auto& c = y->childs[1];
auto& d = z->childs[1];
root = reshape(x, y, z, a, b, c, d);
} break;
case -1: {
auto& x = child;
auto& y = x->childs[1];
auto& a = x->childs[0];
auto& b = y->childs[0];
auto& c = y->childs[1];
auto& d = z->childs[1];
root = reshape(x, y, z, a, b, c, d);
} break;
default: std::abort();
}
} break;
case -2: {
auto& x = root;
auto& child = x->childs[1];
switch (balance_factor(child)) {
case +1: {
auto& z = child;
auto& y = z->childs[0];
auto& a = x->childs[0];
auto& b = y->childs[0];
auto& c = y->childs[1];
auto& d = z->childs[1];
root = reshape(x, y, z, a, b, c, d);
} break;
case -1: {
auto& y = child;
auto& z = y->childs[1];
auto& a = x->childs[0];
auto& d = y->childs[0];
auto& b = z->childs[0];
auto& c = z->childs[1];
root = reshape(x, y, z, a, b, c, d);
} break;
default: std::abort();
}
} break;
default: std::abort();
}
DDD(std::cerr << "Balanced\n");
DDD(print(root, 2));
DDD(std::cerr << "\n");
}
static node_pointer reshape(
node_pointer x,
node_pointer y,
node_pointer z,
node_pointer a,
node_pointer b,
node_pointer c,
node_pointer d)
{
x->childs[0] = a;
x->childs[1] = b;
update_depth(x);
z->childs[0] = c;
z->childs[1] = d;
update_depth(z);
y->childs[0] = x;
y->childs[1] = z;
update_depth(y);
return y;
}
static void print(node_pointer const& root, int indent)
{
if (root) {
std::cerr << std::string(indent, ' ') << root->value << " (" << root->depth << "|" << balance_factor(root) << ")\n";
auto shift = std::to_string(root->value).size() + 1;
print(root->childs[0], indent+shift);
print(root->childs[1], indent+shift);
} else {
std::cerr << std::string(indent, ' ') << "* (0|0)\n";
}
}
};
int main()
{
int n;
std::cin >> n;
AvlTree<int> tree;
while (n--) {
int x;
std::cin >> x;
tree.insert(x);
}
DDD(tree.inspect());
std::cout << tree.root_value() << '\n';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment