平衡二叉樹簡介

平衡二叉搜尋樹（Self-balancing binary search tree）又被稱為AVL樹（有别于AVL算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

平衡二叉樹的常用實作方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。 最小二叉平衡樹的節點總數的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數列，可以參考Fibonacci(斐波那契)數列，1是根節點，F(n-1)是左子樹的節點數量，F(n-2)是右子樹的節點數量。

image

平衡二叉樹主要使用在資料的搜尋查詢中，二叉樹支援動态的插入和查找，保證操作在O(height)時間，平衡二叉樹的相關實作算法的應用：

AVL樹:最早的平衡二叉樹之一。應用相對其他資料結構比較少。windows對程序位址空間的管理用到了AVL樹

紅黑樹:平衡二叉樹，廣泛用在C++的STL中。map和set都是用紅黑樹實作的。我們熟悉的STL的map容器底層是RBtree,當然指的不是unordered_map,後者是hash。

B/B+樹用在磁盤檔案組織 資料索引和資料庫索引

Trie樹 字典樹，用在統計和排序大量字元串

幾種平衡二叉樹實作算法的簡介：

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是複雜的，但它的操作有着良好的最壞情況運作時間，并且在實踐中是高效的: 它可以在O(log n)時間内做查找，插入和删除，這裡的n是樹中元素的數目。

AVL是最先發明的自平衡二叉查找樹算法。在AVL中任何節點的兩個兒子子樹的高度最大差别為一，是以它也被稱為高度平衡樹，n個結點的AVL樹最大深度約1.44log2n。

查找、插入和删除在平均和最壞情況下都是O（log n）。增加和删除可能需要通過一次或多次樹旋轉來重新平衡這個樹。

Treap是一棵二叉排序樹，它的左子樹和右子樹分别是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的資料，就是優先級。

Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這裡我們假設節點的優先級大于該節點的孩子的優先級)。但是這裡要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap并不一定是。

伸展樹（Splay Tree）是一種二叉排序樹，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan創造。它的優勢在于不需要記錄用于平衡樹的備援資訊。在伸展樹上的一般操作都基于伸展操作。

Size Balanced Tree（簡稱SBT）是一自平衡二叉查找樹，是在計算機科學中用到的一種資料結構。它是由中國廣東中山紀念中學的陳啟峰發明的。

陳啟峰于2006年底完成論文《Size Balanced Tree》，并在2007年的全國青少年資訊學奧林匹克競賽冬令營中發表。由于SBT的拼寫很容易找到中文諧音，它常被中國的資訊學競賽選手和ACM/ICPC選手們戲稱為“傻B樹”、“Super BT”等。

相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易于實作。據陳啟峰在論文中稱，SBT是“目前為止速度最快的進階二叉搜尋樹”。SBT能在O(log n)的時間内完成所有二叉搜尋樹（BST）的相關操作，而與普通二叉搜尋樹相比，SBT僅僅加入了簡潔的核心操作Maintain。

由于SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很友善地實作動态順序統計中的select和rank操作。

平衡二叉樹的實作比較複雜，這篇文章就當科普一下平衡二叉樹的概念，向往算法工程師發展的可以繼續深入。