使用替罪羊樹進行平衡會比傳統的平衡樹更有效的情況通常包括以下幾種情況：

1. **高度不平衡的操作路徑**：在一些應用中，資料的插入和刪除可能會集中在某些特定的區域，導致平衡樹的高度不平衡，而替罪羊樹通過部分重建的方式，可以較好地應對這種不平衡。替罪羊樹會檢查操作路徑中最高的滿足平衡因子的節點並重建子樹，這樣可以更有效地回應因為大量操作集中在某一部分而造成的不平衡。

2. **經常發生的批量操作**：當系統中有頻繁的批量插入或刪除操作時，替罪羊樹允許在整體運行過程中定期進行重建，這意味著每次重建只需處理影響的子樹，可以有效減少頻繁調整整個樹的成本。

3. **不需要嚴格的平衡**：替罪羊樹不要求和傳統平衡樹一樣嚴格保持高度差，因此有時候在效率需求相對較高的環境中，替罪羊樹能提供更穩定的性能，特別是在高頻率的查詢和更新操作之下。

4. **記憶成本不高**：因為替罪羊樹的重建是基於當前樹結構的部分重建，且不需要頻繁地儲存和更新每個節點的額外數據（如平衡因子等），在空間效率上可能更優於某些傳統平衡樹。

總的來說，在動態變化頻繁且不平衡的環境下，替罪羊樹提供了一種靈活且有效的方式來保持樹的平衡，相對於傳統的平衡樹來說，可以更快速地適應變化。
在什麼情況下，使用替罪羊樹的方式進行平衡會比傳統的平衡樹更有效？
**平衡樹**是電腦科學中的一類資料結構，為改進的二元搜尋樹。一般的二元搜尋樹的查詢複雜度取決於目標結點到樹根的距離（即深度），因此當結點的深度普遍較大時，查詢的均攤複雜度會上升。為了實現更高效的查詢，產生了**平衡樹**。

在這裡，平衡指所有葉子的深度趨於平衡，更廣義的是指在樹上所有可能尋找的均攤複雜度偏低。

## 基本操作

旋轉（rotate）：幾乎所有平衡樹的操作都基於樹旋轉操作（也有部分基於重構，如替罪羊樹），通過旋轉操作可以使得樹趨於平衡。對一棵尋找樹（search tree）進行查詢、新增、刪除等動作，所花的時間與樹的高度 h 成比例，並不與樹的容量 n 成比例。如果可以讓樹維持平衡，也就是讓 h 維持在 $O(\log {n})$ 的左右，就可以在 $O(\log {n})$ 的複雜度內完成各種基本操作。

插入（insert）：在樹中插入一個新值。

刪除（delete）：在樹中刪除一個值。

查詢前驅（predecessor）：前驅定義為小於 _x_，且最大的數。

查詢後繼（successor）：後繼定義為大於 _x_，且最小的數。

在維護節點大小（size）後，可以支援以下操作：

查詢排名（rank）：排名定義為比 x 小的數的個數加一。

查詢第 k 大：即排名為 _k_ 的數。

## 各種平衡樹

* AVL 樹：是最早被發明的自平衡二元搜尋樹。在 AVL 樹中，任一節點對應的兩棵子樹的最大高度差為 1，因此它也被稱為高度平衡樹。尋找、插入和刪除在平均和最壞情況下的時間複雜度都是 $O(\log {n})$ 。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。AVL 樹得名於它的發明者 G. M. Adelson-Velsky 和 Evgenii Landis，他們在 1962 年的論文 _An algorithm for the organization of information_ 中公開了這一資料結構。 節點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子 1、0 或 -1 的節點被認為是平衡的。帶有平衡因子 -2 或 2 的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接儲存在每個節點中，或從可能儲存在節點中的子樹高度計算出來。
* 樹堆（Treap）：是有一個隨機附加域滿足堆的性質的二元搜尋樹，其結構相當於以亂數據插入的二元搜尋樹。其基本操作的期望時間複雜度為 $O(\log {n})$ 。相對於其他的平衡二元搜尋樹，Treap 的特點是實現簡單，且能基本實現隨機平衡的結構。
* 伸展樹（Splay tree）：能在均攤 $O(\log {n})$ 的時間內完成基於伸展（Splay）操作的插入、尋找、修改和刪除操作。它是由丹尼爾・斯立特（Daniel Sleator）和羅伯特・塔揚在 1985 年發明的。在伸展樹上的一般操作都基於伸展操作：假設想要對一個二元搜尋樹執行一系列的尋找操作，為了使整個尋找時間更小，被查頻率高的那些條目就應當經常處於靠近樹根的位置。於是想到設計一個簡單方法，在每次尋找之後對樹進行調整，把被尋找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二元搜尋樹，它會沿著從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。 它的優勢在於不需要記錄用於平衡樹的冗餘資訊。
* 紅黑樹 （Red–black tree）：在 1972 年由魯道夫・貝爾發明，被稱為 "**對稱二元 B 樹**"，它現代的名字源於 Leo J. Guibas 和 Robert Sedgewick 於 1978 年寫的一篇論文。紅黑樹的結構複雜，但它的操作有著良好的最壞情況執行時間，並且在實踐中高效：它可以在 $O(\log {n})$ 時間內完成尋找，插入和刪除，這裡的 n 是樹中元素的數目。
* 加權平衡樹（Weight balanced tree）：加權平衡樹的每個結點儲存這個結點下子樹的大小，可以用來實現順序統計樹操作。優勢在於占用空間相對較小。
* 2-3 樹：其內部節點（存在子節點的節點）要麼有 2 個孩子和 1 個資料元素，要麼有 3 個孩子和 2 個資料元素，葉子節點沒有孩子，並且有 1 個或 2 個資料元素。2–3 樹和 AA 樹是等距同構的，換句話說，對於每個 2–3 樹，都至少有 1 個 AA 樹和它的元素排列是相同的。
* AA 樹：AA 樹是紅黑樹的一種變種，是 Arne Andersson 教授在 1993 年年在他的論文 "Balanced search trees made simple" 中介紹，設計的目的是減少紅黑樹考慮的不同情況，區別於紅黑樹的是，AA 樹的紅節點只能作為右葉子，從而大大簡化了維護 2-3 樹的類比。
* 替罪羊樹：其平衡基於部分重建，在非平衡的二元搜尋樹中，每次操作以後檢查操作路徑，找到最高的滿足左右子樹大小大於平衡因子（alpha）乘以自身大小的結點，重建整個子樹。這樣就得到了替罪羊樹，而被重建的子樹的原來的根就被稱為替罪羊節點。

## 其他類型

以下資料結構支援平衡樹大多數操作，但實現有根本不同:

* 跳表
* 有序向量
* 值域線段樹
* 數字搜尋樹（DigitalSearchTree）

## 應用

用於表示有序的線性資料結構，如優先佇列、關聯陣列、鍵 (key)- 值 (value) 的對映等。自平衡的二元搜尋樹與雜湊表的相比，各有優缺。平衡樹在按序遍歷所有鍵值時是量級最佳的，雜湊表不能。自平衡二元搜尋樹在尋找一個鍵值時，最壞情況下時間複雜度優於雜湊表， $O(\log n)$ 對比 $O(n)$ ；但平均時間複雜度遜於 hash 表， $O(\log n)$ 對比 $O(1)$ 。

平衡樹的排序方法，雖然在平均時間複雜度上也是 $O(n\log n)$ ，但由於 cache 效能、樹的調整操作等，效能上不如快速排序、堆積排序、合併排序等同為 $O(n\log n)$ 複雜度的排序。

## 參考文獻

## 外部連結

* Dictionary of Algorithms and Data Structures: Height-balanced binary search tree （頁面存檔備份，存於網際網路檔案館）
* GNU libavl （頁面存檔備份，存於網際網路檔案館）, a LGPL-licensed library of binary tree implementations in C, with documentation
**平衡樹**是電腦科學中的一類資料結構，為改進的二元搜尋樹。一般的二元搜尋樹的查詢複雜度取決於目標結點到樹根的距離（即深度），因此當結點的深度普遍較大時，查詢的均攤複雜度會上升。為了實現更高效的查詢，產生了**平衡樹**。

在這裡，平衡指所有葉子的深度趨於平衡，更廣義的是指在樹上所有可能尋找的均攤複雜度偏低。

## 基本操作

旋轉（rotate）：幾乎所有平衡樹的操作都基於樹旋轉操作（也有部分基於重構，如替罪羊樹），通過旋轉操作可以使得樹趨於平衡。對一棵尋找樹（search tree）進行查詢、新增、刪除等動作，所花的時間與樹的高度 h 成比例，並不與樹的容量 n 成比例。如果可以讓樹維持平衡，也就是讓 h 維持在 $O(\log {n})$ 的左右，就可以在 $O(\log {n})$ 的複雜度內完成各種基本操作。

插入（insert）：在樹中插入一個新值。

刪除（delete）：在樹中刪除一個值。

查詢前驅（predecessor）：前驅定義為小於 _x_，且最大的數。

查詢後繼（successor）：後繼定義為大於 _x_，且最小的數。

在維護節點大小（size）後，可以支援以下操作：

查詢排名（rank）：排名定義為比 x 小的數的個數加一。

查詢第 k 大：即排名為 _k_ 的數。 **平衡二元搜尋樹**（英語：Balanced Binary Search Tree）是一種結構平衡的二元搜尋樹，它是一種每個節點的左右兩子樹高度差都不超過 1 的二元樹。它能在 O ( $\log n$ ) 內完成插入、尋找和刪除操作，最早被發明的平衡二元搜尋樹爲 AVL 樹。

常見的平衡二元搜尋樹有：

* AVL 樹
* 紅黑樹
* Treap
* 節點大小平衡樹 ## 描述

加權平衡樹是一種儲存子樹大小的二元搜尋樹。那就是說，一個結點包含以下欄位：

* 鍵（_key_），任何可排序的類型
* 值（_value_，可選，只作對映作用）
* 左子樹（_left_），右子樹（_right_），結點的指標
* 大小（_size_），整數類型

從定義上來說，樹上葉子（沒有子結點的元素）的大小（典型地用一個空指標表示）是 0。一個內部結點的大小是它的兩棵子樹的大小，再加一
（size[n] = size[n.left] + size[n.right] + 1）。一個結點的權重取決於它的大小或者等於它的大小，或 weight[n] = size[n] + 1。

修改樹的操作必須使用與 AVL 樹中相同的操作來保證左子樹和右子樹的大小相互存在某種內在因子 α，也就是旋轉和兩次選擇。形式上來說，結點平衡操作如下定義： 在電腦科學裡面，**加權平衡樹**（**WBTs**）是一種可以用來實現集合、字典（對映）和序列的平衡樹。這些樹結構在 20 世紀 70 年代被 Nievergelt 和 Reingold 作為**有界限的自平衡樹**或 **BB [α] 樹**提出。讓這些結構普及的是高德納。

就像其他自平衡樹一樣，加權平衡樹儲存的帳簿資訊可以在樹結構被插入和刪除操作打亂時，通過平衡結點和操作樹旋轉來使樹結構重新達到平衡。特別的地方是，加權平衡樹的每個結點儲存這個結點下子樹的大小，並且這個結點左右子樹的大小保持著某種內在聯絡。不同於 AVL 樹（儲存子樹的高度）和紅黑樹（儲存虛構的「顏色」位），加權平衡樹儲存記帳資訊的方式是對應用真正有用的屬性：一棵樹下元素的數量等於它的根的大小，然而這個根的大小是一個用來實現順序統計樹操作的有用資料，也就是說，可以得到一個大小為 n 的集合下的最大元素或者決定一個順序結構下一個元素的索引。

加權平衡樹在函式程式語言社群下面非常受歡迎以及被用來實現 MIT Scheme 的集合和對映結構還有 Haskell 語言的實現。