2023計(jì)算機(jī)考研初試在即，在最后階段建議各位同學(xué)將知識(shí)點(diǎn)再系統(tǒng)復(fù)習(xí)一遍，以免有所遺漏！2022計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)第六單元知識(shí)點(diǎn)包含二分搜索、二叉搜索樹、平衡二叉樹等內(nèi)容。高頓考研為大家整理了2022計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)第六單元知識(shí)點(diǎn)的詳細(xì)內(nèi)容，供大家參考復(fù)習(xí)！
二分搜索
關(guān)鍵字：用來標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)。
主關(guān)鍵字：可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字。
次關(guān)鍵字：不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字。
搜索：在數(shù)據(jù)結(jié)構(gòu)中尋找關(guān)鍵字等于給定值的元素。
平均搜索長(zhǎng)度：搜索過程中關(guān)鍵字值之間的平均比較次數(shù)。
二分搜索
將中間位置上的元素的關(guān)鍵字與待搜索元素的關(guān)鍵字相比較
若相等：搜索成功。
若較?。涸谥虚g元素的左邊的表中進(jìn)行二分搜索，若較大則在右邊進(jìn)行。
實(shí)現(xiàn)：用low和high分別指示表的兩端，m為中間元素的位置
初始時(shí)有m=(low+high)/2
若表長(zhǎng)為偶數(shù)，根據(jù)小數(shù)與int型數(shù)的轉(zhuǎn)換可知，m應(yīng)該向下取整。
每次比較之后，根據(jù)比較的結(jié)果調(diào)整low或high的值來調(diào)整需要繼續(xù)進(jìn)行二分搜索操作的表的范圍。
二叉搜索樹
每個(gè)結(jié)點(diǎn)的關(guān)鍵字都大于其左子樹上所有結(jié)點(diǎn)的關(guān)鍵字，小于右子樹上所有結(jié)點(diǎn)的關(guān)鍵字(中序遍歷該樹，所得序列的關(guān)鍵字的值遞增)。
搜索過程中，若元素值小于根結(jié)點(diǎn)的關(guān)鍵字值，則進(jìn)入左子樹，反之進(jìn)入右子樹。
1)二叉搜索樹的刪除：
a.若被刪結(jié)點(diǎn)沒有孩子：用空子樹NULL代替即可。
b.若被刪結(jié)點(diǎn)有一個(gè)孩子：用孩子代替即可。
c.若被刪結(jié)點(diǎn)有兩個(gè)孩子：找到其中序遍歷下的直接后繼，將其值復(fù)制，并刪除該后繼。
2)二叉搜索樹的高度：
對(duì)于n個(gè)結(jié)點(diǎn)的二叉搜索樹：
最大高度為n，此時(shí)，按此順序插入的元素的關(guān)鍵字值遞增或者遞減。
最小高度為log2n，將結(jié)點(diǎn)按關(guān)鍵字從小到大排列，二分搜索的過程中，按比較次數(shù)由小到大的順序，插入結(jié)點(diǎn)可得最小高度。
平衡二叉樹
任何一個(gè)結(jié)點(diǎn)的左右子樹的高度相差不過1。
1)平衡因子：結(jié)點(diǎn)的左子樹的高度減去右子樹的高度。
平衡過程：插入、平衡、重組
a.插入：將新結(jié)點(diǎn)q按照平衡二叉搜索樹的排序性質(zhì)作為樹葉插入，令其平衡因子為0，記下離q最近且平衡因子不為0的祖先結(jié)點(diǎn)s，若所有祖先結(jié)點(diǎn)的平衡因子均為0，令s指向根結(jié)點(diǎn)。
b.平衡：修改從s到q的路徑上的結(jié)點(diǎn)的平衡因子，不修改s和q，對(duì)于其中的結(jié)點(diǎn)p，若q插在p的左子樹，則平衡因子+1，否則-1。
c.重組：當(dāng)s的平衡因子為0時(shí)，s為根結(jié)點(diǎn)，此時(shí)將s的平衡因子+1或者-1即可。
若s的平衡因子為-1，q插在s的左子樹，或+1，插在右子樹，只需改平衡因子為0。
若s的平衡因子為+1，q插在左子樹，此時(shí)左重組，反之右重組。
2)重組方式：
a.若插入前，從根結(jié)點(diǎn)到新結(jié)點(diǎn)的插入位置的路徑上，所有結(jié)點(diǎn)的平衡因子值均為0，則插入即可。
b.若插在結(jié)點(diǎn)較矮的子樹上，則插入即可。
c.if(r->bf==1)
{s->lchild=r->rchild;r->rchild=s;}//LL
d.u=r->rchild;
r->rchild=u->lchild;
u->lchild=r;
s->lchild=u->rchild;
u->rchild=s;
散列表：
散列搜索的搜索過程是按照關(guān)鍵字來計(jì)算元素可能的存儲(chǔ)地址
確定一個(gè)函數(shù)，每個(gè)元素的關(guān)鍵字經(jīng)由這一函數(shù)映射出一個(gè)函數(shù)值
這樣的函數(shù)稱作散列函數(shù)，得到的值為散列地址，函數(shù)的值域?yàn)樯⒘械刂房臻g
好的散列函數(shù)應(yīng)該使得函數(shù)值盡可能均勻分布在散列地址空間
1)處理沖突：
a.開地址法(線性探測(cè))
地址為i的單元發(fā)生沖突時(shí)，依次探測(cè)(i+1)%m，(i+2)%m…將元素插入第一個(gè)空單元。
即每次往后移動(dòng)一個(gè)存儲(chǔ)單元查找是否有空閑地址，允許循環(huán)，直到再次到達(dá)地址i或在此之前找到空閑地址。
缺點(diǎn)：n個(gè)被占用的單元連成一片時(shí)，后面的空單元被占用的可能性增加。
b.開地址法(雙散列函數(shù)探測(cè))
當(dāng)i=h1(k)被占用時(shí)，
C=h2(k)然后依次探測(cè)(i+c)%m(i+2c)%m…
線性探測(cè)每次只移動(dòng)一個(gè)存儲(chǔ)單元，雙散列函數(shù)探測(cè)法中，每次移動(dòng)的大小由第二個(gè)散列函數(shù)決定。
缺點(diǎn)：由于尋找是跳躍性的，部分空單元可能總被跳過去，無法利用。
c.拉鏈法：將散列地址相同的元素鏈接起來，構(gòu)成一個(gè)線性鏈表，將各鏈表的表頭指針存入散列表。
2)裝載密度=存入散列表的節(jié)點(diǎn)個(gè)數(shù)散列地址空間大小。
3)開地址法中，刪除一個(gè)結(jié)點(diǎn)時(shí)，只能在刪除的結(jié)點(diǎn)上做標(biāo)記，不能真正刪除，不然會(huì)影響其他的結(jié)點(diǎn)查找。
不同搜索方式的時(shí)間復(fù)雜度：
順序搜索：查找和插入的時(shí)間復(fù)雜度：O(n)
二分查找：查找時(shí)間復(fù)雜度O(logn)插入時(shí)間復(fù)雜度O(n)
二叉搜索樹：查找時(shí)間復(fù)雜度O(logn)插入時(shí)間復(fù)雜度O(logn)
散列表法：O(1)