二叉搜索樹（Binary Search Tree ）的定義及分析

定義：

二叉搜索樹或者是一棵空樹，或者是具有下列性質的二叉樹：

1. 每個結點都有一個作為搜索依據的關鍵碼(key)，所有結點的關鍵碼互不相同。
2. 左子樹（如果非空）上所有結點的關鍵碼都小於根結點的關鍵碼。
3. 右子樹（如果非空）上所有結點的關鍵碼都大於根結點的關鍵碼。
4. 左子樹和右子樹也是二叉搜索樹。
5. 結點左子樹上所有關鍵碼小於結點關鍵碼；
6. 右子樹上所有關鍵碼大於結點關鍵碼；
7. 若從根結點到某個葉結點有一條路徑，路徑左邊的結點的關鍵碼不一定小於路徑上的結點的關鍵碼。
8. 如果對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結點關鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。 下圖為二叉搜索樹的一個圖

二叉搜索樹時一個用於查找操作的搞笑數據結構，因為在最壞的情況下只要查找其中一個分支上的數據就可以了。復雜度為O（nlg n），n為二叉樹元素的個數。所以在實際使用中，盡可能的保證二叉樹的平衡，這樣對搜索來說是最高效的。

二叉樹的實現和分析

前面提到，只有當二叉樹搜索樹保持平衡時對搜索來說才是最高效的，如何保持平衡，實際上很難得。在實際運用中使用最多的就是AVL樹，專門在百度百科上專門搜索了下。下面是概述：

********************************************************************************

概述

在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。AVL樹得名於它的發明者 G.M. Adelson-Velsky 和 E.M. Landis，他們在 1962 年的論文 "An algorithm for the organization of information" 中發表了它。

AVL 節點數計算

高度為 h 的 AVL 樹，節點數 N 最多2^h − 1； 最少 （其中）。

最少節點數 n 如以費伯納西數列可以用數學歸納法證明：

Nh= F【h+ 2】 - 1 (F【h+ 2】是 Fibonacci polynomial 的第h+2個數）。

即：

N0 = 0 （表示 AVL Tree 高度為0的節點總數）

N1 = 1 （表示 AVL Tree 高度為1的節點總數）

N2 = 2 （表示 AVL Tree 高度為2的節點總數）

Nh= N【h− 1】 + N【h− 2】 + 1 （表示 AVL Tree 高度為h的節點總數）

換句話說，當節點數為 N 時，高度 h 最多為。

節點的平衡因子是它的右子樹的高度減去它的左子樹的高度。帶有平衡因子 1、0 或 -1 的節點被認為是平衡的。帶有平衡因子 -2 或 2 的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。

操作

AVL樹的基本操作一般涉及運做同在不平衡的二叉查找樹所運做的同樣的算法。但是要進行預先或隨後做一次或多次所謂的"AVL 旋轉"。