課本源碼部分 第9章 查找 - 平衡二叉排序（搜索）樹 ——《數據結構》-嚴蔚敏.吳偉民版 源碼使用說明 鏈接☛☛☛ 《數據結構-C語言版》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明 課本源碼合輯 鏈接☛☛☛ 《數據結構》課本源碼合輯 習題集全解析 鏈接☛☛☛ 《數據結構題集》習題解析合輯 本 ...
課本源碼部分
第9章 查找 - 平衡二叉排序（搜索）樹
——《數據結構》-嚴蔚敏.吳偉民版
源碼使用說明 鏈接☛☛☛ 《數據結構-C語言版》（嚴蔚敏,吳偉民版）課本源碼+習題集解析使用說明
課本源碼合輯 鏈接☛☛☛ 《數據結構》課本源碼合輯
習題集全解析 鏈接☛☛☛ 《數據結構題集》習題解析合輯
本源碼引入的文件 鏈接☛ Base.c
相關測試數據下載 鏈接☛ 數據包
文檔中源碼及測試數據存放目錄：數據結構\▲課本演算法實現\▲09 查找\07 BalancedBinarySortTree
概述
平衡二叉排序（搜索）樹常被稱作平衡二叉樹（Balanced Binary Tree），簡稱為AVL樹（有別於AVL演算法）。
解析
一棵平衡二叉排序（搜索）樹或者是空樹，或者是具有下列性質的二叉排序樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為平衡二叉排序樹；
（4）沒有鍵值相等的結點。
（5）左子樹與右子樹的高度之差的絕對值小於等於1；（區別於普通二叉排序樹的地方）。
對於一般的二叉搜索樹，其期望高度（即為一棵平衡樹時）為log2n，其各操作的時間複雜度（O(log2n)）同時也由此而決定。但是，在某些極端的情況下（如在插入的序列是有序的時），二叉搜索樹將退化成近似鏈或鏈，此時，其操作的時間複雜度將退化成線性的，即O(n)。我們可以通過隨機化建立二叉搜索樹來儘量的避免這種情況，但是在進行了多次的操作之後，由於在刪除時，我們總是選擇將待刪除節點的後繼代替它本身，這樣就會造成總是右邊的節點數目減少，以至於樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間複雜度。
平衡二叉搜索樹（Balanced Binary Tree）具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O（log（n）），大大降低了操作的時間複雜度。
源碼
文件一 ☛ BalancedBinarySortTree.h
文件二 ☛ BalancedBinarySortTree.c
文件三 ☛ BalancedBinarySortTree-main.c （測試文檔）
文件四 ☛ TestData_Table.txt（查找表測試數據）
測試結果展示
