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