平衡二元樹的判定

平衡二元樹具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二元樹，同時，平衡二元樹必定是二叉搜尋樹，反之則不一定。

平衡二元樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。紅黑樹是一種自平衡二元搜尋樹，是在計算機科學中用到的一種資料結構，典型的用途是實現關聯陣列。AVL是最先發明的自平衡二元搜尋樹演算法。Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的資料，即優先順序。伸展樹的優勢在於不需要記錄用於平衡樹的冗餘資訊。