AVL树向左和向右旋转C＃

我试图实现AVL树，但是当我将树打印出来时，它什么都不做。我在想我的左右旋转实现有问题。AVL树向左和向右旋转C＃

我已经在两个变量“旧”和“新”之间转移了旋转值以使其更容易。

 private void rotateLeft(ref Node<T> tree) 
     { 
      if (tree.Right.BalanceFactor > 0) 
      { 
       rotateRight(ref tree.Right); 
      } 
      Node<T> oldRoot = tree; 
      Node<T> newRoot = tree; 

      newRoot.Right = oldRoot; 
      oldRoot.Left = newRoot; 
      newRoot.Right = oldRoot.Left; 

     } 

     private void rotateRight(ref Node<T> tree) 
     { 
      if (tree.Left.BalanceFactor < 0) 
      { 
       rotateLeft(ref tree.Left); 
      } 
      Node<T> oldRoot = tree; 
      Node<T> newRoot = tree; 

      newRoot.Left = oldRoot; 
      oldRoot.Right = newRoot; 
      newRoot.Left = oldRoot.Right; 


     }

继承人的节点BalanceFactor

class Node<T> where T : IComparable 
{ 
    private T data; 
    private int balanceFactor = 0; //added for AVLTree 
    public Node<T> Left, Right; 

    public int BalanceFactor 
    { 
     set { balanceFactor = value; } 
     get { return balanceFactor; } 
    }

插入项目

private void insertItem(T item, ref Node<T> tree) 
     { 
      if (tree == null) 
       tree = new Node<T>(item); 
      else if (item.CompareTo(tree.Data) < 0) 
       insertItem(item, ref tree.Left); 
      else if (item.CompareTo(tree.Data) > 0) 
       insertItem(item, ref tree.Right); 

      tree.BalanceFactor = Height(tree.Left) - Height(tree.Right); 

      if (tree.BalanceFactor <= -2) 
       rotateLeft(ref tree); 
      if (tree.BalanceFactor >= 2) 
       rotateRight(ref tree); 
     }

来源

2014-01-27 bananabreadbob

你可以发布'Node.BalanceFactor'的代码吗？ –

“BalanceFactor”在哪里计算？从您发布的代码看起来，“BalanceFactor”的值始终为0. –

它是在插入项目中计算的。我会发布上面的代码。 – bananabreadbob

看看这段代码：

Node<T> oldRoot = tree; 
Node<T> newRoot = tree; 

newRoot.Right = oldRoot; 
oldRoot.Left = newRoot; 
newRoot.Right = oldRoot.Left;

和填充tree过的位置有可能。 ......这里有云：

tree.Right = tree; 
tree.Left = tree; 
tree.Right = tree.Left;

我相当肯定这是不是你想干什么。看看在wikipedia的AVL平衡算法。

来源

2014-01-27 22:31:51

AVL树向左和向右旋转C＃

回答

相关问题