C++. Как спроектировать наследование Дерева Поиска в АВЛ

Question

Ломаю голову над тем, как правильно реализовать АВЛ-дерево на основе существующего бинарного поиска.

Есть шаблонный класс Узел, который хранит ключ и данные узла (некий словарь), указатели на поддеревья.

template <class T>
class Node
{
private:
    T _data;
    int _key;
    Node* _left, * _right;

public:
    friend class BinaryTree<T>;
}

Сам же шаблонный класс Дерево хранит указатель на корень и инварианты древа.

template <class T>
class BinaryTree
{
private:
    Node<T>* _root;
    int _height,
        _order;
}

Так вот, я хотел бы унаследовать это дерево, просто переопределив добавление, удаление (сделав функции виртуальными). Да и логично это - АВЛ это то же дерево, с единственным отличием - оно всегда сбалансировано.

Но возникает проблема - класс Узел. Для АВЛ дерева он должен содержать высоту относительно корня, для БДП это излишне, и как разрешить эту коллизию без костылей - я не знаю.

Answer 1

Способ есть, но вам не понравится. С использованием CRTP.

Это также позволяет обойтись без виртуальных функций - что хорошо, потому что быстрее и не занимает места в классе. Но если вдруг захочется их добавить, то ничто не мешает это сделать (в реализации от них толку нет; есть смысл добавлять только как фичу для пользователей класса, если им позарез нужно использовать деревья полиморфно) (для этого добавляете родителя с единственным шаблонным параметром template <typename T>, от него наследуете BasicBinaryTree).

#include <iostream>

// Binary tree

template <typename DerivedNode, typename T>
struct BasicBinaryTreeNode
{
    // Для простоты все публичное.
    // Все равно из дерева не должны торчать наружу ноды, так?
    T value{};
    DerivedNode *left = nullptr;
    DerivedNode *right = nullptr;
};

template <typename Derived, typename Node, typename T>
class BasicBinaryTree
{
  protected:
    Node *left = nullptr;
    Node *right = nullptr;

    // Тестовая функция, внутренняя, которую будем переопределять в потомке.
    void TEST_modify_node(Node *) {}

  public:
    BasicBinaryTree() {}

    // Здесь функции родителя - бинарного дерева.

    // Тестовая функция.
    void TEST_add_node()
    {
        std::cout << "Adding node!\n";
        left = new Node;
        // Хитрый вызов, чтобы подхватить переопределение из потомка.
        static_cast<Derived *>(this)->TEST_modify_node(left);
    }
};

template <typename T>
struct BinaryTreeNode : BasicBinaryTreeNode<BinaryTreeNode<T>, T> {};
template <typename T>
class BinaryTree : public BasicBinaryTree<BinaryTree<T>, BinaryTreeNode<T>, T>
{
  public:
    // Наследуем конструкторы.
    using BasicBinaryTree<BinaryTree<T>, BinaryTreeNode<T>, T>::BasicBinaryTree;
};

// AVL tree

// Казалось бы, этот класс избыточен, можно сразу вписать все в `AvlTreeNode`.
// Но тогда не получится сделать еще один уровень наследования, если он потом понадобится.
template <typename DerivedNode, typename T>
struct BasicAvlTreeNode : BasicBinaryTreeNode<DerivedNode, T>
{
    int height = 0;
};
template <typename T>
struct AvlTreeNode : BasicAvlTreeNode<AvlTreeNode<T>, T> {};

// Аналогично.
template <typename Derived, typename Node, typename T>
class BasicAvlTree : public BasicBinaryTree<Derived, Node, T>
{
    // Здесь функции потомка - AVL-дерева.
    // Тут в основном должны быть protected функции, в небольшом количестве.
    // Основная масса public функций - в родителе.

    friend BasicBinaryTree<Derived, Node, T>;

  protected:
    void TEST_modify_node(Node *x)
    {
        std::cout << "Setting height!\n";
        x->height = 1;
    }

  public:
    using BasicBinaryTree<Derived, Node, T>::BasicBinaryTree;
};

template <typename T>
class AvlTree : public BasicAvlTree<AvlTree<T>, AvlTreeNode<T>, T>
{
  public:
    using BasicAvlTree<AvlTree<T>, AvlTreeNode<T>, T>::BasicAvlTree;
};

// ---

// Пробуем:
int main()
{
    BinaryTree<int> x;
    x.TEST_add_node(); // Adding node!
    std::cout << "---\n";
    AvlTree<int> y;
    y.TEST_add_node(); // Adding node! Setting height!
}

Answer 2

Из всех зол выбрал наименьшее: в шаблон добавил параметр по умолчанию, принимающий тип узла, в теле класса старые типы Node заменил на шаблонный тип:

template <typename T, class TypeNode = Node<T>>
class BinaryTree{
    ...
    BinaryTree(BinaryTree<T, TypeNode>&& other) noexcept;
    ...
    TypeNode* find(int) const;
    ...
};

При этом инициализация осталась прежней:

BinaryTree<int> tree(key, data, 16); // 16 - размер массивов key и data

Для АВЛ-дерева написал свой контейнер узла (минимальное дублирование кода):

template <typename T>
class AVLNode
{
public:
    T _data;
    int _key;
    AVLNode* _left, * _right;
    int _height;

public:
    friend class AVLTree<T>;        // для того, что бы AVLTree имел доступ к полям и методам AVLNode
    ...
}

Ну и унаследовал, собственно, само дерево, подставляя в качестве контейнера AVLNode:

template <typename T, class TypeNode>
class AVLTree : public BinaryTree<T, AVLNode<T>>
{
public:
    AVLTree() : BinaryTree<T, AVLNode<T>>() {
    }
    ...
}

Для более изящного решения нужно унаследовать сам AVL-узел. я столкнулся со следующей проблемой:

template <typename T>
class AVLNode : public Node<T> 
{
protected:
    int _height;

public:
    friend class AVLTree<T>;
    ...
};

при такой структуре указатели нода все равно остаются не авл, поэтому вариантов два:

сделать их приватными, добавить и в AVL, и в BST с нужным типом - дублирование кода, смысл тогда наследовали?
сделать для нода такой же шаблонный параметр, как и для BST, но тогда встает вопрос с параметром по умолчанию: он будет классом, параметром шаблона которого он является - ошибка компиляции. как разрешить - вопрос.

БЛОГ НА HUSL

C++. Как спроектировать наследование Дерева Поиска в АВЛ

Ответы (2 шт):