Наследование и деревья AVL/BST

Можно ли использовать одну и ту же функцию вставки для дерева Bst и Avl? Проблема в том, что Bst и Avl имеют разные типы узлов, но я не хочу, чтобы Bst Node имел общий случай (с высотой и Node * parent внутри, что не имеет смысла, потому что нет необходимости в родительском и высотном уровне внутри Bst).Наследование и деревья AVL/BST

class Bst 
{ 
public: 
    struct Node 
    { 
     int value; 
     Node* left; 
     Node* right; 
    }; 

    Node* insert(Node* node) {/* do stuff using Bst::Node */} 

    // ... 
}; 

class Avl : public Bst 
{ 
public: 
    struct Node : public Bst::Node 
    { 
     int height; 
     Node* parent; 
    }; 

    // now I want that Bst::insert use this Node 
    // instead of the old one 


    Node* insert(Node* node) 
    { 
     Node* inserted_node = Bst::insert(node); 
     /* rotations stuff */ 
     return inserted_node; 
    } 
};

Примерно то, что я пытаюсь сделать, это Bst::Node "virtual".

Итак, как я могу решить проблему внедрения Avl Tree без перезаписи всей функции вставки только потому, что Node изменен?

источник

2015-11-25 tjbrn

Почему BST и дерево AVL имеют разные типы узлов? По моему пониманию предмета, представленные данные одинаковы, дерево AVL использует более сложные алгоритмы для вставки и удаления узлов. – Codor

Это одна из тех ситуаций, когда шаблоны и «виртуальные» - это два разных механизма для достижения одного и того же. Но в этом конкретном случае «виртуальный» явно уступает. Это меньше обычного выбора стиля и более хорошего/плохого выбора. – JSF

BST просто нужно значение и указатели влево и вправо, AVL нужно дополнительное значение высоты и указатель родителя. Представленные данные (значение) имеют тот же тип – tjbrn

Возможно, вам нужен CRTP (в этом случае вы не указали достаточную информацию о своих потребностях даже для приблизительного примера, но более простой и менее мощный подход к шаблону может иметь для вас больше смысла. Используйте базовый класс (под каждым из ваши типы деревьев), которые не имеют элементов данных, и просто определяют статические функции шаблона для общего кода. Поскольку функции являются статическими, вам необходимо передать соответствующие данные (для вставки, которая должна быть &root), но это не должно быть большой проблемой . (Грубый и непроверенные):

struct tree_base 
{ 
    template <class Node> 
    static Node* insert(Node** where, Node* what) 
    { 
     Node* here; 
     while ((here = *where) != 0) 
     { 
     if (*what < *here) where = &(here->left); 
     else if (*here < *what) where = &(here->right); 
     else 
     { 
     Trying to insert something already there, what should be done 
     } 
     } 
     *where = what; 
     return what; // Is that the desired return? 
    } 
};

Тогда каждый из ваших классов реального дерева унаследует от tree_base и назвали бы tree_base::insert(&root, new_node) сделать общие части insert

CRTP-версия, которая позволила бы root быть членом базового класса, даже если он указывает на тип узла производного класса. Учитывая, что root является членом базового класса, функция вставки не должна быть static и не требуется принимать &root в качестве входных данных. А поскольку базовый класс CRTP уже правильно настроен для доступа к типу Node, метод вставки базового класса не должен быть шаблоном. Все, что было бы намного больше, чтобы учиться (смотря на некоторые реальные примеры CRTP) и, вероятно, перегружать для совместного использования кода.

источник

2015-11-25 15:27:23 JSF

Наследование и деревья AVL/BST

ответ

Смежные вопросы