#c #class #templates #binary-search-tree #avl-tree
#c #класс #шаблоны #binary-search-tree #avl-tree
Вопрос:
Я изучаю общие деревья двоичного поиска (BST) и деревья AVL (AVL) по некоторым заметкам, которые содержат псевдокоды реализации. Я немного озадачен некоторыми деталями их реализации.
BST основан на struct Node
приведенном ниже
struct Node{
int key;
Node* parent;
Node* left;
Node* right;
//constructors
}
//methods
Версия AVL в основном такая же, с несколькими полями больше для балансировки дерева (я назову это AVLNode
для ясности, но в примечаниях нет такого различия):
struct AVLNode{
int key;
int height;
int size;
AVLNode* parent;
AVLNode* leftchild;
AVLNode* rightchild;
//constructors
}
//methods
Многие операции одинаковы между двумя деревьями, и я могу легко использовать шаблоны, чтобы повторно использовать их на обоих деревьях. Однако рассмотрим операцию insert
, которая вставляет новый узел. Код для BST-это что-то вроде
//Insert node with key k in tree with root R
void insert(const intamp; k, Node* root){
Node* N=find(k, root); //finds where to insert the node
if (N->key>k)
N->leftchild=new Node(k,N); //inserts as a left child
else
N->rightchild=new Node(k,N); //inserts as a right child
}
Теперь дело в том, что insert
работа с деревом AVL в основном одинакова. Псевдокод, представленный в примечаниях, выглядит следующим образом:
void avlInsert(int k, AVLNode* R){
insert(k,R); //same operations as for Nodes, shown above
AVLNode* N=find(x,R); //find node inserted (generic operation for BST)
rebalance(N); //perform balancing operations specific to AVL trees
}
На данный момент я немного озадачен, я знаю, что приведенное выше — всего лишь псевдокод, но мне было интересно, есть ли способ повторно использовать insert
уже предусмотренную Node
операцию. Использование специализации шаблона просто означало бы написание другой специализации insert<AVLNode>
для AVLNode
, так что это не то, что я имею в виду.
Я думаю, что было бы определить AVLNode
как дочерний класс Node
, а затем использовать что-то вроде
struct AVLNode : Node {
//implementation
}
void avlInsert(int k, AVLNode* R){
Node *root=R;
insert(k,root);
AVLNode* N=find(x,R);
rebalance(N);
}
но я не совсем уверен, что это сработает, и я не знаю, как управлять указателями на parent
и дочерними элементами (т. Е. Они должны быть указателями на Node
inside Node
и на AVLNode
inside AVLNode
).
Есть ли способ избежать перезаписи одного и того же кода?
Комментарии:
1. Рассматривали ли вы ООП? Похоже, что узел AVL является специальным узлом. Вы можете использовать AVL node extend None, а затем использовать общий узел, где это возможно
2. Да, прочтите последний абзац.
3. Дело в том, что есть 3 указателя
Node*
вNode
, которые должны бытьAVLNode*
вAVLNode
. Если я просто переопределю их вAVLNode
, в дочернем классе будет три бесполезныхNode*
указателяAVLNode
.4. Можете ли вы показать
insert
код, который вы не хотите повторять? Я не совсем понимаю, насколько сильно дублирование. Если код в основном тот же, вы могли бы использовать шаблоны.5. Не беспокойтесь о наследовании или упрощении. Вы потратите больше усилий, чем получите выгоды. Поскольку структуры независимы, оставьте их такими.
Ответ №1:
Вы могли бы использовать CRTP здесь. Это позволило бы вам создать левый правый и родительский узлы в базовом классе. Например, рассмотрим что-то вроде этого:
template<typename T>
struct BaseNode{
int key;
T* parent;
T* left;
T* right;
};
struct AVLNode : public BaseNode<AVLNode>{
int height;
int size;
AVLNode(const intamp;k, AVLNode*root){};
AVLNode(){};
};
struct Node : public BaseNode<Node>{
Node(const intamp;k, Node*root){};
Node(){};
};
template<typename T>
T* find(const intamp; k, T* root){return root;};
template<typename T>
void insert(const intamp; k, T* root){
T* N=find(k, root); //finds where to insert the node
if (N->key>k)
N->left=new T(k,N); //inserts as a left child
else
N->right=new T(k,N); //inserts as a right child
}
void test(){
AVLNode avl_root;
Node node_root;
insert(42, amp;avl_root);
insert(42, amp;node_root);
}
Недостатком является то, что компилятор сгенерирует больше кода, чем необходимо. Потому что это создает новую функцию вставки для каждого типа. Возможно, это не проблема для вас, но стоит подумать. Сгенерированный код см. в godbolt.
В качестве отступления. Пожалуйста, пожалуйста, пожалуйста, не используйте необработанные указатели и new и delete. Вы получите так много утечек памяти, особенно если указатель «потерян» из-за удаления его родительского элемента. Рассмотрите возможность использования интеллектуальных указателей, таких как unique_ptr
или shared_ptr