旋转二叉搜索树 [英] Rotating a binary search tree

问题描述

我正在实现一个二进制搜索树.如果发现树不平衡，我已经创建了一种旋转树的方法.不知何故，此方法无法正常工作，我的树被清空了.我添加的使树不平衡的最后两个值仍然保留在树中.你能告诉我我的算法有什么问题吗?我没有发布整个课程，因为它很长，不想让任何人感到困惑.

I am implementing a binary search tree. I have created a method to rotate the tree if I find that the tree is out of balance. Somehow this method is not working correctly and my tree is emptied. Only the last two values I added to make the tree unbalanced are still left in the tree. Can you tell me what is wrong with my algorithm? I have not posted the entire class because it is very long and do not want to confuse anyone.

 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;   
  }

推荐答案

如果您有这样的错误，那么想象完成该操作总是有帮助的.我已向您的实施中添加了(个人)评论:

If you have such a bug then it is always helpful to imagine what is done. I've added (personal) comments to you implementation:

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)
}

我已经纠正了您的算法(至少对于右侧平衡而言.如果您遵循我的指南，则可以由您完成左侧平衡).要创建这样的算法，您可以使用以下介绍的技术:

I've corrected your algorithm (at least for the right balancing. The left balancing can be done by you if you follow my guidelines). To create such an algorithm you can use a technique that I introduce in the following:

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)
}

(*)这永远都不会发生，就好像我们平衡右边然后右边的树大于左边的树.

(*) This should never happen as if we balance right then the right tree is larger than the left one.

要了解算法，请写下算法中发生的事情会有所帮助:

To understand the algorithm it is helpful to write down what happens in the algorithm:

首先，我画出一棵树，这种树要满足此算法的要求.

First I draw a tree that is as simple as needed for this algorithm.

  1
 / \
2   3
   / \
  4   5

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

Now I write down all pointers link at every stage of the algorithm (the numbers correspondent with the numbers in the algorithm):

(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

现在，我再次将树重新组成:

Now I compose the tree back again:

    3
   / \
  1   5
 / \
2   4

对于您的算法，它看起来像(数字表示我在算法中插入的数字):

With your algorithm it looks like (the numbers reference to the numbers I inserted in your algorithm):

  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

那么您的算法的结果就是:

The result of your algorithm is then:

  3
 / \
4   5

特别是在使用纸和铅笔时，这种算法最多可以评估；)

Especially such algorithm can be evaluated at best when using paper and pencil ;)

这篇关于旋转二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！