实现二叉搜索树时对类的疑问

Question

我正在研究一些包含实现伪代码的笔记上的通用二叉搜索树(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 int& 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
}

现在，重点是AVL树的insert操作基本相同。注释中提供的伪代码如下：

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 
}

在这一点上我有点困惑，我知道上面只是一个伪代码，但我想知道是否有办法重用已经为Node提供的操作insert。使用模板专业化只是意味着为AVLNode编写不同的专业化insert<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内部Node和AVLNodeAVLNode内部的指针)。

有没有办法避免重写相同的代码？

Answer 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 int&k, AVLNode*root){};
AVLNode(){};
};
struct Node : public BaseNode<Node>{
Node(const int&k, Node*root){};
Node(){};
};
template<typename T>
T* find(const int& k, T* root){return root;};
template<typename T>
void insert(const int& 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, &avl_root);
insert(42, &node_root);
}

缺点是编译器将生成比必要更多的代码。因为它为每个类型创建一个新的插入函数。这对您来说可能不是问题，但值得考虑。有关生成的代码，请参见 godbolt。

顺便说一句。请不要使用原始指针和新的和删除。你会得到很多内存泄漏，特别是如果一个指针因为它的父指针被删除而"丢失"。考虑使用智能指针，如unique_ptr或shared_ptr