Усиление структуры данных без потери памяти

Question

У меня есть класс Tree, который я хотел бы расширить в более специализированные структуры данных, такие как Order_tree и Interval_tree. Эти дополнения требуют дополнений к Node, таких как информация о размере и незначительные изменения некоторых алгоритмов.

Я хотел бы знать, как наилучшим образом реализовать дополнения в C++ с точки зрения производительности, удобочитаемости и ремонтопригодности. Деревья не должны использоваться полиморфно. До сих пор я пытался публично наследовать Tree, а затем перегружать базовые методы. (Прошу прощения за то, что новичок в объектно-ориентированном программировании)

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{}}; 

Заказать дерево

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{}}; 

Однако это не ведет себя должным образом, так как теперь у меня есть 2 корня и 2 Nils, со всей базой методы, работающие с базовым корнем, и с Tree<T>::NP, а не Order_tree::NP, поэтому атрибут размера Order_node не может быть использован.

Один из способов заключается в том, чтобы скопировать код, который очень не подлежит контролю. Другой способ, по-моему, состоит в шаблоне Tree на T, а также в NP, так что Order_tree является псевдонимом using Order_tree = Tree<Order_node> и специализирует дерево на узле.

Answer 1

После некоторых экспериментов я нашел лучший способ добиться того, что я хочу от:

• шаблон дерева от типа узла
• сделать ноль статического элемента каждого типа узла
• двигаться некоторые частные методы которые работают на узлах, не зависящих от . Корень является нормальным функционалом, установленным на узле
• выполняет функции, которые могут быть изменены виртуальные
• augment Tree публично унаследовав от него и первостепенных необходимы виртуальных функций
• использовать базовый корень Дерева (не держат данных в производном классе)

Что это выглядит сейчас:
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.ч

#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>>; 

} 

В результате размер файла проведение расширенной структуры данных в настоящее время около 1/3, как большой, а дублирование кода удаляется полностью! Это означает, что любые изменения для улучшения основных методов могут быть локализованы только в tree.h, и его эффект будет ощущаться и во всех добавленных деревьях.

Answer 2

Если вы действительно заинтересованы в том, чтобы иметь «общее дерево всех деревьев», кажется, проблема не в дереве, а в узле. Вам нужны специальные случаи узлов, так почему бы их не обобщить? Например:

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. 

}; 

Однако стоимость вызовов виртуальной функции узла довольно велика. Поэтому вам нужно четко понимать - вам нужно обобщение, а не дублирование кода, или вам нужно работать.