嚴格平衡二叉排序樹類屬類_平均查找長度

1、嚴格平衡二叉排序樹類屬類嚴格平衡二叉排序樹類屬類_平均查找長度平均查找長度作者在文獻[1]中提出了二叉樹結(jié)點的嚴格平衡因子、嚴格平衡二叉樹和嚴格平衡二叉排序樹的概念，證明了嚴格平衡二叉樹的平衡性態(tài)優(yōu)于傳統(tǒng)的平衡二叉樹；嚴格平衡二叉排序樹的查找時間復(fù)雜度優(yōu)于傳統(tǒng)的平衡二叉排序樹。該文提出的構(gòu)造嚴格平衡二叉排序樹的算法以及插入、刪除元素時二叉排序樹的嚴格平衡化過程與傳統(tǒng)的相應(yīng)算法相比較，具有更簡單和自然的優(yōu)點。本文將對文獻[1]中提出的嚴格

2、平衡二叉排序樹的查找時間復(fù)雜度問題進行詳細分析并對其漸近性態(tài)的誤差作出估計。嚴格平衡二叉排序樹是最優(yōu)的二叉排序樹，并且插入、刪除元素又十分方便，因此它非常適合于作為動態(tài)查找表的存貯結(jié)構(gòu)。本文應(yīng)用C語言的模板機制，給出嚴格平衡二叉排序樹類屬類的總體設(shè)計和主要成員函數(shù)的詳細設(shè)計，希望為文獻[4]中給出的標準模板類庫提供新的模板類。本文下面的敘述中，術(shù)語嚴格平衡二叉排序樹通常用SBBST表示，特別是在標題中。2SBBST查找時間復(fù)雜度分析2.

3、1SBBST平均查找長度的計算公式文獻[1]提出了等概率情況下平均查找長度的計算問題，下面的定理1給出了由嚴格平衡二叉排序樹的結(jié)點個數(shù)計算其平均查找長度的公式。定理1設(shè)嚴格平衡二叉排序樹的結(jié)點個數(shù)為n，則其平均查將代入(5)即得定理1得證。推論1若嚴格平衡二叉排序樹的結(jié)點個數(shù)n=2k1(k=123)則其平均查找長度ASL(n)的計算公式為證明當n=2k1(k=123)時，所以推論1得證。文獻[2]中給出的靜態(tài)查找表二分查找的計算公式與推