3

我正在实现 AVL 搜索树。到目前为止，我已经完成了编码部分，并开始测试它的错误。我发现我的节点旋转方法有问题，看在上帝的份上，我无法理解问题所在。

该算法在纸上工作，但在机器上执行时它很好......泄漏树节点。

这是用于向左旋转节点的方法：http: //pastebin.com/mPHj29Af

bool avl_search_tree::avl_tree_node::rotate_left()
{
    if (_right_child != NULL) {
        avl_tree_node *new_root = _right_child;
 
        if (_parent != NULL) {
            if (_parent->_left_child == this) {
                _parent->_left_child = new_root;
            } else {
                _parent->_right_child = new_root;
            }
        }
 
        new_root->_parent = _parent;
        _parent = new_root;
 
        _right_child = new_root->_left_child;
        new_root->_left_child = this;
 
        if (_right_child != NULL) {
            _right_child->_parent = this;
        }
 
        //update heights
        update_height();
        new_root->update_height();
 
        return true;
    }
 
    return false;
}

在我的插入方法中，我评论了 AVL 平衡部分，而我只是试图将新插入的节点向左旋转。以升序插入整数的结果：我的树只包含初始根（插入的第一个节点），所有其他节点都泄漏了。

由于我开始发疯，因此非常感谢您在识别问题方面的任何帮助。

记录一下：如果我不使用任何旋转，树不会泄漏节点，它可以作为正常的不平衡二叉搜索树（用于插入和查找）。

编辑：由于 AJG85 的评论，我将添加观察结果：

我将 printf 'checks' 添加到 avl_search_tree::avl_tree_node 的析构函数方法中，该方法将在清理之前打印键值（在我的情况下为 32 位整数），并添加到 avl_search_tree 的 insert 方法中，该方法将打印刚刚插入的键。

然后在程序的入口点中，我在堆上分配一个 avl_search_tree 并按升序向它添加键，然后将其删除。

启用 AVL 平衡后，我在终端中得到以下输出：

bool avl_search_tree::insert(const int&) : 1
bool avl_search_tree::insert(const int&) : 2
bool avl_search_tree::insert(const int&) : 3
bool avl_search_tree::insert(const int&) : 4
bool avl_search_tree::insert(const int&) : 5
bool avl_search_tree::insert(const int&) : 6
bool avl_search_tree::insert(const int&) : 7
bool avl_search_tree::insert(const int&) : 8
avl_search_tree::avl_tree_node::~avl_tree_node() : 1

这意味着所有插入都成功，但只有根已被删除。

注释掉 AVL 平衡后，它的工作原理就像一个普通的二叉搜索树。终端输出为：

bool avl_search_tree::insert(const int&) : 1
bool avl_search_tree::insert(const int&) : 2
bool avl_search_tree::insert(const int&) : 3
bool avl_search_tree::insert(const int&) : 4
bool avl_search_tree::insert(const int&) : 5
bool avl_search_tree::insert(const int&) : 6
bool avl_search_tree::insert(const int&) : 7
bool avl_search_tree::insert(const int&) : 8
avl_search_tree::avl_tree_node::~avl_tree_node() : 1
avl_search_tree::avl_tree_node::~avl_tree_node() : 2
avl_search_tree::avl_tree_node::~avl_tree_node() : 3
avl_search_tree::avl_tree_node::~avl_tree_node() : 4
avl_search_tree::avl_tree_node::~avl_tree_node() : 5
avl_search_tree::avl_tree_node::~avl_tree_node() : 6
avl_search_tree::avl_tree_node::~avl_tree_node() : 7
avl_search_tree::avl_tree_node::~avl_tree_node() : 8

这意味着一切都已妥善清理。

现在......我是如何得出轮换方法是问题的结论？在注释的 AVL 平衡子程序下，我添加了一条线，将每个新插入的节点向左旋转。结果？就像启用了 AVL 平衡子例程一样。

而关于 update_height() 方法，它不会以任何方式改变树的结构。

我希望这会澄清它。

编辑2：

为了澄清更多的事情，他是如何实现 avl_tree_node 析构函数的：

avl_search_tree::avl_tree_node::~avl_tree_node()
{
    printf("%s : %d\n", __PRETTY_FUNCTION__, *_key);

    if (_left_child != NULL) {
        delete _left_child;
    }

    if (_right_child != NULL) {
        delete _right_child;
    }

    if (_key != NULL) {
        delete _key;
    }
}

_left_child 和 _right_child 是指向在堆上分配的 avl_tree_node 对象的指针。

编辑3：

感谢 AGJ85 的第二条评论，我发现了这个问题。在我的旋转方法中，我忘记了每当根移动时我实际上必须将树的根指针更新为新根。

基本上，树的根始终指向第一个插入的节点，并且在需要时不更新指针，我的旋转方法会泄漏实际配置正确的新树的根。:)

谢谢AGJ85！

4

3 回答 3

3

感谢 AGJ85 的第二条评论，我发现了这个问题。在我的旋转方法中，我忘记了每当根移动时我实际上必须将树的根指针更新为新根。

基本上，树的根始终指向第一个插入的节点，并且在需要时不更新指针，我的旋转方法会泄漏实际配置正确的新树的根。:)

于 2011-08-03T09:03:33.677 回答
2

编辑- 该死的 - 我没有看到问题已经解决（有问题的答案）。尽管如此，也许在这个值得挽救的问题中存在一些非答案提示。

我没有彻底检查，但我认为你在这条线上出错了......

_right_child = new_root->_left_child;

问题是您可能已经new_root->_left_child在该行中覆盖了...

_parent->_left_child = new_root;

我认为你应该做的是，在一开始，有一个本地定义块，比如......

avl_tree_node *orig_parent      = _parent;
avl_tree_node *orig_this        = this;
avl_tree_node *orig_left_child  = _left_child;
avl_tree_node *orig_right_child = _right_child;

然后使用orig_局部变量作为以后赋值的源。这在一定程度上省去了对旋转过程中通过各种指针的数据流的担忧。优化器应该摆脱在这方面值得担心的任何多余工作，而且无论如何也没有太多。

加几分...

首先，C++（和 C）标准保留带有前导下划线和双下划线的标识符。据称，如果您不尊重这一点，您可能会与标准库和编译器提供的库进行惊人的交互——不过，我想这必须与成员标识符的宏相关。尾随下划线是可以的 - 我倾向于将它们用于包含警卫。

成员变量的常见约定是添加前导mor m_。更常见的可能是根本没有任何特殊的前缀或后缀。

其次，您可能（或可能不会）发现实现没有存储在节点中的父链接的 AVL 树更容易。我自己还没有实现 AVL 树，但我确实实现了一次红黑树。许多算法需要将递归搜索作为第一步 - 您不能只进行标准搜索来记住找到的节点，但会丢弃到达该节点的路由。但是，递归实现还不错，而且可以玩弄的指针更少。

最后，一个一般提示 - 尝试“试运行”这样的算法很容易让你绊倒，除非你严格地一步一步地完成它，并检查所有相关的信息来源（我已经修改了吗？）每一步。很容易养成跳过一些细节以提高速度的习惯。一个有用的机器辅助试运行是在调试器中逐步运行代码，并查看每一步的结果是否与您的论文试运行一致。

编辑- 另一个注意事项 - 我不会称之为小费，因为我不确定在这种情况下。我通常用简单的结构来实现数据结构节点——没有数据隐藏，如果有的话，成员函数很少。大多数代码与数据结构分开保存，通常在“工具”类中。我知道这打破了旧的“形状自己绘制”OOP 原则，但 IMO 在实践中效果更好。

于 2011-08-02T19:34:02.177 回答
1

我看到您在代码中找到了您正在寻找的错误。（正如您所说，当根更改时，您并没有将树根指针更新到新根。这是列表和树插入/删除方法的常见范例，以返回指向列表头或树根的指针，如果你记得那个范式不会再犯错误了。）

在更高的层次上，我用来避免AVL 树或红黑树代码问题的技术是使用与它们具有相似性能的AA Tree，使用 O(n) 空间和 O(log n) 插入、删除和搜索的时间。但是，AA 树的编码要简单得多。

于 2011-08-04T15:55:29.493 回答