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＃

回答

相關問題