二叉排序樹(二叉排序樹平均查找長度)

什么是二叉排序樹

二叉排序樹（Binary Sort Tree），首先它是一棵樹，“二叉”這個描述已經(jīng)很明顯了，就是樹上的一根樹枝開兩個叉，于是遞歸下來就是二叉樹了（下圖所示），而這棵樹上的節(jié)點是已經(jīng)排好序的，具體的排序規(guī)則如下：

若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值

若右子樹不空，則右字數(shù)上所有節(jié)點的值均大于它的根節(jié)點的值

它的左、右子樹也分別為二叉排序數(shù)（遞歸定義）

從圖中可以看出，二叉排序樹組織數(shù)據(jù)時，用于查找是比較方便的，因為每次經(jīng)過一次節(jié)點時，最多可以減少一半的可能，不過極端情況會出現(xiàn)所有節(jié)點都位于同一側(cè)，直觀上看就是一條直線，那么這種查詢的效率就比較低了，因此需要對二叉樹左右子樹的高度進行平衡化處理，于是就有了平衡二叉樹（Balenced Binary Tree）

所謂“平衡”，說的是這棵樹的各個分支的高度是均勻的，它的左子樹和右子樹的高度之差絕對值小于1，這樣就不會出現(xiàn)一條支路特別長的情況。于是，在這樣的平衡樹中進行查找時，總共比較節(jié)點的次數(shù)不超過樹的高度，這就確保了查詢的效率（時間復(fù)雜度為O(logn)）

二叉排序樹定義

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數(shù)據(jù)結(jié)構(gòu)中的一類。在一般情況下，查詢效率比鏈表結(jié)構(gòu)要高。

定義一：

一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的結(jié)點。

定義二：

一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值；
（3）左、右子樹也分別為二叉排序樹。

定義三：

一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
（3）左、右子樹也分別為二叉排序樹；

【注】：以上的三種定義在不同的數(shù)據(jù)結(jié)構(gòu)教材中均有不同的定義方式 但是都是正確的 在開發(fā)時需要根據(jù)不 同的需求進行進行選擇。

插入刪除：
與次優(yōu)二叉樹相對，二叉排序樹是一種動態(tài)樹表。其特點是：樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當樹中不存在關(guān)鍵字等于給定值的結(jié)點時再進行插入。新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。

什么是二叉排序樹?

二叉排序樹要么是空二叉樹，要么具有如下特點：

二叉排序樹中，如果其根結(jié)點有左子樹，那么左子樹上所有結(jié)點的值都小于根結(jié)點的值；二叉排序樹中，如果其根結(jié)點有右子樹，那么右子樹上所有結(jié)點的值都大小根結(jié)點的值；二叉排序樹的左右子樹也要求都是二叉排序樹；

二叉樹排序

二叉排序樹就是中序遍歷之后是有序的；

構(gòu)造二叉排序樹步驟如下；

插入法構(gòu)造

第二個結(jié)點4比6來的小所以插入在6的左子樹；

第三個結(jié)點8比6來的大所以插入在6的右子樹；

第四個結(jié)點5比6來得小先進入左子樹然后跟4比較，

5比4大所以插入在4的右子樹；

以此類推將要插入的結(jié)點先跟根結(jié)點比較，比根結(jié)點大進入右子樹反之進入左子樹；

在跟進入的左子樹（右子樹）的結(jié)點比較方法同上；

直到?jīng)]有結(jié)點了 在插入； 你給的排序最后的二叉排序樹如下；

中序遍歷結(jié)果是 ： 3456789；

先序遍歷結(jié)果是：6435879；

【數(shù)據(jù)結(jié)構(gòu)】二叉排序樹(Binary Sort Tree)（建立、插入、刪除）

二叉排序樹(Binary Sort Tree) ，又稱 二叉查找樹 。它是一顆 空樹 ，或者具有下列性質(zhì)：

二叉排序樹的刪除操作相對復(fù)雜，因為不能因為刪除了結(jié)點，讓這顆二叉排序樹變得不滿足二叉排序樹的性質(zhì)，所以對于二叉排序樹的刪除存在三種情況：

將它的直接前驅(qū)或者直接后繼作為刪除結(jié)點的數(shù)據(jù)

對于二叉排序樹的建立，可以通過二叉排序樹的插入操作來實現(xiàn)。
通過中序遍歷二叉排序樹，結(jié)果是從小到大輸出。

二叉排序樹怎么構(gòu)造

假設(shè)二叉排序樹T為空，則創(chuàng)建一個keyword為k的結(jié)點。將其作為根結(jié)點。

否則將k和根結(jié)點的keyword進行比較，假設(shè)相等則返回，假設(shè)k小于根結(jié)點的keyword則插入根結(jié)點的左子樹中，否則插入根結(jié)點的右子樹中。

int InrtBST(BSTNode *p, KeyType k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
el if(k==p->key)
return 0;
el if(k<p->key)
return InrtBST(p->lchild, k);
el
return InrtBST(p->rchild, k);
}
二叉排序樹的生成算法：
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InrtBST(bt, A[i]);
i++;
}
return bt;
}

擴展資料：

在一般情況下，設(shè) P（n，i）為它的左子樹的結(jié)點個數(shù)為 i 時的平均查找長度。如圖的結(jié)點個數(shù)為 n = 6 且 i = 3; 則 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：這里 P(3)、P(2) 是具有 3 個結(jié)點、2 個結(jié)點的二叉分類樹的平均查找長度。 在一般情況，P（i）為具有 i 個結(jié)點二叉分類樹的平均查找長度。平均查找長度= 每個結(jié)點的深度的總和 / 總結(jié)點數(shù)。

參考資料來源：百度百科——二叉排序樹