Блог

Я изучаю общие деревья двоичного поиска (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 ).

Есть ли способ избежать перезаписи одного и того же кода?

Вы могли бы использовать 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