歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

AVL樹-scala實現

二叉查找樹已經能夠很好的應用到應用程序中,但它們在最壞的情況下性能還是很糟糕。考慮到如圖所示這種情況: 查找操作的性能完全等同於線性。而AVL樹的查找操作,能夠保證無論怎麼構造它,運行時間一直對數級別的。一起來學習一下AVL樹吧。

什麼是AVL

AVL(Adelson-Velsky 和 Landis)樹,是帶有平衡條件的二叉查找樹,這個平衡條件必須要容易保持,並且它保證樹的深度是O(LogN).

一顆AVL樹是其每個節點的左右子樹節點高度最多差1的二叉查找樹。

平衡條件

我門上面說,一顆AVL樹是其每個節點的左右子樹節點高度最多差1的二叉查找樹。 左右子樹的高度最多差1便是AVL樹的平衡條件。

當進行插入操作時,我們需要更新通往根節點的所有節點的平衡信息。而插入操作隱含困難的原因在於,可能會破壞AVL樹的特性(例如,考慮將6插入到圖1的AVL樹中將會破壞節點為8的平衡條件)。如果發生這種情形,那麼就要考慮在插入完成之後重新回復節點的平衡信息。事實上,總可以通過對樹進行簡單的修正得到,我們稱其為旋轉(ratation).

在插入以後,只有那些從插入點到根節點的平衡條件可能變化,因為只有這些節點的字數可能發生變化。當我們沿著這條路路徑行進到根節點,可以發現一個節點它的新平衡破壞了AVL樹的特性。我們需要在這個節點重新平衡這棵樹。

我們把必須重新平衡的節點叫做α。因為平衡條件是高度最多相差1,那麼出現不平衡就是α點的高度相差為2。容易看出這種不平衡可能出現在下面這四種情況下:

  1. 對α的左兒子的左子樹進行一次插入
  2. 對α的左兒子的右子樹進行一次插入
  3. 對α的右兒子的左子樹進行一次插入
  4. 對α的右兒子的右子樹進行一次插入

1和4,2和3 是關於α點的鏡像對稱。因此理論上講只有兩種情況,當然編程上還是四種情況。

第一種情況是插入發生在外邊的情況(即左-左的情況或者右-右的情況),該情況是通過對樹的一次單旋轉來完成操作。

第二種情況是插入發生在內部的情形(即左-右的情況或者右-左的情況),該情況通過稍微復雜點的雙旋轉操作來處理。

單旋轉

下圖顯示了單旋轉如何調整情形1。旋轉前的圖在左邊,旋轉後的圖在右邊。

讓我們來分析具體的做法。節點K2不滿足平衡條件, 因為它的左子樹比右子樹深兩層(圖中的虛線表示樹的各層).

為使樹恢復平衡,我們把節點X向上移一層,並把Z像下移一層,為此我們重新安排節點以形成一顆等價的樹。如上圖的右邊部分。抽象的形容就是,把把樹想象成一棵柔軟靈活的樹,抓住子節點K1,閉上眼睛使勁的搖動它,這樣由於重力的作用,K1就變成了新的根。二叉樹的性質告訴我們,在原樹中K2>K1,這樣在新樹中,K2變成了K1的右兒子,Y變成了K2的左子樹,而X、Z依然是K1的左子樹和K2的右子樹。

讓我們演示一個更長的例子,假設從初始的空的AVL樹開始依次插入3、2、1,然後再依次插入4-7.

在插入關鍵字1的時候第一個問題就出現了,AVL性質在根處被破壞,我們在根和其左兒子之間施加單旋轉操作來修正問題。下圖是旋轉之前和之後的兩棵樹。

圖中虛線連接的兩個節點,它們是旋轉的主體。下面我們插入關鍵字4這沒有問題,在我們插入關鍵字5的時候,問題又出現了,平衡條件在關鍵字3處被破壞,而通過單旋轉再次將問題修復。

接下來插入6,平衡條件在根節點處被打破,因此我們在根處,在2、4之間施加一次單旋轉操作。

我們插入最後的關鍵字7,它導致另外的旋轉。

雙旋轉

單旋轉對情形2、3無效願因在於子樹Y太深。單旋轉沒有降低它的深度。

對於子樹Y我們可以假設他有一個根和兩棵子樹(對應上圖的K2、B、C)。

為了平衡期間,我們不能再把K3當成根了,而如上圖所示K3和K1之間旋轉又解決不了問題,唯一的選擇是把K2當成根,這迫K1成為K2的左子樹,K3成為K1的右子樹,而K2的左子樹成為K1的右子樹,K2的右子樹成為K3的左子樹。容易看出最後得到的樹滿足AVL樹的特征。

我們繼續在前面例子的基礎上以倒序插入10-16,接著插入8,再插入9.插入16很容易這並不破壞樹的平衡,插入15會引起節點7處的高度不平衡,這屬於情形3,需要通過右-左雙旋轉來解決。如圖:

下面我們來插入14,它也需要一個雙旋轉。此時修復樹的旋轉還是右-左雙旋轉

如果現在插入13那麼在根處就會出現不平衡,由於13不在4-7之間,我們知道只要一次單旋轉就行.

插入12也需要一次雙旋轉

插入11、10都需要進行單旋轉,接著我們插入8不需要進行旋轉,這樣就建成了一顆近乎理想的平衡樹

最後我們插入9,在節點10發生不平衡,這裡滿足情形2,對左兒子的右子樹進行一次,需要一次雙旋轉。

總結

現在讓我們對上面的討論做出總結,除幾種情形外,編程的細節是相當簡單的。為將節點X插入AVL樹T中,我們遞歸的將X插入到T的子樹中。如果子樹的高度不變,那麼插入完成;如果出現高度不平衡,那麼找到不平衡點,做適當的單旋轉或者雙旋轉,更新這些高度,從而完成插入。

scala實現

sealed traitAVLTree[+A] extends Serializable {
  defbalance: Int

  defdepth: Int

  defcontains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean

  definsert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B]


  defrebalance[B >: A]: AVLTree[B]

}

/**
 * 葉子節點
 */
case objectLeafextendsAVLTree[Nothing] {

  override valbalance: Int = -1
  override valdepth: Int = 0

  override defcontains[B >: Nothing](x: B)(implicit ordering: Ordering[B]): Boolean = false



  override definsert[B >: Nothing](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
    Node(x, Leaf, Leaf)
  }


  override defrebalance[B >: Nothing]: AVLTree[B] = this

}

case classNode[A](value: A, left: AVLTree[A], right: AVLTree[A]) extends AVLTree[A] {
  override defbalance: Int = right.depth - left.depth

  override defdepth: Int = math.max(left.depth, right.depth)

  override defcontains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean = ???

  override definsert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
    valcmp = ordering.compare(x,value)
    if (cmp < 0){
      Node(value, left.insert(x),right).rebalance
    } else if (cmp > 0){
      Node(value, left, right.insert(x)).rebalance
    } else {
      this
    }
  }

  override defrebalance[B >: A]  = {
    if (-2 == balance){
      if (1 == left.balance){
        doubleRightRotation
      } else {
        rightRotation
      }
    } else if(2 == balance) {
      if (-1 == right.balance){
        doubleLeftRotation
      }else {
        leftRotation
      }
    } else {
      this
    }
  }


  /*
   *   5
   *    \                                  6
   *     6       ---- 左單旋轉 --->        /  \
   *      \                              5   7
   *       7
   *
   *   在節點5 發生不平衡 5的右節點成為新的根節點
   */
  private defleftRotation[B >: A] = {
    if (Leaf != right) {
      valr = right.asInstanceOf[Node[A]]
      Node(r.value, Node(value, left, r.left), r.right)
    } else {
      sys.error("should not happen.")
    }
  }


  /*
   *           7
   *          /                                6
   *         6    ---- 右單旋轉 --->           /  \
   *        /                                5   7
   *       5
   *
   *    在節點7 發生不平衡 7的左節點成為新的根節點
   */
  private defrightRotation[B >: A] = {
    if (Leaf != left) {
      vall = left.asInstanceOf[Node[A]]
      Node(l.value, l.left, Node(value, l.right, right))
    } else {
      sys.error("should not happen.")
    }

  }

  /*
   *     左雙旋轉
   *
   *     5                           5
   *       \                          \                     6
   *        7    ----step1 --->        6    ---step2--->   / \
   *       /                            \                 5   7
   *      6                              7
   *
   *  在節點5處不平衡
   *  step1 : 節點5的右節點 做一次 右旋轉
   *  step2 : 左旋轉
   *
   */
  private defdoubleLeftRotation[B >: A] = {
    if (Leaf != right) {
      valr = right.asInstanceOf[Node[A]]
      valrightRotated = r.rightRotation
      Node(rightRotated.value, Node(value, left, rightRotated.left), rightRotated.right)
    } else {
      sys.error("should not happen.")
    }
  }

  /*
  *   右雙旋轉
  *
  *     7                            7
  *    /                            /                   6
  *   5       ----step1 --->       6    ---step2--->   / \
  *    \                          /                   5   7
  *     6                        5
  *
  *  在節點7處不平衡
  *  step1 : 節點7的左節點 做一次 左旋轉
  *  step2 : 右旋轉
  *
  */
  private defdoubleRightRotation[B >: A] = {
    if (Leaf != left) {
      vall: Node[A] = left.asInstanceOf[Node[A]]
      valleftRotated = l.leftRotation
      Node(leftRotated.value, leftRotated.left, Node(value, leftRotated.right, right))
    } else sys.error("Should not happen.")
  }

參考資料

《數據結構與算法分析java語言描述》 http://www.linuxidc.com/Linux/2014-04/99735.htm

Copyright © Linux教程網 All Rights Reserved