c++ - 二叉树旋转

Question

我正致力于实现 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 的插入方法中，它将打印刚刚插入的键.

然后在程序的入口点，我在堆上分配一个 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 Balancing 后，它就像普通的二叉搜索树一样工作。终端输出为:

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!

Answer 1

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

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