旋转二叉搜索树

Question

我正在实现一个二进制搜索树。我已经创建了一个方法，如果我发现树失去了平衡，就可以旋转树。不知怎么的，这个方法不能正常工作，我的树就被清空了。只有我为使树不平衡而添加的最后两个值仍留在树中。你能告诉我我的算法出了什么问题吗？我没有发布整个类，因为它很长，不想让任何人感到困惑。

 public boolean balanceBST(){
      if (root == null){
          return false;
      }

      int right = treeHeight(root.right);
      int left = treeHeight(root.left);

      if (nodeBalanceLevel(root) > 1){

                if (right - left > 1){
                    this.balanceRight();
        }
        if ( left - right > 1){
        this.balanceLeft(); 
        }
        return balanceBST();  

      }

    return true;

  }

  private void balanceRight(){

            TreeNode oldRoot = root;
            if (root.left != null)
            oldRoot.left = root.left;
            if (root.right != null)
            root = root.right;
            if (root.left != null)
             oldRoot.right = root.left; 
  }

  public void balanceLeft(){
      TreeNode oldRoot = root;
      if (root.right != null)
      oldRoot.right = root.right;
      if (root.left != null)
      root = root.left;
      if (root.right != null)
       oldRoot.left = root.right;   
  }

Answer 1

如果您有这样的bug，那么想象一下所做的事情总是很有帮助的。我已经为您的实现添加了(个人)注释：

private void balanceRight() {
  TreeNode oldRoot = root;     // Save the current root (1)
  if (root.left != null)       // This does not matter as first an assignment of null does not matter
                               // second the next assignment is a NoOp
    oldRoot.left = root.left;  // this is an assignment with no effect (2)
  if (root.right != null)
    root = root.right;         // Setting the new root (3)
  if (root.left != null)       // Now root.left is the left part of the previous root.right
                               // the left part of the previous root is discarded this way
    oldRoot.right = root.left; // oldRoot will be invalid after this operation therefore it does not matter (4)
}

我已经修正了你的算法(至少为了正确的平衡。如果你遵循我的指导原则，左边的平衡可以由你完成)。要创建这样的算法，您可以使用我在下面介绍的技术：

private void balanceRight() {
  TreeNode oldRoot = root;     // Save the current root (1)
  if (root.right != null) {    // Can this ever happen? (*)
    root = root.right;         // Setting the new root  (2)
  }
  oldRoot.right = root.left; // Assign the left sub tree to the previous root right tree (3)
  root.left = oldRoot;       // Assign to the new left tree the prevouis left tree (4)
}

(*)这种情况永远不会发生，就好像我们平衡右边的树，那么右边的树比左边的树大。

为了理解算法，写下算法中发生的事情是很有帮助的：

首先，我画了一棵树，就像这个算法所需要的那样简单。

  1
 / \
2   3
   / \
  4   5

现在我写下算法每个阶段的所有指针链接(数字与算法中的数字相对应)：

(1)

root    -> 1 / left -> 2 / right -> 3
oldRoot -> 1 / left -> 2 / right -> 3

(2)

root    -> 3 / left -> 4 / right -> 5
oldRoot -> 1 / left -> 2 / right -> 3

(3)

root    -> 3 / left -> 4 / right -> 5
oldRoot -> 1 / left -> 2 / right -> 4

(4)

root    -> 3 / left -> 1 / right -> 5
oldRoot -> 1 / left -> 2 / right -> 4

现在我又重新组合了这棵树：

    3
   / \
  1   5
 / \
2   4

对于你的算法，它看起来像(这些数字引用了我在你的算法中插入的数字)：

  1
 / \
2   3
   / \
  4   5

(1)

root    -> 1 / left -> 2 / right -> 3
oldRoot -> 1 / left -> 2 / right -> 3

(2)

root    -> 1 / left -> 2 / right -> 3
oldRoot -> 1 / left -> 2 / right -> 3

(3)

root    -> 3 / left -> 4 / right -> 5
oldRoot -> 1 / left -> 2 / right -> 3

(4)

root    -> 3 / left -> 4 / right -> 5
oldRoot -> 1 / left -> 2 / right -> 4

然后你的算法的结果是：

  3
 / \
4   5

特别是当使用纸和铅笔时，这种算法可以得到最好的评估;)