继承和 AVL/BST 树

Question

有什么方法可以对Bst和Avl树使用相同的插入函数吗？问题是 Bst 和 Avl 有不同的 Node 类型，但我不想让 Bst Node 成为一般情况（里面有 height 和 Node* parent，这是没有意义的，因为不需要 parent 和 height inside a 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".

那么，如何解决仅仅因为Node变了就实现Avl Tree而不重写整个insert函数的问题呢？

Answer 1

也许您需要 CRTP（在这种情况下，您没有提供足够的信息来说明您的需求，即使是一个粗略的例子，但更简单、功能更弱的模板方法可能对您更有意义。有一个基础 class （在你的每个树类型下）没有数据成员，只是为公共代码定义静态模板函数。由于函数是静态的，你需要传入相关数据（插入应该是 &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?
   }
};

然后你的每个真正的树 classes 将继承自 tree_base 并调用 tree_base::insert(&root, new_node) 来完成 insert

的公共部分

它的 CRTP 版本将允许 root 成为基础 class 的成员，即使它指向派生 class 的节点类型。给定 root 作为基础 class 的成员，插入函数不需要 static 也不需要将 &root 作为输入。由于 CRTP 基础 class 已经正确地模板化以访问 Node 类型，基础 class 插入方法不需要是模板。所有这些都需要学习更多的东西（通过查看 CRTP 的一些真实示例），并且对于您想要的代码共享来说可能有点矫枉过正。

Answer 2

其实我也在做这方面的工作，我觉得你很清楚地描述了你想要什么。

起初，可能对给定的接口有点困惑，insert() 不应该 return 节点的指针，不是吗。我们可以使用 findNode() 函数，它 return Node 的指针并且只做这个工作。

回到主要问题，也许你可以使用模板为BST中的每个函数设置你的节点类型。但是BST不仅仅是一个抽象接口，它还实现了BST操作，所以不是CRTP..

目前的伪代码可能如下： // 预定义：

//parent ptr also alleviate the implementation of BST.

template<typename T>
class BST{
    ... omit..
    protected:
        template<typename node_type>
        class BST_Node{  
            public:
                T val;
                BST_Node *left, *right, *parent;  
                BST_Node():left{nullptr}, 
                           right{nullptr},
                           parent{nullptr}, val{}{};
        // empty {} default to value initialization.
        }
 ... omit ...
}


template<typename T>
class AVL_Node : public BST_Node{
    public:
        short height;
        AVL_Node(T val):BST_Node(val), height(0){};
}

template<typename T>
void insert(T val){
    AVL_Node<T> Node(val);
    BST<T>::insert_node<AVL_Node>(Node);
    AVL_Node<T>* ptr = BST<T>::find_node<AVL_Node>(val);
    ptr->height = BST<T>::get_height(ptr); 

    state = chk_balance(ptr);
    switch(state){
        case 0:  // tree very balance..
            break;
        case 1:
            LL_rotate(ptr);
            break;
        case 2:
            RR_rotate(ptr);
            break;
        ... omit
     }
}

@帮助post解决你的问题..

继承和 AVL/BST 树

Inheritance and AVL/BST Trees

c++

inheritance

binary-search-tree

avl-tree