Increasing data structure without wasting memory
I have a class Tree
that I would like to extend into more specialized data structures like Order_tree
and Interval_tree
. These additions require additions to Node
, such as size information and minor changes in some algorithms.
I would like to know the best way to implement additions in C ++ in terms of performance, readability, and maintainability. Trees should not be used polymorphically. So far, I've tried to publicly inherit Tree
and then overload the base methods. (I apologize for being new to object oriented programming)
template <typename T>
class Tree {
protected:
enum class Color : char {BLACK = 0, RED = 1};
struct Node {
T key;
Node *parent, *left, *right;
Color color;
Node() : color{Color::BLACK} {} // sentinel construction
Node(T val, Color col = Color::RED) : key{val}, parent{nil}, left{nil}, right{nil}, color{col} {}
};
using NP = typename Tree::Node*;
NP root {nil};
// nil sentinel
static NP nil;
// core utility algorithms...
};
template <typename T>
typename Tree<T>::NP Tree<T>::nil {new Node{}};
Order tree
template <typename T>
class Order_tree : public Tree<T> {
using Color = typename Tree<T>::Color;
using Tree<T>::Tree; // inherit constructors
struct Order_node {
T key;
Order_node *parent, *left, *right;
size_t size; // # of descendent nodes including itself = left->size + right->size + 1
Color color;
Order_node() : size{0}, color{Color::BLACK} {} // sentinel construction
Order_node(T val, Color col = Color::RED) : key{val}, parent{nil}, left{nil}, right{nil}, size{1}, color{col} {}
};
using NP = typename Order_tree::Order_node*;
NP root {nil};
static NP nil;
// overloading on only the methods that need changing
};
template <typename T>
typename Order_tree<T>::NP Order_tree<T>::nil {new Order_node{}};
However, this does not behave correctly as I now have 2 roots and 2 nils, with all base methods working with base root and Tree<T>::NP
and not Order_tree::NP
, so the size attribute Order_node
cannot be used.
One way is to copy the code, which is very irreplaceable. Another way I believe is to pattern Tree on T as well as NP, so that Order_tree
is an alias using Order_tree = Tree<Order_node>
and specializes tree to node.
source to share
After some experimentation, I found the best way to achieve what I want:
- tree pattern on Node type
- make nil a static element of every Node type
- move some private methods that run on nodes without relying on root to be normal functions configured on Node
- execute functions that can be changed by virtual
- Increase the tree by publicly inheriting from it and overriding the necessary virtual functions
- use base Tree root (contain no data in derived class)
How it looks now:
tree.h
namespace sal {
// utilities with no dependence on root, outside of class now
template <typename Node>
Node* tree_find(Node* start, typename Node::key_type key) {
while (start != Node::nil && start->key != key) {
if (key < start->key) start = start->left;
else start = start->right;
}
return start;
}
// more of them...
template <typename Node>
class Tree {
protected:
using NP = Node*;
using T = typename Node::key_type;
// nil is static member of each Node type now
NP root {Node::nil};
// virtual methods that could be changed by augmentation
virtual void rotate_left(NP node);
virtual void rotate_right(NP node);
virtual void tree_insert(NP start, NP node);
virtual void rb_delete(NP node);
// non-virtual methods that are never overridden
void rb_insert_fixup(NP node);
void rb_delete_fixup(NP successor);
void rb_insert(NP node); // just a call to tree_insert and rb_insert_fixup
void transplant(NP old, NP moved);
public:
virtual ~Tree(); // does all the clean up so its derived classes don't have to
// interface...
};
template <typename T>
struct Basic_node {
static Basic_node* nil;
using key_type = T;
T key;
Basic_node *parent, *left, *right;
Color color;
Basic_node() : color{Color::BLACK} {} // sentinel construction
Basic_node(T val) : key{val}, parent{nil}, left{nil}, right{nil}, color{Color::RED} {}
};
template <typename T>
using Basic_tree = Tree<Basic_node<T>>;
template <typename T>
Basic_node<T>* Basic_node<T>::nil {new Basic_node{}};
}
order_tree.h
#include "tree.h"
namespace sal {
template <typename Node>
class Order_augment : public Tree<Node> {
using NP = Node*;
using T = typename Node::key_type;
using Tree<Node>::root;
// no need to redefine shared core functions
using Tree<Node>::rb_insert;
using Tree<Node>::transplant;
using Tree<Node>::rb_insert_fixup;
using Tree<Node>::rb_delete_fixup;
// order statistics operations
NP os_select(NP start, size_t rank) const;
size_t os_rank(NP node) const;
// modification of rb operations to maintain augmentation
virtual void tree_insert(NP start, NP node) override;
virtual void rb_delete(NP node) override;
virtual void rotate_left(NP node) override;
virtual void rotate_right(NP node) override;
public:
// augmented interface
};
template <typename T>
struct Order_node {
static Order_node* nil;
using key_type = T;
T key;
Order_node *parent, *left, *right;
size_t size; // # of descendent nodes including itself = left->size + right->size + 1
Color color;
Order_node() : size{0}, color{Color::BLACK} {} // sentinel construction
Order_node(T val) : key{val}, parent{nil}, left{nil}, right{nil}, size{1}, color{Color::RED} {}
};
template <typename T>
Order_node<T>* Order_node<T>::nil {new Order_node{}};
template <typename T>
using Order_tree = Order_augment<Order_node<T>>;
}
As a result, the size of the file that stores the extended data structures is now about 1/3, and duplicate code is completely removed! This means that any changes to improve the core methods can only be localized in tree.h, and its effect will be felt in all added trees.
source to share
If you are really interested in having a "common tree of all trees", it seems that the problem is not with the tree, but with Node. You need special cases of nodes, so why not generalize them? For example:
template <typename T>
class Tree {
protected:
struct BaseNode {
//all code you really can generalize here
};
struct Node : public BaseNode {
//You need Node here only if you want your base Tree class to be ready to use.
//If you want to use only its derives such as Order_tree,
//you create special nodes kinds only there
};
// core utility algorithms...
BaseNode * root; //Only one root node, there is no need in duplication!
//You can instantiate it as root = new OrderTreeNode or root = new SpecialTreeNode in any derives.
};
However, the cost for calls to virtual Node functions is quite high. Therefore, you need to be clear: you need generalization, not code duplication, or you need execution.
source to share