获取堆栈溢出试图实施AVL树

-1

每次我添加一个新的节点插入到树首先将其排序，作为一个二叉树然后递归查找违规在AVL旋转时。获取堆栈溢出试图实施AVL树

问题是在我的旋转功能我试图测试AVL违规，这需要一个左 - 左旋转，当我通过首先创建一个根，然后创建一个正确的孩子，然后另一个左边的孩子B一个。现在发生的事情是，它输出了直到结束，然后我得到一个错误说：

Exception in thread "main" java.lang.StackOverflowError

at AVLTree$AVLNode.height(AVLTree.java:63)

at AVLTree$AVLNode.height(AVLTree.java:62)

我真的不了解问题

54 int getBalance(){ 
55  int leftHeight = (left == null)?0:left.height(); 
56  int rightHeight = (right == null)?0:right.height(); 
57  
58  return leftHeight - rightHeight; 
59 } 
61 int height(){ 
62  int leftHeight = (left == null)?0:left.height(); 
63  int rightHeight = (right == null)?0:right.height(); 

     return 1 + Math.max(leftHeight, rightHeight); 
    }  

public void rotate(AVLNode test){ 
     System.out.println(test.getBalance()); 
     if(Math.abs(test.getBalance()) < 2){ 

      if(test.getParent() != null){ 
       rotate(test.getParent()); 
      } 
      else{ 
       return; 
      } 
     } 
     if(test.getBalance() <= -2){ 

      System.out.println(test.getBalance()); 

      if(test.getRight().getBalance() <= 0){ 

       System.out.println("i'm in"); 
       AVLNode parent = test.getParent(); 

       if(parent != null){ 

        if(parent.getLeft() == test){ 
         parent.setLeft(test.getRight()); 
        } 
        else{ 
         parent.setRight(test.getRight()); 
        } 
       } 

       else{ 
        this.root = test.getRight(); 
       } 
       test.setParent(test.getRight()); 

       if(test.getRight().getLeft() != null){ 

       test.getRight().getLeft().setParent(test); 
       test.setRight(test.getRight().getLeft()); 
       } 

       test.getParent().setLeft(test); 
       System.out.println("got till the end"); 
      } 
     }

来源

2016-11-28 mouse_s

int height(){ 
     int leftHeight = (left == null)?0:left.height(); 
     int rightHeight = (right == null)?0:right.height(); 
     return 1 + Math.max(leftHeight, rightHeight); 
    }

这个recursive method没有exit当left不是null它会调用left.height（）left.height（）left.height（）left.height（）.... ....直到堆栈溢出

来源

2016-11-28 01:59:03

如何你建议退出该方法吗？ –

我的想法是，如果我们需要计算**节点**的高度，那么计算其左侧子节点和右侧子节点的高度，然后return 1 + Math.max(leftHeight, rightHeight); 完整的代码可以是这样的：'int height（TreeNode tn）{if（tn = = null）{return 0;}
int leftHeight = tn.left.height（）;
int rightHeight = tn.right.height（）;
返回1 +数学。最大（leftHeight，rightHeight）;
}' –

推测高度是一种属于AVLNode的方法，在这种情况下，递归调用应该最终终止，假设一个合适的树结构。虽然这是发生溢出的方法，但这不是问题的原因。 – Lidae

我认为你有一个rotate方法的问题，虽然很难通过阅读代码来进行调试。在我看来，你正在得到一个循环引用，然后引起height方法中的StackOverflow。虽然height就是溢出根据堆栈跟踪时，它不应该发生，除非有在树形结构中循环。例如，如果其中一个节点本身是左小孩，则会发生这种情况。

我不是很熟悉的AVL算法，但它看起来对我来说，错误的来源之一（可能不是唯一的一个）在rotate方法是parent的左孩子可能会设置为test的但是测试的权利孩子的父母从未设置为parent。

同样，这样很难读取和调试代码。一个建议是尝试将算法分成更小的块，或者制作易于验证的小型辅助函数。

来源

2016-11-28 02:15:06 Lidae

你是对的我真的用旋转方法冲过去了我会努力使它更清晰 –

我的想法是，如果我们需要计算节点的高度，然后计算出其左孩子和右孩子的高度，然后
return 1 + Math.max(leftHeight, rightHeight)
完整的代码可以是这样的：

int height(TreeNode tn){ 
     if(tn==null){return 0;} 
     int leftHeight = tn.left.height(); 
     int rightHeight = tn.right.height(); 
     return 1 + Math.max(leftHeight, rightHeight); 
    }

来源

2016-11-28 02:22:19

获取堆栈溢出试图实施AVL树

回答

相关问题