二进制搜索树平衡

我在这里有一个quesiton，但它没有保存。我无法平衡完全不平衡的树（右侧的节点1-15）。二进制搜索树平衡

我遇到了麻烦，因为我得到堆栈溢出。

> // balancing 
    public void balance(node n) { 
     if(n != null) { 
      System.out.println(height(n)-levels); 
      if (height(n.RCN) != height(n.LCN)) { 
       if (height(n.RCN) > height(n.LCN)) { 
        if(height(n.RCN) > height(n.LCN)) { 
         n = rotateL(n); 
         n = rotateR(n); 
        } else { 
         n = rotateL(n); 
        } 
       } else { 
        if(height(n.LCN) > height(n.RCN)) { 
         n = rotateR(n); 
         n = rotateL(n); 
        } else { 
         n = rotateR(n); 
        } 
       } 
       balance(n.LCN); 
       balance(n.RCN); 
      } 
     } 
    } 

    // depth from node to left 
    public int heightL(node n) { 
     if (n == null) 
      return 0; 
     return height(n.LCN) + 1; 
    } 

    // depth from node from the right 
    public int heightR(node n) { 
     if (n == null) 
      return 0; 
     return height(n.RCN) + 1; 
    } 

    // left rotation around node 
    public node rotateL(node n) { 
     if (n == null) 
      return null; 
     else { 
      node newRoot = n.RCN; 
      n.RCN = newRoot.LCN; 
      newRoot.LCN = n; 
      return newRoot; 
     } 
    } 

    // right rotation around node 
    public node rotateR(node n) { 
     if (n == null) 
      return null; 
     else { 
      node newRoot = n.LCN; 
      n.LCN = newRoot.RCN; 
      newRoot.RCN = n; 
      return newRoot; 
     } 
    }

来源

2010-03-23 Stephen

强制性评论：呵呵？你的问题是什么？ – 2010-03-23 18:58:39

我以为我用我的问题编辑过，但没有保存。我的错。基本上，我得到一个堆栈溢出，因为我有一个不正确的算法。我有正确的想法，但我无法实施。我认为麻烦的是，如果n是偶数，我需要从根部平衡到双方相等或相差1，然后沿着左边节点向下进行递归平衡，然后进入根节点。 – Stephen 2010-03-23 19:05:08

我也注意到，似乎有一个错误发生，因为空值（也许n.left为空，所以我得到一个错误），但我把一个“其他回报”，并停止了错误，并显示那里几乎没有发生变化。 – Stephen 2010-03-23 19:07:03

做一个rotateL后跟一个rotateR结束无所事事，因为要修改的同一节点。 n不是原来的n。它是功能的newNode。所以基本上，n是这样的：

newNode = rotateL(n); 
n = rotateR(newNode);

所以你基本上是离开树不变。

我也不确定你为什么重复if (height(n.RCN) > height(n.LCN))检查。我想你的意思是你的第一次检查更像abs(height(n.RCN) - height(n.LCN)) > 1，然后使用比较来确定旋转方式。

另外，你可以添加执行height(...)？

来源

2010-03-23 19:35:42

二进制搜索树平衡

回答

相关问题