二叉树旋转

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“支票”来的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 

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

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 Balancing子例程启用相同。

关于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的第二条评论，我发现了这个问题。在我的旋转方法中，我忘记了实际上每当根被移位时我都必须更新树的根指针。

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

Answer 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）标准储备标识符与领先的下划线，并且用双下划线。据称，如果你不尊重标准和编译器提供的库，你可以得到惊人的交互 - 尽管如此，我想这必须与成员标识符的宏相关。尾部下划线是可以的 - 我倾向于将它们用于包括守卫。

成员变量的通用惯例是添加前导m或m_。可能更常见的是，根本没有任何特殊的前缀或后缀。其次，你可能（或不可能）发现实现没有父节点存储在节点中的AVL树更容易。我自己还没有实现AVL树，但是我曾经实施过红黑树。许多算法需要包括递归搜索作为第一步 - 您不能只做一个标准的搜索来记录找到的节点，但会丢弃到该节点的路由。但是，递归实现并不算太糟糕，并且指向玩杂耍的指针也越来越少。

最后，一般的提示 - 试图“预演”像这样的算法可以很容易地发觉你的，除非你严格工作通过它一步一步，并检查相关的所有信息来源（有我已经修改了这个？）在每一步。养成跳过速度细节的习惯很容易。一个有用的机器辅助的干运行是在调试器中逐步运行代码，并查看每个步骤的结果是否与您的纸张干运行一致。

编辑 - 多一个音符 - 因为我不知道在这种情况下，我不会把这种小费。我通常用简单的结构来实现数据结构节点 - 没有数据隐藏，如果有任何成员函数，则很少。大多数代码与数据结构保持分离，通常在“工具”类中。我知道这打破了旧的“形状本身”的OOP原则，但IMO在实践中效果更好。

Answer 3

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

以现在的眼光较高的水平，我已经使用，以避免与AVL Tree或Red-Black Tree代码的问题是改为使用一个AA Tree，它具有类似性能的技术他们使用O（n）空间和O（log n）时间来进行插入，删除和搜索。但是，AA树的代码要简单得多。