定義：
平衡二叉樹（Balanced Binary Tree），這個性質(zhì)辨萍，在數(shù)據(jù)結構的發(fā)展中出現(xiàn)了幾種平衡二叉樹近忙。
均具有以下性質(zhì)：
它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1骄酗，并且左右兩個子樹都是一棵平衡二叉樹。
構造與調(diào)整方法 平衡二叉樹的常用算法有紅黑樹邦邦、AVL安吁、Treap等。
最小二叉平衡樹的節(jié)點的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數(shù)列燃辖，
可以參考Fibonacci數(shù)列鬼店，1是根節(jié)點，F(xiàn)(n-1)是左子樹的節(jié)點數(shù)量郭赐，
F(n-2)是右子樹的節(jié)點數(shù)量
一般的二叉搜索樹（Binary Search Tree）薪韩，其期望高度（即為一棵平衡樹時）為log2n，
其各操作的時間復雜度（O(log2n)）同時也由此而決定捌锭。
但是俘陷，在某些極端的情況下（如在插入的序列是有序的時），二叉搜索樹將退化成近似鏈或鏈观谦，
此時拉盾，其操作的時間復雜度將退化成線性的，即O(n)豁状。
我們可以通過隨機的建立二叉搜索樹來盡量的避免這種情況捉偏，但是在進行了多次的操作之后倒得，
由于在刪除時，
我們總是選擇將待刪除節(jié)點的后繼代替它本身夭禽，這樣就會造成總是右邊的節(jié)點數(shù)目減少霞掺，
以至于樹向左偏沉。這同時也會造成樹的平衡性受到破壞讹躯，
提高它的操作的時間復雜的菩彬。
分類：
目前幾種被使用的較為廣泛的是：
紅黑樹
紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數(shù)據(jù)結構潮梯，典型的用途是實現(xiàn)關聯(lián)數(shù)組骗灶。
它是在1972年由Rudolf Bayer發(fā)明的，他稱之為"對稱二叉B樹"秉馏，它現(xiàn)代的名字是在 Leo J. Guibas 和
Robert Sedgewick 于1978年寫的一篇論文中獲得的耙旦。它是復雜的，但它的操作有著良好的最壞情況運行時間萝究，
并且在實踐中是高效的: 它可以在O(log n)時間內(nèi)做查找免都，插入和刪除，這里的n是樹中元素的數(shù)目帆竹。
AVL樹
AVL是最先發(fā)明的自平衡二叉查找樹算法琴昆。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為一，
所以它也被稱為高度平衡樹馆揉，n個結點的AVL樹最大深度約1.44log2n。查找抖拦、插入和刪除在平均和
最壞情況下都是O（log n）升酣。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。
Treap
Treap是一棵二叉排序樹态罪，它的左子樹和右子樹分別是一個Treap噩茄，和一般的二叉排序樹不同的是，
Treap紀錄一個額外的數(shù)據(jù)复颈，就是優(yōu)先級绩聘。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆
的性質(zhì)(在這里我們假設節(jié)點的優(yōu)先級大于該節(jié)點的孩子的優(yōu)先級)耗啦。但是這里要注意的是Treap和
二叉堆有一點不同凿菩，就是二叉堆必須是完全二叉樹，而Treap并不一定是帜讲。
伸展樹
伸展樹（Splay Tree）是一種二叉排序樹衅谷，它能在O(log n)內(nèi)完成插入、查找和刪除操作似将。
它由Daniel Sleator和Robert Tarjan創(chuàng)造获黔。它的優(yōu)勢在于不需要記錄用于平衡樹的冗余信息蚀苛。
在伸展樹上的一般操作都基于伸展操作。
SBT
Size Balanced Tree（簡稱SBT）是一自平衡二叉查找樹玷氏，是在計算機科學中用到的一種數(shù)據(jù)結構堵未。
它是由中國廣東中山紀念中學的陳啟峰發(fā)明的。陳啟峰于2006年底完成論文《Size Balanced Tree》盏触，
并在2007年的全國青少年信息學奧林匹克競賽冬令營中發(fā)表渗蟹。由于SBT的拼寫很容易找到中文諧音，
它常被中國的信息學競賽選手ACM選手們戲稱為“傻B樹”耻陕、“Super BT”等拙徽。相比紅黑樹、
AVL樹等自平衡二叉查找樹诗宣，SBT更易于實現(xiàn)膘怕。據(jù)陳啟峰在論文中稱，SBT是“目前為止速度最快的
高級二叉搜索樹”召庞。SBT能在O(log n)的時間內(nèi)完成所有二叉搜索樹（BST）的相關操作岛心，
而與普通二叉搜索樹相比，SBT僅僅加入了簡潔的核心操作Maintain篮灼。由于SBT賴以保持平衡的是size域
而不是其他“無用”的域忘古，它可以很方便地實現(xiàn)動態(tài)順序統(tǒng)計中的select和rank操作。
小編推薦一個學C語言/C++的學習裙【 六二六诅诱，八七一髓堪，九一六? 】邀請碼凌云，無論你是大牛還是小白娘荡，是想轉(zhuǎn)行還是想入行都可以來了解一起進步一起學習干旁！裙內(nèi)有開發(fā)工具，很多干貨和技術資料分享炮沐！
