c++ - 如何在 C++ 中实现一个 avl 树，每个节点都是另一个 avl 树

Question

我有一个 input.txt 文件，其中包含这样的数字：input.txt 文件

我正在尝试制作一个 avl 树，其中每个节点都是来自第一列的数字，并且每个节点都指向另一个包含来自第二列的数字的 avl 树。有人可以解释如何在 C++ 中实现这一点吗？

标签： c++avl-tree

Answer 1

像使用整数节点一样实现它：

struct AVL_node
{
  bool color;
  int key;
  AVL_Tree value;
  AVL_Node * left_subtree;
  AVL_Node * right_subtree;
};

在树中，您需要将键、值和链接字段分开。关键是您用于订购节点的内容。价值就是数据。

值没有区别。它可能是std::vector或std::map丢失。一般不会复制节点，只会更改链接。但是，如果复制节点，则键和值字段都将被复制。

请记住，在组织节点时，只有链接字段会发生变化。密钥用于确定排序。