二叉平衡排序樹的查找演算法

① 數據結構 簡單演算法實現在二叉排序樹上查找關鍵值k

如果用C語言，應該要寫成這樣:
typedef
struct
node{int
key;
struct
node
*lchild;
struct
node
*rchild;}bitree;
bitree
*bstsearch(bitree
*t,
int
k)
{
if
(t==NULL
)
//這里t是一個指針，是不能跟0判等的，要和空指針判等
{
return(NULL);//如果t是空指針，表示數是空數，不存在關鍵值key
}
else
{
while
(t!=NULL)//要循環遍歷整個樹，尋找關鍵值key
{
if
(t->key==k)
//如果找到了關鍵值key，則返回節點指針t
return(t);
else
if
(t->key>k)
//因為是排序樹，則有對於任意節點，左孩子小於根小於右孩子
t=t->lchild;
//所以如果當前節點的key大於輸入值，則搜索左子樹，否則右子樹
else
t=t->rchild_;
}
return
NULL;//這里要加這個，如果搜索不到的話要返回空指針
}
}

② 題目3． 平衡二叉樹演算法查找樹中某節點的時間復雜度是多少

平均查找的時間復雜度為O(log n)。

平衡樹的查找過程和排序樹的相同。在查找過程中和給定值進行比較關鍵字個數不超過樹的深度。

如果二叉樹的元素個數為n，那麼不管是對樹進行插入節點、查找、刪除節點都是log(n)次循環調用就可以了。它的時間復雜度相對於其他數據結構如數組等是最優的。

是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。

(2)二叉平衡排序樹的查找演算法擴展閱讀：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

(1)空二叉樹——(a)

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

③ 計算機考研：數據結構常用演算法解析(8)

第九章 查找
查找分成靜態查找和動態查找，靜態查找只是找，返回查找位置。而動態查找則不同，若查找成功，返回位置，若查找不成功，則要返回新記錄的插入位置。也就是說，靜態查找不改變查找表，而動態查找則會有插入操作，會改變查找表的。
不同的查找所採用的存儲結構也不同，靜態查找採用順序表，而動碼遲態查找由於經常變動，所以用二叉排序樹，二叉平衡樹、B-和B+。
靜態查找有，順序查找，折半查找，分塊查找(索引順序查找)
順序查找(Sequential Search)是最簡單的一種查找方法。
演算法思路
設給定值為k，在表(R1 R2……Rn)中，從Rn即最後一個元素開始，查找key=k的記錄。若存在一個記錄Ri(l≤i≤n)的key為k，則查找成功，返回記錄序號i;否則，查找失敗，返回0。
演算法描述
int sqsearch(sqlist r,keytype k) //對表r順序查找的演算法//
{ int i;
r.data[0].key=k; //k存入監視哨//
i=r.len; //取表長//
while(r.data[i].key!=k)
i--; //順序查找//
return(i);
}
演算法用了一點技巧：先將k存入監視哨，若對某個i(≠0)有r.data[i].key=k，則查找成功，返回i;若i從n遞減到1都無記錄的key為k，i再減1為0時，必有r.data[0].key=k，說明查找失敗，返回i=0。
平均查找成功長度ASL= ，而查找失敗時，查找次數等於n+l。
折半查找演算法及分析
當記錄的key按關系≤或≥有序時，不管是遞增的還是遞減的，只要有序且採用順序存儲。
演算法描述
int Binsearch(sqlist r,keytype k) //對有序表r折半查找的演算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空間存在時//
{ mid=(low+high)/2; //求當前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //調整上界，向左部查找//
else
low=mid+1; //調整下界，向右部查找//
}
return(0); //low>high，查找失敗//
}
判定樹：用來描述二分查找過程的二叉樹。n個結點的判定樹的深度和n個結點的完全二叉樹深度相同= 。但判斷樹不一定是完全二叉樹，但他的葉子結點所在層次之差不超過1。所以，折半查找在查找成功時和給定值進行比笑困較的關鍵字個數至多為
ASL=
分塊查找演算法及分析
分塊查找(Blocking Search)，又稱索引順序查找(Indexed Sequential Search)，是順序查找方法的一種改進，目的也是為了提高查找效率。
1.分塊
設記錄表長為n，將表的n個記錄分成b= 個塊，每塊s個記錄(最後一塊記錄數可以少於s個)，即：
且表分塊有序，即第i(1≤i≤b-1)塊所有記錄的key小於第i+1塊中記錄的key，但塊內記錄可以無序。
2.建立索引
每塊對應一索引項：
KeymaxLink
其中Keymax為該塊內記錄的最大key;link為該塊第一記錄的序號(或指針)。
3.演算法思路 分塊索碰模念引查找分兩步進行：
(1)由索引表確定待查找記錄所在的塊;(可以折半查找也可順序因為索引表有序)
(2)在塊內順序查找。(只能用順序查找，塊內是無序的)

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/