順序查找
略
折半查找
折半查找疙描，也稱二分查找诚隙，在某些情況下，折半查找比順序查找效率更高（要求靜態(tài)查找表中數(shù)據(jù)必須有序）
折半查找效率為：logN
一般用遞歸來(lái)實(shí)現(xiàn)起胰。
總結(jié)：
1.折半查找算法只適用于有序表久又，同時(shí)只能查找順序存儲(chǔ)結(jié)構(gòu)。
2.當(dāng)查找表使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)效五，折半查找無(wú)法有效的進(jìn)行比較操作
分塊查找
分塊查找地消，也叫索引順序查找，算法實(shí)現(xiàn)除了需要查找表本身之外畏妖，還需要根據(jù)查找表建立一個(gè)索引表脉执。
圖中，查找表中共 18 個(gè)查找關(guān)鍵字戒劫，將其平均分為 3 個(gè)子表半夷，對(duì)每個(gè)子表建立一個(gè)索引，索引中包含中兩部分內(nèi)容：該 子表部分中最大的關(guān)鍵字以及第一個(gè)關(guān)鍵字在總表中的位置迅细，即該子表的起始位置玻熙。
建立的索引表要求按照關(guān)鍵字進(jìn)行升序排序，查找表要么整體有序疯攒，要么分塊有序嗦随。
分塊有序指的是第二個(gè)子表中所有關(guān)鍵字都要大于第一個(gè)子表中的最大關(guān)鍵字，第三個(gè)子表的所有關(guān)鍵字都要大于第二個(gè)子表中 的最大關(guān)鍵字敬尺，依次類推
分塊查找的過(guò)程分為兩步進(jìn)行：
- 1.確定要查找的關(guān)鍵字可能存在的具體塊（子表）
- 2.在具體的塊中進(jìn)行順序查找
分塊查找的性能分析
總體來(lái)說(shuō)枚尼，分塊查找算法的效率介于順序查找和折半查找之間。
二叉查找樹(shù)
二叉查找樹(shù)BST(binary search/sort tree) ,又叫二叉查找樹(shù)或者二叉排序樹(shù)砂吞，它首先是一個(gè)二叉樹(shù)署恍，并且滿足一下條件：
- 1.若左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值蜻直。
- 2.若右子樹(shù)不為空盯质，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。
-
3.左右子樹(shù)也分別為二叉排序樹(shù)
二叉查找樹(shù)（二叉排序樹(shù)）
如果二叉樹(shù)查找樹(shù)的所有非葉子節(jié)點(diǎn)的左右子樹(shù)節(jié)點(diǎn)數(shù)據(jù)均保持差不多(平衡)概而，那么二叉查找樹(shù)搜索性能逼近于二分查找呼巷。但它相對(duì)于連續(xù)內(nèi)存空間的二分查找的優(yōu)點(diǎn)是：
插入與刪除結(jié)點(diǎn)，不需要移動(dòng)大段的內(nèi)存赎瑰，甚至通常是常數(shù)開(kāi)銷
但二叉查找樹(shù)在多次刪除插入之后王悍，有可能導(dǎo)致變?yōu)殒湵斫Y(jié)構(gòu)。搜索性能已經(jīng)是線性的了餐曼。
實(shí)際使用的二叉查找樹(shù)都是在原基礎(chǔ)上加入了平衡算法压储。即平衡二叉樹(shù)鲜漩。
平衡二叉樹(shù)（AVL樹(shù)）
AVL自平衡二叉查找樹(shù)
平衡二叉樹(shù)用平衡因子差值來(lái)判斷是否平衡，并旋轉(zhuǎn)二叉樹(shù)集惋。平衡因子：左右子樹(shù)高度差孕似。平衡二叉樹(shù)里平衡因子不能超過(guò)1，否則旋轉(zhuǎn)刮刑。（常用平衡二叉樹(shù)算法有紅黑樹(shù)喉祭，AVL，Treap为朋，伸展樹(shù)等）臂拓。
這個(gè)方案很好的解決了二叉查找樹(shù)退化成鏈表的問(wèn)題厚脉，把插入习寸，查找，刪除的時(shí)間復(fù)雜度最好情況和最壞情況都維持在O(logN)傻工。但是頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉O(logN)左右的時(shí)間霞溪，不過(guò)相對(duì)二叉查找樹(shù)來(lái)說(shuō)，時(shí)間上穩(wěn)定了很多中捆。
windows對(duì)進(jìn)程地址空間的管理用到了AVL樹(shù)鸯匹。
旋轉(zhuǎn)
LL，RR 一次旋轉(zhuǎn)
LR泄伪，RL 雙旋轉(zhuǎn)(先左后右殴蓬，先右后左)
紅黑樹(shù)
紅黑樹(shù)（RB-Tree）是一種自平衡的二叉查找樹(shù)，他的節(jié)點(diǎn)為紅色和黑色蟋滴，不像AVL樹(shù)嚴(yán)格控制左右子樹(shù)的高度差染厅。紅黑樹(shù)的特性
- 1.節(jié)點(diǎn)是紅色或黑色。
- 2.根節(jié)點(diǎn)是黑色津函。
- 3.葉子節(jié)點(diǎn)是黑色肖粮。
- 4.一個(gè)紅色節(jié)點(diǎn)只能有0個(gè)到2個(gè)黑色節(jié)點(diǎn)。
- 5.葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)的數(shù)量是相同的尔苦。
紅黑樹(shù)
紅黑樹(shù)能以O(shè)(logN)的時(shí)間復(fù)雜度進(jìn)行搜索涩馆，插入和刪除操作。紅黑樹(shù)在查找方面與AVL樹(shù)操作幾乎相同允坚。但是在插入和刪除操作上魂那，AVL樹(shù)每次插入刪除會(huì)進(jìn)行大量的平衡度計(jì)算，紅黑樹(shù)犧牲了嚴(yán)格的平衡為代價(jià)稠项，他只要求部分達(dá)到平衡要求冰寻，降低了對(duì)旋轉(zhuǎn)的要求，從而提高了性能皿渗。任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決斩芭。
紅黑樹(shù)能確保任何一個(gè)節(jié)點(diǎn)的左右子樹(shù)高度差不會(huì)超過(guò)二者中較低那一個(gè)的一倍轻腺。
紅黑樹(shù)廣泛用于TreeMap、TreeSet划乖、以及JDK1.8的hashMap贬养。
B樹(shù)
B樹(shù)（Blance-Tree）平衡樹(shù)，也叫作B-樹(shù)琴庵，是多路查找平衡樹(shù)（可能是二叉也可能是多叉）误算。
B樹(shù)是一個(gè)高度平衡樹(shù)。
一個(gè)M階的B樹(shù)規(guī)定了：
- 1.樹(shù)中每個(gè)節(jié)點(diǎn)至多有m棵子樹(shù)（兩棵子樹(shù)指針夾著一個(gè)關(guān)鍵字）
- 2.若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)迷殿，至少有兩棵子樹(shù)（至少一個(gè)關(guān)鍵字）
- 3.除根節(jié)點(diǎn)之外的所有非終端節(jié)點(diǎn)至少有[m/2]棵子樹(shù)儿礼。（即至少包含有[m/2]-1個(gè)關(guān)鍵字）
- 4.所有的葉子節(jié)點(diǎn)出現(xiàn)在同一層次上。實(shí)際上這些節(jié)點(diǎn)都不存在庆寺，只想這些節(jié)點(diǎn)的指針都為null蚊夫。
- 5.每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，A0懦尝，K1知纷，A1，K2陵霉，A2琅轧，……，Kn踊挠，An)乍桂。其中
- a)Ki (i=1…n)為關(guān)鍵字，且關(guān)鍵字按順序排序Ki < K(i-1)
- b)Ai為指向子樹(shù)根的接點(diǎn)效床，且指針A(i-1)指向子樹(shù)種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki睹酌，但都大于K(i-1)。
- c) 關(guān)鍵字的個(gè)數(shù)n必須滿足： [m/2]-1 <= n <= m-1
B樹(shù)拆入刪除 節(jié)點(diǎn)分裂合并視頻
https://www.bilibili.com/video/av36069871?from=search&seid=10258516047823270671
B樹(shù)有以下特性：
- 1.關(guān)鍵字集合分布在整棵樹(shù)中忍疾。
- 2.任何一個(gè)關(guān)鍵字出現(xiàn)只能出現(xiàn)在一個(gè)節(jié)點(diǎn)中。
- 3.搜索有可能在非葉子節(jié)點(diǎn)結(jié)束谨朝。
- 4.其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找卤妒。
- 5.自動(dòng)層次控制。
- 6.每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)字币，也就是對(duì)應(yīng)的key和value则披。
B樹(shù)對(duì)于紅黑樹(shù)的優(yōu)勢(shì)很明顯了，最明顯的就是B樹(shù)一個(gè)結(jié)點(diǎn)存放了多個(gè)關(guān)鍵字洗出。節(jié)點(diǎn)越多士复，B~樹(shù)比平衡二叉樹(shù)所用的操作次數(shù)將越少，效率也越高。
B樹(shù)一般應(yīng)用于文件管理阱洪，或外部存儲(chǔ)的地址管理便贵。mongoDB也是用B樹(shù)索引。
一棵含n個(gè)結(jié)點(diǎn)的B樹(shù)的高度為O（lgn）冗荸，所以承璃，B樹(shù)可以在O（logn）時(shí)間內(nèi)（沒(méi)有計(jì)算分裂合并的時(shí)間），實(shí)現(xiàn)各種如插入（insert）蚌本，刪除（delete）等動(dòng)態(tài)集合操作盔粹。
，一般用于數(shù)據(jù)庫(kù)中做索引程癌，因?yàn)樗鼈兎种Ф鄬訑?shù)少舷嗡，因?yàn)榇疟PIO是非常耗時(shí)的，而像大量數(shù)據(jù)存儲(chǔ)在磁盤中所以我們要有效的減少磁盤IO次數(shù)避免磁盤頻繁的查找嵌莉。
B樹(shù)有一些場(chǎng)景不友好进萄，比如范圍查找。
B樹(shù)在提高自盤IO性能的同時(shí)烦秩，并沒(méi)有解決元素遍歷的效率問(wèn)題垮斯，而B(niǎo)+樹(shù)可以解決郎仆。B+樹(shù)只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整個(gè)樹(shù)的遍歷只祠。
B+樹(shù)
? B樹(shù)，B+樹(shù)：它們特點(diǎn)是一樣的扰肌，是多路查找樹(shù)
B+樹(shù)是B樹(shù)的變種樹(shù)抛寝，有n棵子樹(shù)的節(jié)點(diǎn)中含有n個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字不保存數(shù)據(jù)曙旭，只用來(lái)索引盗舰，數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。是為文件系統(tǒng)而生的桂躏。
B+樹(shù)具有以下特性：
- 1.有n棵子樹(shù)的節(jié)點(diǎn)中含有n個(gè)關(guān)鍵字
- 2.所有的非葉子節(jié)點(diǎn)中包含了全部關(guān)鍵字的信息钻趋，及指向含有這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序進(jìn)行連接（B樹(shù)的非葉子節(jié)點(diǎn)也包含了數(shù)據(jù)信息）
- 3.根節(jié)點(diǎn)和中間結(jié)點(diǎn) 只做索引剂习，不包含數(shù)據(jù)指針以及數(shù)據(jù)
- 4.葉子結(jié)點(diǎn)包含所有數(shù)據(jù)蛮位，并按照從小到大順序排列
- 5.葉子結(jié)點(diǎn)用指針連在一起
B+樹(shù)的頭指針有兩個(gè)，一個(gè)指向根節(jié)點(diǎn)鳞绕，另一個(gè)指向關(guān)鍵字最小的元素失仁，因此B+樹(shù)有兩種遍歷的方式：
1.從根節(jié)點(diǎn)開(kāi)始隨機(jī)查詢
2.從最小關(guān)鍵詞順序查詢
? B+樹(shù)相對(duì)B樹(shù)磁盤讀寫代價(jià)更低：因?yàn)锽+樹(shù)非葉子結(jié)點(diǎn)只存儲(chǔ)鍵值，單個(gè)節(jié)點(diǎn)占空間小们何，索引塊能夠存儲(chǔ)更多的節(jié)點(diǎn)萄焦，從磁盤讀索引時(shí)所需的索引塊更少，所以索引查找時(shí)I/O次數(shù)較B-Tree索引少冤竹，效率更高拂封。而且B+Tree在葉子節(jié)點(diǎn)存放的記錄以鏈表的形式鏈接茬射，范圍查找或遍歷效率更高。Mysql InnoDB用的就是B+Tree索引冒签。
B+樹(shù)也需要分裂和合并
Trie樹(shù)
單詞查找樹(shù) DFA
Trie樹(shù)：
? 又名單詞查找樹(shù)躲株，一種樹(shù)形結(jié)構(gòu)，常用來(lái)操作字符串镣衡。它是不同字符串的相同前綴只保存一份霜定。
相對(duì)直接保存字符串肯定是節(jié)省空間的，但是它保存大量字符串時(shí)會(huì)很耗費(fèi)內(nèi)存（是內(nèi)存）廊鸥。
類似的有：前綴樹(shù)(prefix tree)望浩，后綴樹(shù)(suffix tree)，radix tree(patricia tree, compactprefix tree)惰说，crit-bit tree（解決耗費(fèi)內(nèi)存問(wèn)題）磨德，以及前面說(shuō)的double array trie。
前綴樹(shù)：字符串快速檢索吆视，字符串排序典挑，最長(zhǎng)公共前綴，自動(dòng)匹配前綴顯示后綴啦吧。
后綴樹(shù)：查找字符串s1在s2中您觉，字符串s1在s2中出現(xiàn)的次數(shù)，字符串s1,s2最長(zhǎng)公共部分授滓，最長(zhǎng)回文串琳水。
trie 樹(shù)的一個(gè)典型應(yīng)用是前綴匹配，比如下面這個(gè)很常見(jiàn)的場(chǎng)景般堆，在我們輸入時(shí)在孝，搜索引擎會(huì)給予提示。
hash查找法
散列表（Hash table淮摔，也叫哈希表）私沮，是根據(jù)鍵（Key）而直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)和橙，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)仔燕，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，這加快了查找速度胃碾。這個(gè)映射函數(shù)稱做散列函數(shù)涨享，存放記錄的數(shù)組稱做散列表。
是一種以空間換時(shí)間的算法仆百。
布隆過(guò)濾器就是一種hash查找法厕隧，以空間換時(shí)間。存在hash沖突。
散列規(guī)則：直接定址法吁讨，數(shù)字分析法髓迎，平方取中法，折疊法建丧，隨機(jī)數(shù)法排龄，儲(chǔ)留余數(shù)法。
