演算法與資料結構(五)樹表的查詢
*樹表的查詢*
(1)二叉排序樹
(2)二叉排序樹的操作——查詢
(3) 二叉排序樹的操作——插入
(4) 二叉排序樹的操作——生成
(5) 二叉排序樹的操作——刪除
(1)二叉排序樹
由於線性表的查詢更適合於靜態查詢表,若要對動態查詢表進行高效率的查詢,可採用二叉樹作為查詢表的組織形式,將其統稱為樹表。
二叉排序樹又稱二叉查詢樹,是一種對排序和查詢都很有用的特殊二叉樹。該表結構在查詢過程中動態生成,對於給定值key 若表中存在,則成功返回; 否則插入關鍵字等於key 的記錄。
二叉排序樹或是空樹,或是滿足如下性質的二叉樹:
(1)若其左子樹非空,則左子樹上所有結點的值均小於根結點的值;
(2)若其右子樹非空,則右子樹上所有結點的值均大於等於根結點的值;
(3)其左右子樹本身又各是一棵二叉排序樹。
☆ 中序遍歷二叉排序樹後的結果有什麼規律?
答:得到一個關鍵字的遞增有序序列
(2)二叉排序樹的操作——查詢
若查詢的關鍵字等於根結點,成功 否則 若小於根結點,查其左子樹 若大於根結點,查其右子樹 在左右子樹上的操作類似。
演算法思想:
(1)若二叉排序樹為空,則查詢失敗,返回空指標。
(2)若二叉排序樹非空,將給定值key與根結點的關鍵字T->data.key進行比較:
① 若key等於T->data.key,則查詢成功,返回根結點地址;
② 若key小於T->data.key,則進一步查詢左子樹;
③ 若key大於T->data.key,則進一步查詢右子樹。
程式碼:
1 BSTree SearchBST(BSTree T,KeyType key) { 2if((!T) || key==T->data.key) return T; 3else if (key<T->data.key)return SearchBST(T->lchild,key); 4//在左子樹中繼續查詢 5else return SearchBST(T->rchild,key); 6//在右子樹中繼續查詢 7 } // SearchBST
(3) 二叉排序樹的操作——插入
若二叉排序樹為空,則插入結點應為根結點 否則,繼續在其左、右子樹上查詢 樹中已有,不再插入 樹中沒有,查詢直至某個葉子結點的左子樹或右子樹為空為止,則插入結點應為該葉子結點的左孩子或右孩子
插入的元素一定在葉結點上
例:插入結點20:
(4) 二叉排序樹的操作——生成
從空樹出發,經過一系列的查詢、插入操作之後,可生成一棵二叉排序樹。
注意:不同插入次序的序列生成不同形態的二叉排序樹
查詢效能分析:
第i層結點需比較i次。在等概率的前提下,上述兩圖的平均查詢長度為:
總結:
平均查詢長度和二叉樹的形態有關,即:
最好:log2n(形態勻稱,與二分查詢的判定樹相似)
最壞: (n+1)/2(單支樹)
(5)二叉排序樹的操作——刪除
將因刪除結點而斷開的二叉連結串列重新連結起來,並且儘可能地防止重新連結後樹的高度增加。
刪除葉結點: 只需將其雙親結點指向它的指標清零,再釋放它即可。
被刪結點缺右子樹: 可以拿它的左子女結點頂替它的位置,再釋放它。
被刪結點缺左子樹: 可以拿它的右子女結點頂替它的位置,再釋放它。
被刪結點左、右子樹都存在: 可以在它的右子樹中尋找中序下的第一個結點(關鍵碼最小),或者左子樹中定址中序下的最後一個結點(關鍵碼最大),用它的值填補到被刪結點中,再來處理這個結點的刪除問題。