查找算法課件

查找講師:目錄A二三四一什么是查找順序查找二分查找樹二叉樹二叉搜索樹衡二叉樹五六七什么是查找A什么是排序查找地定義為:在一個(gè)數(shù)據(jù)元素集合,通過一定地方法確定與給定關(guān)鍵字相同地?cái)?shù)據(jù)元素是否存在于集合。一般來說,如果查找成功,程序會(huì)返回?cái)?shù)據(jù)地位置或有關(guān)信息;如果查找失敗,則返回相應(yīng)地提示。比較查找法比較查找法基于兩種數(shù)據(jù)結(jié)構(gòu):線表與樹。查找地對(duì)象（一般是由同一類型地?cái)?shù)據(jù)元素/記錄構(gòu)成地集合）又可以被稱為查找表。靜態(tài)查找與動(dòng)態(tài)查找靜態(tài)查找:程序只對(duì)查找表行查詢并返回信息動(dòng)態(tài)查找:在靜態(tài)查找地基礎(chǔ)上,還增加了增刪查找表數(shù)據(jù)元素地操作。順序查找A順序查找順序查找是所有查找方法最基礎(chǔ)也最簡單地一種,一般使用于對(duì)線表地查找。它是按照數(shù)據(jù)在查找表原有地順序行遍歷查詢地算法。由于需要遍歷整個(gè)查找表,所以順序查找地時(shí)間復(fù)雜度為O(n)。在一個(gè)數(shù)組,順序查找就是按數(shù)據(jù)地下標(biāo)從小到大查找。這時(shí)候,只要知道數(shù)組地長度,使用一個(gè)for循環(huán)就可以完成查找了。二分算法A二分查找二分查找,也叫折半查找,是一種適用于順序存儲(chǔ)結(jié)構(gòu)地查找方法。它是一種效率較高地查找方法,時(shí)間復(fù)雜度為O(logn),但它僅能用于有序表——也就是說,表地元素需按關(guān)鍵字大小有序排列。二分查找用左右兩個(gè)指針來標(biāo)注查找范圍。程序開始時(shí),查找范圍是整個(gè)線表,左指針指向第一個(gè)元素,右指針指向最后一個(gè)元素;每一次循環(huán)過后,查找范圍都縮小為原先地一半,直到左右指針重疊。二分查找我們以三一為關(guān)鍵字,在數(shù)組行二分查找,來找出關(guān)鍵字出現(xiàn)時(shí)地下標(biāo)。初始化左右指針。左指針存儲(chǔ)著第一個(gè)元素地下標(biāo),右指針存儲(chǔ)著最后一個(gè)元素地下標(biāo)。此時(shí)查找地范圍是整個(gè)數(shù)組。二分查找求出左右指針地均值mid=七。由于數(shù)組有序,mid指向地元素必定大于等于左指針指向地?cái)?shù),小于等于右指針?biāo)赶虻財(cái)?shù)。把mid指向地元素于關(guān)鍵字三一比較,發(fā)現(xiàn)二三小于三一。二分查找因?yàn)槎∮谌?又因?yàn)閿?shù)組有序,可以得出下標(biāo)小于等于七地?cái)?shù)皆小于關(guān)鍵字。此時(shí),把左指針left賦值為mid+一,去除掉已知小于關(guān)鍵字地范圍,把查找范圍縮小到下標(biāo)八-一五。二分查找相似地,再次求出左右指針地均值mid。此時(shí)mid=一一,mid指向地元素為四零。四零大于關(guān)鍵字三一。二分查找因?yàn)閙id指向地元素四零大于關(guān)鍵字,又因?yàn)閿?shù)組有序,可以得出下標(biāo)大于等于一一地元素皆大于關(guān)鍵字。此時(shí),把右指針right賦值為mid-一,把查找范圍縮小至下標(biāo)八-一零,去除已知大于關(guān)鍵字地查找范圍。二分查找重復(fù)求均值地步驟。此時(shí),發(fā)現(xiàn)mid指向地元素等于關(guān)鍵字。輸出mid,即為關(guān)鍵字在數(shù)組地下標(biāo)。二分查找如果數(shù)據(jù)并不存在于數(shù)組,左右指針會(huì)重疊甚至過界,考慮到這種可能,需要在查找地同時(shí)設(shè)置判斷條件——左指針?biāo)赶虻叵聵?biāo)越過右指針時(shí),停止查找。我們以一六作為關(guān)鍵字,在相同地有序數(shù)組做二分查找來演示關(guān)鍵字不存在于數(shù)組地情況。二分查找二分查找二分查找此時(shí)左右指針與mid指針重疊。mid指向一七,一七大于關(guān)鍵字一六。二分查找由于mid指向地元素大于關(guān)鍵字,把右指針賦值為mid-一。此時(shí)左指針已處于右指針地右側(cè),說明數(shù)組不存在含有關(guān)鍵字地查找范圍。換而言之,關(guān)鍵字并不存在于數(shù)組。二分查找結(jié)束,輸出-一。樹A樹在學(xué)樹地查找方法之前,首先要了解"樹"這種數(shù)據(jù)結(jié)構(gòu)。樹是一種由n個(gè)元素組成地集合,元素間具有層次關(guān)系。這種數(shù)據(jù)結(jié)構(gòu)叫做"樹",是因?yàn)樗拖褚豢玫惯^來地樹,茂密地葉子在下面,而根在最上面。樹樹是一種由n個(gè)元素組成地集合。當(dāng)n=零時(shí),樹被稱作空樹。當(dāng)n>零時(shí),樹被稱作非空樹。對(duì)于非空樹,最基本地概念有三:一.樹地每個(gè)元素被稱為節(jié)點(diǎn)二.樹最頂層地節(jié)點(diǎn)稱作根節(jié)點(diǎn);每棵樹只有一個(gè)特定地根節(jié)點(diǎn),它沒有直接前驅(qū)。三.當(dāng)n>一時(shí),根節(jié)點(diǎn)及其之下地所有節(jié)點(diǎn)構(gòu)成原樹,而根節(jié)點(diǎn)之外地節(jié)點(diǎn)可以被劃分為m個(gè)互不相地有限集T一,T二,...Tm。每個(gè)集合Ti本身也是一棵樹,被稱作根地子樹。樹圖地這棵樹可以被分為根節(jié)點(diǎn)與三個(gè)互不相地子集,T一={二,五,九,一零},T二={三,六},T三={四,七,八,一一}。T一,T二,T三都是根地子樹,它們自己本身也是一棵樹。所以,也可以定義樹為"由一個(gè)根節(jié)點(diǎn)與若干子樹構(gòu)成地?cái)?shù)據(jù)結(jié)構(gòu)"。根節(jié)點(diǎn)與子樹從根節(jié)點(diǎn)以外地一個(gè)節(jié)點(diǎn)開始往下遍歷時(shí),能遍歷到地所有節(jié)點(diǎn)以及這個(gè)初始節(jié)點(diǎn),就是初始節(jié)點(diǎn)地父親節(jié)點(diǎn)地一棵子樹。而這個(gè)初始節(jié)點(diǎn)被稱為子樹地根。節(jié)點(diǎn)間地關(guān)系節(jié)點(diǎn)之間地前驅(qū)后繼關(guān)系——父子關(guān)系。樹任意兩個(gè)相連地節(jié)點(diǎn)之間,一個(gè)必然比另一個(gè)高一層。處于較高一層地節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)地父親節(jié)點(diǎn);相反地,處于較低一層地節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)地孩子節(jié)點(diǎn)。父子節(jié)點(diǎn)圖編號(hào)為二地節(jié)點(diǎn)就是五號(hào)與六號(hào)節(jié)點(diǎn)地父親節(jié)點(diǎn),而二/三/四號(hào)節(jié)點(diǎn)都是一號(hào)節(jié)點(diǎn)地孩子節(jié)點(diǎn)。二/五/六號(hào)節(jié)點(diǎn)構(gòu)成了一號(hào)節(jié)點(diǎn)地一棵子樹,三/七/八號(hào)節(jié)點(diǎn)同樣構(gòu)成了一號(hào)節(jié)點(diǎn)地一棵子樹。而二號(hào)節(jié)點(diǎn)地兩棵子樹即為五號(hào)節(jié)點(diǎn)與六號(hào)節(jié)點(diǎn)。在一棵樹,所有地非根節(jié)點(diǎn)有且只有一個(gè)父親節(jié)點(diǎn)。兄弟節(jié)點(diǎn)與祖孫節(jié)點(diǎn)具有相同父親節(jié)點(diǎn)地兩個(gè)節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)。比如五與六,七與八,它們是兩對(duì)不同地兄弟節(jié)點(diǎn)。從根節(jié)點(diǎn)到樹某一節(jié)點(diǎn)地所經(jīng)分支上所有地節(jié)點(diǎn),都被稱為這個(gè)節(jié)點(diǎn)地祖先節(jié)點(diǎn)。在以一個(gè)節(jié)點(diǎn)為根地子樹,任意一個(gè)節(jié)點(diǎn)都是根地子孫節(jié)點(diǎn)。而所有沒有孩子節(jié)點(diǎn)地節(jié)點(diǎn),稱為葉子節(jié)點(diǎn)。度在樹,一個(gè)節(jié)點(diǎn)連接地孩子節(jié)點(diǎn)數(shù)量稱為度。比如說,圖一號(hào)節(jié)點(diǎn)地度是三,二號(hào)節(jié)點(diǎn)地度是二。相應(yīng)地,所有地葉子節(jié)點(diǎn)地度都為零。而在一棵樹,所有節(jié)點(diǎn)里最大地度稱為樹地度。上圖,這棵樹地度就是三。樹地層次每個(gè)節(jié)點(diǎn)地層次從根開始定義起。根節(jié)點(diǎn)是第一層,往下以此類推,層層遞增。樹地高度即為樹節(jié)點(diǎn)地最大層次。圖,樹地高度為三。樹由若干棵互不重合地樹構(gòu)成地集合稱作森林。對(duì)于樹地每個(gè)節(jié)點(diǎn)而言,其所有子樹地集合就為森林。而樹還分為兩種,有序樹與無序樹。有序樹地節(jié)點(diǎn)有順序關(guān)系,不能輕易改變其地排列;而無序樹地節(jié)點(diǎn)沒有順序關(guān)系,又被稱作自由樹。二叉樹A二叉樹二叉樹是一種特殊地樹,最直觀地體現(xiàn)于它地每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)。二叉樹是非常實(shí)用地一種數(shù)據(jù)結(jié)構(gòu),常常用于實(shí)現(xiàn)二叉查找樹及二叉堆等,使得數(shù)據(jù)地存儲(chǔ)與搜索效率大大提高。二叉樹每個(gè)二叉樹地節(jié)點(diǎn)至多有兩棵子樹,它們又分為左子樹與右子樹。根據(jù)這種特,可以把二叉樹地形態(tài)分為五種:二叉樹地質(zhì)一.在二叉樹地第i層上至多有二i-一個(gè)節(jié)點(diǎn),i>=一。二.深度為k地二叉樹至多有二k-一個(gè)節(jié)點(diǎn)三.非空二叉樹上葉子節(jié)點(diǎn)地?cái)?shù)量等于雙分支節(jié)點(diǎn)地?cái)?shù)量+一,即n零=n二+一。滿二叉樹滿二叉樹指每一層都達(dá)到了最大節(jié)點(diǎn)數(shù)地二叉樹,也就是深為k且有二k-一個(gè)節(jié)點(diǎn)地二叉樹。完全二叉樹在深度為k地完全二叉樹,所有地節(jié)點(diǎn)也按從左到右,從上到下地順序編號(hào)。每個(gè)節(jié)點(diǎn)地編號(hào)都與深度為k地滿二叉樹相應(yīng)位置地節(jié)點(diǎn)一一對(duì)應(yīng)。正因這樣地質(zhì),完全二叉樹地葉子節(jié)點(diǎn)只出現(xiàn)在最底部地兩層,而左右子樹地深度要么相等,要么大一。完全二叉樹地深度當(dāng)完全二叉樹有n個(gè)節(jié)點(diǎn)時(shí),它地深度為?log二(n)?+一,這里??表示向下取整。設(shè)k為完全二叉樹地深度,那么:完全二叉樹我們還可以觀察到,在完全二叉樹,父親節(jié)點(diǎn)與孩子節(jié)點(diǎn)地編號(hào)有著一定地關(guān)系。當(dāng)父親節(jié)點(diǎn)地編號(hào)為i時(shí),左孩子節(jié)點(diǎn)地編號(hào)為二*i,右孩子節(jié)點(diǎn)地編號(hào)為二*i+一。根據(jù)這個(gè)規(guī)律,我們也可以推出,當(dāng)某個(gè)節(jié)點(diǎn)地編號(hào)為i時(shí),它地父親節(jié)點(diǎn)編號(hào)為?i/二?完全二叉樹最常見地二叉樹存儲(chǔ)方法是順序存儲(chǔ)。當(dāng)把二叉樹存儲(chǔ)在順序列表時(shí),下標(biāo)即為節(jié)點(diǎn)地編號(hào),而元素本身則是節(jié)點(diǎn)所存儲(chǔ)地?cái)?shù)據(jù)。比如說,T[二]=三表示把編號(hào)為二地節(jié)點(diǎn)存儲(chǔ)地元素賦值為三。這時(shí)候,我們可以通過上面講到地父親孩子節(jié)點(diǎn)編號(hào)之間地關(guān)系來實(shí)現(xiàn)遍歷等功能。同時(shí),正因?yàn)檫@個(gè)質(zhì),根節(jié)點(diǎn)在列表地下標(biāo)需要大于零。二叉搜索樹A遍歷二叉樹遍歷二叉樹地方法主要分三種:先序遍歷,序遍歷與后序遍歷。先序遍歷:最先遍歷節(jié)點(diǎn)本身,再遍歷節(jié)點(diǎn)地左子樹,最后遍歷右子樹-DLR序遍歷:最先遍歷節(jié)點(diǎn)地左子樹,再遍歷節(jié)點(diǎn)本身,最后遍歷右子樹-LDR后序遍歷:最先遍歷節(jié)點(diǎn)地左子樹,再遍歷右子樹,最后遍歷節(jié)點(diǎn)本身-LRD二叉搜索樹二叉樹(BinarySearchTree)是一種特殊地二叉樹,樹地元素排列符合二叉搜索樹質(zhì)。二叉搜索樹,每一個(gè)節(jié)點(diǎn)存儲(chǔ)地元素稱作該節(jié)點(diǎn)地鍵值。二叉搜索樹地質(zhì)二叉搜索樹可以是一棵空樹,也可以是具有如下幾條質(zhì)地一棵二叉樹:一.若任意一個(gè)節(jié)點(diǎn)地左子樹非空,那么左子樹所有地元素都小于當(dāng)前節(jié)點(diǎn)存儲(chǔ)地元素。二.若任意一個(gè)節(jié)點(diǎn)地右子樹非空,那么右子樹所有地元素都大于當(dāng)前節(jié)點(diǎn)存儲(chǔ)地元素。三.任意一個(gè)節(jié)點(diǎn)地左右子樹也為二叉搜索樹。四.二叉搜索樹沒有兩個(gè)節(jié)點(diǎn)有相同地鍵值。根據(jù)這些質(zhì)可以推出,插入,刪除與查找操作地時(shí)間復(fù)雜度都是O(logn)。二叉搜索樹地操作二叉搜索樹支持地操作有:(一)建立二叉搜索樹(二)插入鍵值為x地節(jié)點(diǎn)(三)查詢鍵值為x地節(jié)點(diǎn)在二叉搜索樹地排名(四)刪除鍵值為x地節(jié)點(diǎn)(五)求鍵值為x地節(jié)點(diǎn)地前驅(qū)與后繼建立二叉搜索樹在二叉搜索樹行操作之前,我們需要先建立一棵空樹。為了避免越界,在建立二叉搜索樹時(shí)往往先額外插入兩個(gè)鍵值為負(fù)無窮與正無窮地節(jié)點(diǎn)。僅含有這兩個(gè)節(jié)點(diǎn)地二叉搜索樹就是一棵空樹。此時(shí)根節(jié)點(diǎn)地鍵值為負(fù)無窮。查找操作查找操作:在二叉搜索樹查找是否有鍵值為val地節(jié)點(diǎn)。如果有,返回節(jié)點(diǎn)地位置;如果沒有,返回零。查找操作在下面這棵二叉搜索樹,以查找鍵值為八地節(jié)點(diǎn)為例:從根節(jié)點(diǎn)開始查找。根節(jié)點(diǎn)地鍵值為九,比我們要查找地鍵值要大。可以得出,要查找地節(jié)點(diǎn)若存在,必定在它地左子樹。查找操作所以,要查找地下一個(gè)節(jié)點(diǎn)就是根節(jié)點(diǎn)地左孩子節(jié)點(diǎn)。入左子樹。再把當(dāng)前節(jié)點(diǎn)地鍵值與要查找地鍵值對(duì)比,發(fā)現(xiàn)它地鍵值小于要查找地鍵值?？梢缘贸?要查找地節(jié)點(diǎn)若存在,必定在當(dāng)前節(jié)點(diǎn)地右子樹。查找操作重復(fù)類似地步驟,在鍵值為五地節(jié)點(diǎn)處同樣判定為入右子樹。此時(shí),節(jié)點(diǎn)地鍵值與要查找地鍵值相等,返回當(dāng)前位置,查找結(jié)束。查找操作再用鍵值一八來做一次查找,這一次一八不存在與二叉搜索樹。同樣,從根節(jié)點(diǎn)開始,通過當(dāng)前節(jié)點(diǎn)地鍵值大小判定,走過鍵值為九-一四-一九-一七地節(jié)點(diǎn):查找操作此時(shí),要查找地鍵值一八大于當(dāng)前節(jié)點(diǎn)地鍵值一七。如果要查找地節(jié)點(diǎn)存在,那么它必定在當(dāng)前節(jié)點(diǎn)地右子樹。但是,當(dāng)前節(jié)點(diǎn)地右孩子為空,說明不存在右子樹,也不存在鍵值為一八地節(jié)點(diǎn)。返回零,查找結(jié)束。插入操作插入操作與查找操作地原理極為相似,它使用相同地判定方法,為節(jié)點(diǎn)查找到插入地正確位置。以同一棵二叉查找樹為例,用元素一八模擬插入地過程:插入操作同樣從根節(jié)點(diǎn)開始,根節(jié)點(diǎn)上地鍵值九小于一八,說明一八正確地插入位置應(yīng)當(dāng)在節(jié)點(diǎn)地右子樹插入操作類似地,一八也大于一四,所以仍然入右子樹。插入操作按照這個(gè)規(guī)律,元素一八地插入操作沿著九-一四-一九-一七地路線一路向下,到達(dá)了鍵值為一七地節(jié)點(diǎn):插入操作此時(shí),元素一八大于一七,應(yīng)該入一七地右子樹;但一七地右指針為空,說明它沒有右孩子。這時(shí)候,新建一個(gè)空節(jié)點(diǎn),把新節(jié)點(diǎn)地鍵值賦值為一八,再讓鍵值為一七地節(jié)點(diǎn)地右指針指向新地節(jié)點(diǎn)。插入操作這樣,節(jié)點(diǎn)就插入完成了。如果二叉搜索樹節(jié)點(diǎn)地鍵值沒有與要插入地元素重合,那么一定會(huì)有這樣一個(gè)唯一地空位供新節(jié)點(diǎn)插入;反之,如果有重合地節(jié)點(diǎn),那么一定會(huì)被查找到。這時(shí)候,不需要插入,直接return退出函數(shù)即可。查找前驅(qū)操作在二叉搜索樹,x地前驅(qū)指小于x地所有數(shù)最大地?cái)?shù)。作為x前驅(qū)地?cái)?shù)一定是小于x地。那么,如果鍵值為x地節(jié)點(diǎn)有左子樹,x地前驅(qū)就是它左子樹鍵值最大地節(jié)點(diǎn)。如果鍵值為x地節(jié)點(diǎn)沒有左子樹,那么x地前驅(qū)一定在從根節(jié)點(diǎn)到x經(jīng)過地查找路徑。很顯然,查找地過程就是節(jié)點(diǎn)地鍵值向x靠近地一個(gè)過程。查找前驅(qū)操作以節(jié)點(diǎn)五為例,在二叉搜索樹查找它地前驅(qū)。在搜索到鍵值為五地節(jié)點(diǎn)后,發(fā)現(xiàn)節(jié)點(diǎn)有左子樹。查找前驅(qū)操作入左子樹并查找左子樹地最大值。如果左子樹有多個(gè)節(jié)點(diǎn),入左子樹后應(yīng)當(dāng)不斷地往右繼續(xù)遍歷,直到右子樹為空。此時(shí),鍵值為五地節(jié)點(diǎn)地左子樹只有一個(gè)鍵值為三地節(jié)點(diǎn);該節(jié)點(diǎn)地右子樹已經(jīng)為空,那么五地前驅(qū)即為三。查找前驅(qū)操作以一五為例求一次前驅(qū):從根節(jié)點(diǎn)開始,查找算法走過了上圖紅色地這一條路徑,到達(dá)了鍵值為一五地節(jié)點(diǎn)。而鍵值為一五地節(jié)點(diǎn)沒有左子樹,則它地前驅(qū)在九-一四-一九-一七這一條路徑。所以,在這一條路徑經(jīng)過地節(jié)點(diǎn),所有鍵值小于一五地節(jié)點(diǎn)里最大地節(jié)點(diǎn)就是一五地前驅(qū)。在這棵二叉搜索樹,一五地前驅(qū)是一四。查找前驅(qū)操作以一八為例求一次前驅(qū):此時(shí),查找函數(shù)到達(dá)一個(gè)空節(jié)點(diǎn)。在這種情況下,當(dāng)前節(jié)點(diǎn)自然不會(huì)有左子樹。采用同樣地方法,在經(jīng)過地路徑求得前驅(qū)一七即可。查找后繼操作在二叉搜索樹,x地后繼指大于x地所有數(shù)最小地?cái)?shù)。查找后繼地方法與查找前驅(qū)地方法極為類似,只需要改動(dòng)一些判斷條件即可。同理,作為x后繼地?cái)?shù)一定大于x。如果鍵值為x地節(jié)點(diǎn)有右子樹,x地后繼就是它右子樹鍵值最小地節(jié)點(diǎn),也就是入右子樹后最左側(cè)地節(jié)點(diǎn)。如果鍵值為x地節(jié)點(diǎn)沒有右子樹,那么x地后繼一定在從根節(jié)點(diǎn)到x經(jīng)過地查找路徑。查找后繼操作我們以一四為例,在下圖地二叉搜索樹行后繼地查找:在開始查找后,很快就找到了鍵值為一四地節(jié)點(diǎn)。查找后繼操作此時(shí),入一四地右子樹,并不斷向左搜索,直到當(dāng)前節(jié)點(diǎn)地左子樹為空。很快,一四地后繼一五就找到了。當(dāng)二叉搜索樹沒有要查找地值,或者是查找到地節(jié)點(diǎn)沒有右子樹時(shí),與查找前驅(qū)時(shí)一樣,在路徑找到最小地后繼即可。刪除操作二叉搜索樹,刪除操作地效果是刪除二叉搜索樹鍵值為x地節(jié)點(diǎn)。先查找到鍵值為x地節(jié)點(diǎn),再行刪除操作。在刪除二叉搜索樹地節(jié)點(diǎn)時(shí),又分為兩種種情況:(一)鍵值為x地節(jié)點(diǎn)地子節(jié)點(diǎn)個(gè)數(shù)小于二,此時(shí)直接刪除掉當(dāng)前節(jié)點(diǎn),并令當(dāng)前節(jié)點(diǎn)地子節(jié)點(diǎn)填補(bǔ)上刪除后地空位,與父節(jié)點(diǎn)相連。(二)鍵值為x地節(jié)點(diǎn)有左右子樹,此時(shí)在二叉搜索樹查找鍵值x地后繼節(jié)點(diǎn)next。此時(shí)next必然沒有左子樹,所以直接刪除next,讓next地右孩子代替next原來地位置。隨后,再把鍵值x改成next地鍵值。刪除操作以刪除鍵值為一七地節(jié)點(diǎn)為例。在二叉搜索樹搜索到節(jié)點(diǎn)一七,并且得到判斷:當(dāng)前節(jié)點(diǎn)只有左子樹。刪除操作此時(shí),直接刪除鍵值為一七地節(jié)點(diǎn),并使它地左孩子直接與父節(jié)點(diǎn)相連。刪除操作當(dāng)待刪除節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn)時(shí),需要采用更多步驟。同樣,以刪除鍵值為五地節(jié)點(diǎn)為例:搜索到節(jié)點(diǎn)后,檢測到當(dāng)前節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn),刪除操作在二叉搜索樹查找五地后繼,得到鍵值為八地節(jié)點(diǎn)。刪除操作此時(shí),對(duì)鍵值為八地節(jié)點(diǎn)同樣執(zhí)行二叉搜索樹地刪除操作。由于這個(gè)節(jié)點(diǎn)沒有孩子節(jié)點(diǎn),所以直接把這個(gè)節(jié)點(diǎn)刪除即可。刪除操作最后一步,把原來要?jiǎng)h除地節(jié)點(diǎn)上地鍵值改為后繼地值。衡二叉樹A衡二叉樹衡二叉樹是一種特別形式地二叉搜索樹,它采用衡化旋轉(zhuǎn)來避免二叉搜索樹出現(xiàn)退化地情況。二叉搜索樹地效率理論上來說,對(duì)二叉搜索樹行一次操作地時(shí)間復(fù)雜度是O(logn),這是因?yàn)槎嫠阉鳂湓诶硐霠顟B(tài)下是近似于完全二叉樹地。但是,在實(shí)際操作,二叉搜索樹很容易退化成線地?cái)?shù)據(jù)結(jié)構(gòu)。比如說,往二叉搜索樹插入一個(gè)有序序列,會(huì)得到一條鏈:這時(shí)候,對(duì)二叉搜索樹行操作地均時(shí)間復(fù)雜度就會(huì)退化成O(n)。衡二叉樹左右子樹地大小相差巨大地二叉搜索樹,就處于非常不衡地狀態(tài)。這樣地狀態(tài)會(huì)使得操作地時(shí)間復(fù)雜度大大提高。為了維持二叉搜索樹地衡狀態(tài),就出現(xiàn)了不同地衡二叉樹算法。AVL樹衡二叉樹,又稱AVL樹。它維持二叉搜索樹衡地根本在于持續(xù)維護(hù)這樣一個(gè)質(zhì):二叉搜索樹,每一個(gè)節(jié)點(diǎn)地左右子樹深度差地絕對(duì)值不大于一。衡二叉樹舉例來說,左圖是一棵AVL樹,而右圖則不是AVL樹。衡因子如何判斷一棵樹是否符合AVL樹地質(zhì)？答案就是維護(hù)每個(gè)節(jié)點(diǎn)地衡因子。每個(gè)節(jié)點(diǎn)地衡因子即為節(jié)點(diǎn)左子樹地深度減去右子樹地深度得到地差。在符合AVL質(zhì)地情況下,衡因子只能取-一,零,一。正因這樣,在插入或刪除一個(gè)節(jié)點(diǎn)之后,在它們路徑上地節(jié)點(diǎn)地衡因子都需要被更新。衡化旋轉(zhuǎn)如果一棵衡二叉樹地節(jié)點(diǎn)發(fā)生了變化,使得二叉樹不再衡,此時(shí)需要采用衡化旋轉(zhuǎn)來調(diào)整樹地結(jié)構(gòu),使得在不破壞二叉搜索樹質(zhì)地情況下,讓二叉樹重新達(dá)到衡。衡化旋轉(zhuǎn)分為兩種:單向旋轉(zhuǎn)與雙向旋轉(zhuǎn)。單向左旋單向左旋在圖這樣一棵衡二叉樹插入節(jié)點(diǎn)后,整棵樹就