表、棧和隊(duì)列

表

我們處理形如A₀,A₁,.....,A_N的一般的表麦牺。我們說這個(gè)表的大小是N钮蛛。我們將大小為0 的特殊的表稱為空表(empty list)。除空表之外的任何表剖膳，我們稱A_i后繼A_i-1(或A之后魏颓，i<N)并稱A_i-1前驅(qū)A_i（i>0）。

數(shù)組

數(shù)組是可以再內(nèi)存中連續(xù)存儲多個(gè)元素的結(jié)構(gòu)吱晒，在內(nèi)存中的分配也是連續(xù)的甸饱，數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問，數(shù)組下標(biāo)從0開始仑濒。例如下面這段代碼就是將數(shù)組的第一個(gè)元素賦值為 1叹话。

優(yōu)點(diǎn)
1、按照索引查詢元素速度快
2躏精、按照索引遍歷數(shù)組方便
缺點(diǎn)
1渣刷、數(shù)組的大小固定后就無法擴(kuò)容了
2鹦肿、數(shù)組只能存儲一種類型的數(shù)據(jù)
3矗烛、添加，刪除的操作慢，因?yàn)橐苿?dòng)其他的元素瞭吃。
適用場景
頻繁查詢碌嘀，對存儲空間要求不大，很少增加和刪除的情況歪架。

鏈表

鏈表是物理存儲單元上非連續(xù)的股冗、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實(shí)現(xiàn)和蚪，每個(gè)元素包含兩個(gè)結(jié)點(diǎn)止状，一個(gè)是存儲元素的數(shù)據(jù)域 (內(nèi)存空間)，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)地址的指針域攒霹。根據(jù)指針的指向怯疤，鏈表能形成不同的結(jié)構(gòu)，例如單鏈表催束，雙向鏈表冈敛，循環(huán)鏈表等衰伯。

image.png

優(yōu)點(diǎn)：
鏈表是很常用的一種數(shù)據(jù)結(jié)構(gòu)，不需要初始化容量，可以任意加減元素集侯；
添加或者刪除元素時(shí)只需要改變前后兩個(gè)元素結(jié)點(diǎn)的指針域指向地址即可，所以添加妹蔽，刪除很快沥匈；
缺點(diǎn)
因?yàn)楹写罅康闹羔樣颍加每臻g較大罕容；
查找元素需要遍歷鏈表來查找妨马，非常耗時(shí)。
適用場景
數(shù)據(jù)量較小杀赢，需要頻繁增加烘跺，刪除操作的場景

棧

棧是一種特殊的線性表，僅能在線性表的一端操作脂崔，棧頂允許操作滤淳，棧底不允許操作。 棧的特點(diǎn)是：先進(jìn)后出(LIFO)砌左，或者說是后進(jìn)先出脖咐，從棧頂放入元素的操作叫入棧，取出元素叫出棧汇歹。

棧操作

棧的結(jié)構(gòu)就像一個(gè)集裝箱屁擅，越先放進(jìn)去的東西越晚才能拿出來，所以产弹，棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場景派歌，例如斐波那契數(shù)列。

隊(duì)列

像棧一樣，隊(duì)列(queue)也是表胶果。然而使用隊(duì)列時(shí)插入在一端進(jìn)行而刪除在另一端進(jìn)行匾嘱。也就是：先進(jìn)先出（FIFO）。從一端放入元素的操作稱為入隊(duì)早抠，取出元素為出隊(duì)霎烙，示例圖如下：

image.png

使用場景
因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)，在多線程阻塞隊(duì)列管理中非常適用

樹

樹是一種數(shù)據(jù)結(jié)構(gòu)蕊连，它是由n（）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合悬垃。把它叫做 “樹” 是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上甘苍，而葉朝下的盗忱。它具有以下的特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)羊赵；
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)趟佃；
除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹昧捷；

術(shù)語

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度闲昭；
樹的度：一棵樹中，最大的節(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)，則這個(gè)節(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)的子節(jié)點(diǎn)簸淀；
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
節(jié)點(diǎn)的層次：從根開始定義起毒返，根為第1層租幕，根的子節(jié)點(diǎn)為第2層，以此類推拧簸；
樹的高度或深度：樹中節(jié)點(diǎn)的最大層次劲绪；
堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；
節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)盆赤；
子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫贾富；
森林：由m（）棵互不相交的樹的集合稱為森林。

二叉樹

二叉樹的定義： 二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))牺六，二叉樹的子樹有左右之分颤枪，次序不能顛倒。二叉樹的第i層至多有2i-1個(gè)結(jié)點(diǎn)淑际；深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)畏纲；對任何一棵二叉樹T扇住，如果其終端結(jié)點(diǎn)數(shù)為n₀，度為2的結(jié)點(diǎn)數(shù)為n₂霍骄，則n₀ = n₂+1。

二叉樹

1. 在非空二叉樹中淡溯，第i層的結(jié)點(diǎn)總數(shù)不超過2^i-1, ;
2. 深度為h的二叉樹最多有2^h-1個(gè)結(jié)點(diǎn)()读整，最少有h個(gè)結(jié)點(diǎn);
3. 對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N₀咱娶，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N₂米间，則N₀=N₂+1;
4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log₂(n+1);
5. 有N個(gè)結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲，則結(jié)點(diǎn)之間有如下關(guān)系：

若I為結(jié)點(diǎn)編號則 如果I>1膘侮，則其父結(jié)點(diǎn)的編號為屈糊；
　　如果2I<=N，則其左兒子（即左子樹的根結(jié)點(diǎn)）的編號為2I琼了；若2I>N逻锐，則無左兒子；
　　如果2I+1<=N雕薪，則其右兒子的結(jié)點(diǎn)編號為2I+1昧诱；若2I+1>N，則無右兒子所袁。

6. 給定N個(gè)節(jié)點(diǎn)盏档，能構(gòu)成h(N)種不同的二叉樹，其中h(N)為卡特蘭數(shù)的第N項(xiàng)燥爷，h(N) = 蜈亩。
7. 設(shè)有i個(gè)枝點(diǎn)，I為所有枝點(diǎn)的道路長度總和前翎，J為葉的道路長度總和J=I+2ⁱ稚配。

滿二叉樹

定義： 除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)港华。也可以這樣理解药有，除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)均有兩個(gè)子結(jié)點(diǎn)。節(jié)點(diǎn)數(shù)達(dá)到最大值苹丸，所有葉子結(jié)點(diǎn)必須在同一層上愤惰。
滿二叉樹的性質(zhì)：

1. 一顆樹深度為h，最大層數(shù)為k赘理，深度與最大層數(shù)相同宦言，k=h;
2. 葉子數(shù)為2^h;
3. 第k層的結(jié)點(diǎn)數(shù)是：2^k-1;
4. 總結(jié)點(diǎn)數(shù)是：2^k-1，且總節(jié)點(diǎn)數(shù)一定是奇數(shù)商模。

滿二叉樹

完全二叉樹

定義： 若設(shè)二叉樹的深度為h奠旺，除第 h 層外蜘澜，其它各層 (1～(h-1)層) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊响疚，這就是完全二叉樹鄙信。

完全二叉樹

注：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，堆是一種完全二叉樹或者近似完全二叉樹忿晕，所以效率極高装诡，像十分常用的排序算法、Dijkstra算法践盼、Prim算法等都要用堆才能優(yōu)化鸦采，二叉排序樹的效率也要借助平衡性來提高，而平衡性基于完全二叉樹咕幻。

二叉查找樹

定義：又稱為是二叉排序樹（Binary Sort Tree）或二叉搜索樹渔伯。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

1. 若左子樹不空肄程，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值锣吼；
2. 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值蓝厌；
3. 左吐限、右子樹也分別為二叉排序樹；
4. 沒有鍵值相等的節(jié)點(diǎn)褂始。

二叉查找樹的性質(zhì)： 對二叉查找樹進(jìn)行中序遍歷诸典，即可得到有序的數(shù)列。

二叉查找樹的時(shí)間復(fù)雜度：它和二分查找一樣崎苗，插入和查找的時(shí)間復(fù)雜度均為O(logN )狐粱，但是在最壞的情況下仍然會(huì)有O(n)的時(shí)間復(fù)雜度。原因在于插入和刪除元素的時(shí)候胆数，樹沒有保持平衡肌蜻。我們追求的是在最壞的情況下仍然有較好的時(shí)間復(fù)雜度，這就是平衡查找樹設(shè)計(jì)的初衷必尼。二叉查找樹的高度決定了二叉查找樹的查找效率蒋搜。
　二叉查找樹的插入過程如下：

1. 若當(dāng)前的二叉查找樹為空，則插入的元素為根節(jié)點(diǎn);
2. 若插入的元素值小于根節(jié)點(diǎn)值判莉，則將元素插入到左子樹中;
3. 若插入的元素值不小于根節(jié)點(diǎn)值豆挽，則將元素插入到右子樹中。

二叉查找樹的刪除券盅，分三種情況進(jìn)行處理：

1. p為葉子節(jié)點(diǎn)帮哈，直接刪除該節(jié)點(diǎn)，再修改其父節(jié)點(diǎn)的指針（注意分是根節(jié)點(diǎn)和不是根節(jié)點(diǎn)）锰镀，如圖a;
2. p為單支節(jié)點(diǎn)（即只有左子樹或右子樹）娘侍。讓p的子樹與p的父親節(jié)點(diǎn)相連咖刃，刪除p即可（注意分是根節(jié)點(diǎn)和不是根節(jié)點(diǎn)），如圖b;

3. p的左子樹和右子樹均不空憾筏。找到p的后繼y嚎杨，因?yàn)閥一定沒有左子樹，所以可以刪除y氧腰，并讓y的父親節(jié)點(diǎn)成為y的右子樹的父親節(jié)點(diǎn)枫浙，并用y的值代替p的值；或者方法二是找到p的前驅(qū)x容贝，x一定沒有右子樹自脯，所以可以刪除x之景，并讓x的父親節(jié)點(diǎn)成為y的左子樹的父親節(jié)點(diǎn)斤富。如圖c。

   
   
   a
   
   
   b
   
   
   c

平衡二叉樹

我們知道锻狗，對于一般的二叉搜索樹（Binary Search Tree）满力，其期望高度（即為一棵平衡樹時(shí)）為log₂n，其各操作的時(shí)間復(fù)雜度O(log₂n)同時(shí)也由此而決定轻纪。但是油额，在某些極端的情況下（如在插入的序列是有序的時(shí)），二叉搜索樹將退化成近似鏈或鏈刻帚，此時(shí)潦嘶，其操作的時(shí)間復(fù)雜度將退化成線性的，即O(n)崇众。我們可以通過隨機(jī)化建立二叉搜索樹來盡量的避免這種情況掂僵，但是在進(jìn)行了多次的操作之后，由于在刪除時(shí)顷歌，我們總是選擇將待刪除節(jié)點(diǎn)的后繼代替它本身锰蓬，這樣就會(huì)造成總是右邊的節(jié)點(diǎn)數(shù)目減少，以至于樹向左偏沉眯漩。這同時(shí)也會(huì)造成樹的平衡性受到破壞芹扭，提高它的操作的時(shí)間復(fù)雜度。于是就有了我們下邊介紹的平衡二叉樹赦抖。
定義：平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法）舱卡，且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹队萤。平衡二叉樹的常用算法有紅黑樹灼狰、AVL樹等。在平衡二叉搜索樹中浮禾，我們可以看到交胚，其高度一般都良好地維持在份汗，大大降低了操作的時(shí)間復(fù)雜度。

最小二叉平衡樹的節(jié)點(diǎn)的公式如下：
　　F(n)=F(n-1)+F(n-2)+1
這個(gè)類似于一個(gè)遞歸的數(shù)列蝴簇，可以參考Fibonacci數(shù)列杯活，1是根節(jié)點(diǎn)，F(xiàn)(n-1)是左子樹的節(jié)點(diǎn)數(shù)量熬词，F(xiàn)(n-2)是右子樹的節(jié)點(diǎn)數(shù)量旁钧。

AVL樹

定義：AVL樹是最先發(fā)明的自平衡二叉查找樹。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis互拾，他們在 1962 年的論文 "An algorithm for the organization of information"中發(fā)表了它歪今。在AVL中任何節(jié)點(diǎn)的兩個(gè)兒子子樹的高度最大差別為1，所以它也被稱為高度平衡樹颜矿，N個(gè)結(jié)點(diǎn)的AVL樹最大深度約寄猩。查找、插入和刪除在平均和最壞情況下都是骑疆。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹田篇。這個(gè)方案很好的解決了二叉查找樹退化成鏈表的問題，把插入箍铭，查找泊柬，刪除的時(shí)間復(fù)雜度最好情況和最壞情況都維持在。但是頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉左右的時(shí)間诈火，不過相對二叉查找樹來說兽赁，時(shí)間上穩(wěn)定了很多。（x：算法中l(wèi)og級別的時(shí)間復(fù)雜度都是由于使用了分治思想,這個(gè)底數(shù)直接由分治的復(fù)雜度決定冷守。如果采用二分法,那么就會(huì)以2為底數(shù)及x=2,三分法就會(huì)以3為底數(shù)及x=2）

AVL樹的自平衡操作
旋轉(zhuǎn)：
AVL樹最關(guān)鍵的也是最難的一步操作就是旋轉(zhuǎn)刀崖。旋轉(zhuǎn)主要是為了實(shí)現(xiàn)AVL樹在實(shí)施了插入和刪除操作以后，樹重新回到平衡的方法教沾。下面我們重點(diǎn)研究一下AVL樹的旋轉(zhuǎn)蒲跨。
　　對于一個(gè)平衡的節(jié)點(diǎn)，由于任意節(jié)點(diǎn)最多有兩個(gè)兒子授翻，因此高度不平衡時(shí)或悲，此節(jié)點(diǎn)的兩顆子樹的高度差2.容易看出，這種不平衡出現(xiàn)在下面四種情況：

四種不平衡的情況

1. 6節(jié)點(diǎn)的左子樹3節(jié)點(diǎn)高度比右子樹7節(jié)點(diǎn)大2堪唐，左子樹3節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度大于右子樹4節(jié)點(diǎn)巡语，這種情況成為左左。
2. 6節(jié)點(diǎn)的左子樹2節(jié)點(diǎn)高度比右子樹7節(jié)點(diǎn)大2淮菠，左子樹2節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度小于右子樹4節(jié)點(diǎn)男公，這種情況成為左右。
3. 2節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度比右子樹5節(jié)點(diǎn)小2合陵，右子樹5節(jié)點(diǎn)的左子樹3節(jié)點(diǎn)高度大于右子樹6節(jié)點(diǎn)枢赔，這種情況成為右左澄阳。
4. 2節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度比右子樹4節(jié)點(diǎn)小2，右子樹4節(jié)點(diǎn)的左子樹3節(jié)點(diǎn)高度小于右子樹6節(jié)點(diǎn)踏拜，這種情況成為右右碎赢。

從上圖中可以可以看出，1和4兩種情況是對稱的速梗，這兩種情況的旋轉(zhuǎn)算法是一致的肮塞，只需要經(jīng)過一次旋轉(zhuǎn)就可以達(dá)到目標(biāo)，我們稱之為單旋轉(zhuǎn)姻锁。2和3兩種情況也是對稱的枕赵，這兩種情況的旋轉(zhuǎn)算法也是一致的，需要進(jìn)行兩次旋轉(zhuǎn)位隶，我們稱之為雙旋轉(zhuǎn)拷窜。
單旋轉(zhuǎn)
單旋轉(zhuǎn)是針對于左左和右右這兩種情況的解決方案，這兩種情況是對稱的钓试，只要解決了左左這種情況装黑，右右就很好辦了副瀑。圖3是左左情況的解決方案弓熏，節(jié)點(diǎn)k2不滿足平衡特性，因?yàn)樗淖笞訕鋕1比右子樹Z深2層糠睡，而且k1子樹中挽鞠，更深的一層的是k1的左子樹X子樹，所以屬于左左情況狈孔。

image.png

圖4

紅黑樹

紅黑樹的定義:紅黑樹是一種自平衡二叉查找樹雄卷，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)搓蚪，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的丁鹉，稱之為"對稱二叉B樹"妒潭，它現(xiàn)代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是復(fù)雜的鳄炉，但它的操作有著良好的最壞情況運(yùn)行時(shí)間杜耙，并且在實(shí)踐中是高效的:它可以在O(logn)時(shí)間內(nèi)做查找，插入和刪除拂盯，這里的n是樹中元素的數(shù)目佑女。
紅黑樹和AVL樹一樣都對插入時(shí)間、刪除時(shí)間和查找時(shí)間提供了最好可能的最壞情況擔(dān)保。這不只是使它們在時(shí)間敏感的應(yīng)用如實(shí)時(shí)應(yīng)用（real time application）中有價(jià)值团驱，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為建造板塊的價(jià)值摸吠；例如，在計(jì)算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹嚎花。此外寸痢，紅黑樹還是2-3-4樹的一種等同，它們的思想是一樣的紊选，只不過紅黑樹是2-3-4樹用二叉樹的形式表示的啼止。
紅黑樹的性質(zhì)：
紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色兵罢。在二叉查找樹強(qiáng)制的一般要求以外献烦，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。
性質(zhì)2. 根是黑色卖词。
性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）巩那。
性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)此蜈。)
性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)即横。

紅黑樹的圖例

這些約束確保了紅黑樹的關(guān)鍵特性:

從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個(gè)樹大致上是平衡的裆赵。因?yàn)椴僮鞅热绮迦攵簟h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例，這個(gè)在高度上的理論上限允許紅黑樹在最壞情況下都是高效的顾瞪，而不同于普通的二叉查找樹舔庶。
　　要知道為什么這些性質(zhì)確保了這個(gè)結(jié)果抛蚁，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個(gè)毗連的紅色節(jié)點(diǎn)就足夠了陈醒。最短的可能路徑都是黑色節(jié)點(diǎn)，最長的可能路徑有交替的紅色和黑色節(jié)點(diǎn)瞧甩。因?yàn)楦鶕?jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)钉跷，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

紅黑樹的自平衡操作：
因?yàn)槊恳粋€(gè)紅黑樹也是一個(gè)特化的二叉查找樹肚逸，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同爷辙。然而，在紅黑樹上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致不再符合紅黑樹的性質(zhì)朦促∠チ溃恢復(fù)紅黑樹的性質(zhì)需要少量(O(logn))的顏色變更(實(shí)際是非常快速的)和不超過三次樹旋轉(zhuǎn)(對于插入操作是兩次)务冕。雖然插入和刪除很復(fù)雜血当，但操作時(shí)間仍可以保持為O(logn) 次。

我們首先以二叉查找樹的方法增加節(jié)點(diǎn)并標(biāo)記它為紅色。如果設(shè)為黑色臊旭，就會(huì)導(dǎo)致根到葉子的路徑上有一條路上落恼，多一個(gè)額外的黑節(jié)點(diǎn)，這個(gè)是很難調(diào)整的（違背性質(zhì)5）离熏。但是設(shè)為紅色節(jié)點(diǎn)后佳谦，可能會(huì)導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突，那么可以通過顏色調(diào)換（color flips）和樹旋轉(zhuǎn)來調(diào)整滋戳。下面要進(jìn)行什么操作取決于其他臨近節(jié)點(diǎn)的顏色钻蔑。同人類的家族樹中一樣，我們將使用術(shù)語叔父節(jié)點(diǎn)來指一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)奸鸯。注意:

性質(zhì)1和性質(zhì)3總是保持著矢棚。
性質(zhì)4只在增加紅色節(jié)點(diǎn)、重繪黑色節(jié)點(diǎn)為紅色府喳，或做旋轉(zhuǎn)時(shí)受到威脅蒲肋。
性質(zhì)5只在增加黑色節(jié)點(diǎn)、重繪紅色節(jié)點(diǎn)為黑色钝满，或做旋轉(zhuǎn)時(shí)受到威脅兜粘。

插入操作：
假設(shè)，將要插入的節(jié)點(diǎn)標(biāo)為N弯蚜，N的父節(jié)點(diǎn)標(biāo)為P孔轴，N的祖父節(jié)點(diǎn)標(biāo)為G，N的叔父節(jié)點(diǎn)標(biāo)為U碎捺。在圖中展示的任何顏色要么是由它所處情形這些所作的假定路鹰，要么是假定所暗含的。
　　情形1: 該樹為空樹收厨，直接插入根結(jié)點(diǎn)的位置晋柱，違反性質(zhì)1，把節(jié)點(diǎn)顏色有紅改為黑即可诵叁。
　　情形2: 插入節(jié)點(diǎn)N的父節(jié)點(diǎn)P為黑色雁竞，不違反任何性質(zhì)土至，無需做任何修改涣狗。在這種情形下，樹仍是有效的纳令。性質(zhì)5也未受到威脅侥锦，盡管新節(jié)點(diǎn)N有兩個(gè)黑色葉子子節(jié)點(diǎn)进栽；但由于新節(jié)點(diǎn)N是紅色，通過它的每個(gè)子節(jié)點(diǎn)的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數(shù)目的黑色節(jié)點(diǎn)恭垦，所以依然滿足這個(gè)性質(zhì)快毛。

注： 情形1很簡單盲厌，情形2中P為黑色，一切安然無事祸泪，但P為紅就不一樣了吗浩，下邊是P為紅的各種情況，也是真正難懂的地方没隘。

情形3: 如果父節(jié)點(diǎn)P和叔父節(jié)點(diǎn)U二者都是紅色懂扼，(此時(shí)新插入節(jié)點(diǎn)N做為P的左子節(jié)點(diǎn)或右子節(jié)點(diǎn)都屬于情形3,這里右圖僅顯示N做為P左子的情形)則我們可以將它們兩個(gè)重繪為黑色并重繪祖父節(jié)點(diǎn)G為紅色(用來保持性質(zhì)4)。現(xiàn)在我們的新節(jié)點(diǎn)N有了一個(gè)黑色的父節(jié)點(diǎn)P右蒲。因?yàn)橥ㄟ^父節(jié)點(diǎn)P或叔父節(jié)點(diǎn)U的任何路徑都必定通過祖父節(jié)點(diǎn)G阀湿，在這些路徑上的黑節(jié)點(diǎn)數(shù)目沒有改變。但是瑰妄，紅色的祖父節(jié)點(diǎn)G的父節(jié)點(diǎn)也有可能是紅色的陷嘴，這就違反了性質(zhì)4。為了解決這個(gè)問題间坐，我們在祖父節(jié)點(diǎn)G上遞歸地進(jìn)行上述情形的整個(gè)過程（把G當(dāng)成是新加入的節(jié)點(diǎn)進(jìn)行各種情形的檢查）灾挨。比如，G為根節(jié)點(diǎn)竹宋，那我們就直接將G變?yōu)楹谏ㄇ樾?）劳澄；如果G不是根節(jié)點(diǎn)，而它的父節(jié)點(diǎn)為黑色蜈七，那符合所有的性質(zhì)秒拔，直接插入即可（情形2）；如果G不是根節(jié)點(diǎn)飒硅，而它的父節(jié)點(diǎn)為紅色砂缩，則遞歸上述過程（情形3）。

image.png

image.png

image.png

注: 插入實(shí)際上是原地算法闺魏，因?yàn)樯鲜鏊姓{(diào)用都使用了尾部遞歸未状。

刪除操作：
如果需要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)兒子，那么問題可以被轉(zhuǎn)化成刪除另一個(gè)只有一個(gè)兒子的節(jié)點(diǎn)的問題析桥。對于二叉查找樹司草，在刪除帶有兩個(gè)非葉子兒子的節(jié)點(diǎn)的時(shí)候，我們找到要么在它的左子樹中的最大元素泡仗、要么在它的右子樹中的最小元素翻伺，并把它的值轉(zhuǎn)移到要?jiǎng)h除的節(jié)點(diǎn)中。我們接著刪除我們從中復(fù)制出值的那個(gè)節(jié)點(diǎn)沮焕，它必定有少于兩個(gè)非葉子的兒子吨岭。因?yàn)橹皇菑?fù)制了一個(gè)值，不違反任何性質(zhì)峦树，這就把問題簡化為如何刪除最多有一個(gè)兒子的節(jié)點(diǎn)的問題辣辫。它不關(guān)心這個(gè)節(jié)點(diǎn)是最初要?jiǎng)h除的節(jié)點(diǎn)還是我們從中復(fù)制出值的那個(gè)節(jié)點(diǎn)。
　　我們只需要討論刪除只有一個(gè)兒子的節(jié)點(diǎn)(如果它兩個(gè)兒子都為空魁巩，即均為葉子急灭，我們?nèi)我鈱⑵渲幸粋€(gè)看作它的兒子)。如果我們刪除一個(gè)紅色節(jié)點(diǎn)（此時(shí)該節(jié)點(diǎn)的兒子將都為葉子節(jié)點(diǎn)）谷遂，它的父親和兒子一定是黑色的葬馋。所以我們可以簡單的用它的黑色兒子替換它，并不會(huì)破壞性質(zhì)3和性質(zhì)4肾扰。通過被刪除節(jié)點(diǎn)的所有路徑只是少了一個(gè)紅色節(jié)點(diǎn)畴嘶，這樣可以繼續(xù)保證性質(zhì)5。另一種簡單情況是在被刪除節(jié)點(diǎn)是黑色而它的兒子是紅色的時(shí)候集晚。如果只是去除這個(gè)黑色節(jié)點(diǎn)窗悯，用它的紅色兒子頂替上來的話，會(huì)破壞性質(zhì)5偷拔，但是如果我們重繪它的兒子為黑色蒋院，則曾經(jīng)通過它的所有路徑將通過它的黑色兒子亏钩，這樣可以繼續(xù)保持性質(zhì)5。
　　需要進(jìn)一步討論的是在要?jiǎng)h除的節(jié)點(diǎn)和它的兒子二者都是黑色的時(shí)候欺旧，這是一種復(fù)雜的情況姑丑。我們首先把要?jiǎng)h除的節(jié)點(diǎn)替換為它的兒子。出于方便辞友，稱呼這個(gè)兒子為N(在新的位置上)栅哀，稱呼它的兄弟(它父親的另一個(gè)兒子)為S。在下面的示意圖中踏枣，我們還是使用P稱呼N的父親昌屉，SL稱呼S的左兒子，SR稱呼S的右兒子茵瀑。
　　如果N和它初始的父親是黑色间驮，則刪除它的父親導(dǎo)致通過N的路徑都比不通過它的路徑少了一個(gè)黑色節(jié)點(diǎn)。因?yàn)檫@違反了性質(zhì)5马昨，樹需要被重新平衡竞帽。有幾種情形需要考慮:
　　情形1: N是新的根。在這種情形下鸿捧，我們就做完了屹篓。我們從所有路徑去除了一個(gè)黑色節(jié)點(diǎn)，而新根是黑色的匙奴，所以性質(zhì)都保持著堆巧。

注意: 在情形2、5和6下泼菌，我們假定N是它父親的左兒子谍肤。如果它是右兒子，則在這些情形下的左和右應(yīng)當(dāng)對調(diào)哗伯。

情形2: S是紅色荒揣。在這種情形下我們在N的父親上做左旋轉(zhuǎn)，把紅色兄弟轉(zhuǎn)換成N的祖父焊刹，我們接著對調(diào)N的父親和祖父的顏色系任。完成這兩個(gè)操作后，盡管所有路徑上黑色節(jié)點(diǎn)的數(shù)目沒有改變虐块，但現(xiàn)在N有了一個(gè)黑色的兄弟和一個(gè)紅色的父親（它的新兄弟是黑色因?yàn)樗羌t色S的一個(gè)兒子）俩滥，所以我們可以接下去按情形4、情形5或情形6來處理非凌。

image.png

image.png

image.png

image.png

此時(shí)癌刽，如果一個(gè)路徑不通過N役首，則有兩種可能性:
它通過N的新兄弟。那么它以前和現(xiàn)在都必定通過S和N的父親显拜，而它們只是交換了顏色衡奥。所以路徑保持了同樣數(shù)目的黑色節(jié)點(diǎn)。
它通過N的新叔父远荠，S的右兒子矮固。那么它以前通過S、S的父親和S的右兒子矮台，但是現(xiàn)在只通過S乏屯，它被假定為它以前的父親的顏色，和S的右兒子瘦赫，它被從紅色改變?yōu)楹谏皆巍：铣尚Ч沁@個(gè)路徑通過了同樣數(shù)目的黑色節(jié)點(diǎn)。
在任何情況下确虱，在這些路徑上的黑色節(jié)點(diǎn)數(shù)目都沒有改變含友。所以我們恢復(fù)了性質(zhì)4。在示意圖中的白色節(jié)點(diǎn)可以是紅色或黑色校辩，但是在變換前后都必須指定相同的顏色窘问。

image.png

B樹

具體講解之前，有一點(diǎn)宜咒，再次強(qiáng)調(diào)下：B-樹惠赫，即為B樹。因?yàn)锽樹的原英文名稱為B-tree（B-tree樹即B樹故黑，B即Balanced儿咱，平衡的意思），而國內(nèi)很多人喜歡把B-tree譯作B-樹场晶，其實(shí)混埠，這是個(gè)非常不好的直譯，很容易讓人產(chǎn)生誤解诗轻。如人們可能會(huì)以為B-樹是一種樹钳宪，而B樹又是一種一種樹。而事實(shí)上是，B-tree就是指的B樹吏颖。特此說明搔体。

用階定義B樹： B 樹又叫平衡多路查找樹。一棵m階的B 樹

B樹定義

1.樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（）侦高；
2.除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外嫉柴，其它每個(gè)結(jié)點(diǎn)至少有個(gè)孩子）厌杜；
3.若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)奉呛，則至少有2個(gè)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)夯尽，整棵樹只有一個(gè)根節(jié)點(diǎn)）瞧壮；
4.所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢失敗的接點(diǎn)匙握，實(shí)際上這些結(jié)點(diǎn)不存在咆槽，指向這些結(jié)點(diǎn)的指針都為null)。
5.每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (·n圈纺，P₀秦忿，K₁，P₁蛾娶，K₂灯谣，P₂，......蛔琅，K_n胎许，P_n)。其中：

• a) K_i(i=1...n)為關(guān)鍵字罗售，且關(guān)鍵字按順序升序排序K(i-1)< Ki辜窑。
• b) P_i為指向子樹的節(jié)點(diǎn)，且指針P_i-1指向子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于K_i寨躁，但都大于K_i-1穆碎。
• c) 關(guān)鍵字的個(gè)數(shù)n必須滿足：。

B樹

從圖上和定義中B樹的特征如下:

B+樹

一棵m階B+樹的定義為：
①樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；
②根結(jié)點(diǎn)至少有1棵子樹最筒；除根結(jié)點(diǎn)之外贺氓，每個(gè)結(jié)點(diǎn)至少有 棵子樹；
③所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，按從小到大的順序存放全部關(guān)鍵字辙培，各葉結(jié)點(diǎn)順序鏈接蔑水；
④有n棵子樹的結(jié)點(diǎn)有n個(gè)關(guān)鍵字；
⑤所有非葉子結(jié)點(diǎn)可以看成葉結(jié)點(diǎn)的索引扬蕊，結(jié)點(diǎn)中關(guān)鍵字K_i與指向子樹的指針P_i構(gòu)成對子樹的索引項(xiàng)(K_i,P_i)搀别，K_i是子樹中最大的關(guān)鍵字。

B+樹

一棵m階B+樹是B樹的特殊情形尾抑，它與B樹的不同之外在于：

1.所有關(guān)鍵字都存放與所有的葉子節(jié)點(diǎn)（B-樹的關(guān)鍵字不全在葉子節(jié)點(diǎn)上歇父，而是分布在整棵樹上），非葉子結(jié)點(diǎn)的關(guān)鍵字是其子樹中最大或者最小關(guān)鍵字的拷貝再愈；
2.葉子結(jié)點(diǎn)包含了全部關(guān)鍵字及指向相應(yīng)數(shù)據(jù)記錄存放地址的指針榜苫，且葉子結(jié)點(diǎn)本身按關(guān)鍵字值從小到大順序鏈接（B樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息）；
3.有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字翎冲； (B~樹是n棵子樹有n+1個(gè)關(guān)鍵字)
4.所有的非葉子點(diǎn)可以看成是索引部分垂睬，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最小）關(guān)鍵字抗悍。 (B~樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)

一般B+樹的實(shí)現(xiàn)會(huì)增加兩個(gè)頭指針一個(gè)指向根節(jié)點(diǎn)驹饺，另一個(gè)指向關(guān)鍵字最小的元素，因此B+樹有兩種遍歷的方式：

public class BPlusTree {  
      
    /** 根節(jié)點(diǎn) */  
    protected Node root;  
      
    /** 階數(shù)缴渊，M值 */  
    protected int order;  
      
    /** 葉子節(jié)點(diǎn)的鏈表頭(關(guān)鍵字最小的元素)*/  
    protected Node head;  
}
/**
*樹的結(jié)點(diǎn)
*/
class Node {  
      
    /** 是否為葉子節(jié)點(diǎn) */  
    protected boolean isLeaf;  
      
    /** 是否為根節(jié)點(diǎn)*/  
    protected boolean isRoot;  
  
    /** 父節(jié)點(diǎn) */  
    protected Node parent;  
      
    /** 葉節(jié)點(diǎn)的前節(jié)點(diǎn)*/  
    protected Node previous;  
      
    /** 葉節(jié)點(diǎn)的后節(jié)點(diǎn)*/  
    protected Node next;      
      
    /** 節(jié)點(diǎn)的關(guān)鍵字 */  
    protected List<Entry<Comparable, Object>> entries;  
      
    /** 子節(jié)點(diǎn) */  
    protected List<Node> children;  
}

B*樹

B*樹是B+樹的變體赏壹，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針，將結(jié)點(diǎn)的最低利用率從提高到疟暖。

B樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為M卡儒，即塊的最低使用率為（代替B+樹的）；

B+樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)俐巴，分配一個(gè)新的結(jié)點(diǎn)骨望，并將原結(jié)點(diǎn)中的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針欣舵；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)擎鸠，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針缘圈；

B*樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)劣光，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中糟把，再在原結(jié)點(diǎn)插入關(guān)鍵字绢涡，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了遣疯，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)雄可，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針；

所以数苫，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低聪舒，空間使用率更高。

Trie樹

散列（哈希）

什么是哈希表

哈希表是以 Key-Value 形式存儲的的數(shù)據(jù)結(jié)構(gòu)虐急，當(dāng)我們需要查找某個(gè)值箱残，只需要輸入相應(yīng)的Key值即可。
首先我們看看整個(gè)哈希表的邏輯機(jī)構(gòu)圖

邏輯結(jié)構(gòu)圖

哈希的整個(gè)思路也比較簡單止吁，首先將Key按照特定的哈希算法（算法的選擇被辑，根據(jù)需要而定）函數(shù)H(Key)生成哈希值，再將哈希值轉(zhuǎn)為數(shù)組的一個(gè)索引（Index）赏殃；因?yàn)椴煌墓Ｖ悼赡塬@得同意額索引敷待，也有可能不同的Key 但哈希值相同，所以接下來就是處理索引沖突仁热。

常見的哈希函數(shù)

.正整數(shù)
如果Key是正整數(shù)，常用的哈希算法就是對Key取模運(yùn)算勾哩，也就是對于長度為L的數(shù)組抗蠢，那么對于任意的正整數(shù)N，獲得 index = N%L
.字符串
對于字符串也可以采用取模的運(yùn)算 來獲取索引值思劳，但是須將字符串轉(zhuǎn)為正整數(shù)迅矛，常用的方法就是將字符串中的每個(gè)字符進(jìn)行hash
例如Java中：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

哈希沖突

拉鏈法

通過H（key）可以將哈希值轉(zhuǎn)為0 至 L-1范圍內(nèi)的索引，但是對于索引相同的情況潜叛，就需要有一種方法來解決這種問題秽褒。
一種比較簡單的辦法就是，將長度為L 的數(shù)組的每一個(gè)元素指向一個(gè)條鏈表威兜，鏈表中的每一個(gè)節(jié)點(diǎn)都存儲散列值為該索引的鍵值對销斟，這就是拉鏈法。下圖很清楚的描述了什么是拉鏈法椒舵。
如下圖所示

網(wǎng)絡(luò)圖片

圖中蚂踊，”John Smith”和”Sandra Dee” 通過哈希函數(shù)都指向了152 這個(gè)索引，該索引又指向了一個(gè)鏈表笔宿， 在鏈表中依次存儲了這兩個(gè)字符串犁钟。
該方法的基本思想就是選擇足夠長度的數(shù)組，使得所有的鏈表都盡可能的短小泼橘，以保證查找的效率涝动。對采用拉鏈法的哈希實(shí)現(xiàn)的查找分為兩步，首先是根據(jù)散列值找到對應(yīng)的鏈表炬灭，然后沿著鏈表順序找到相應(yīng)的哈希值H(key)醋粟。此鏈表可以自己實(shí)現(xiàn)。當(dāng)然，您也可以使用Java里面內(nèi)置的LinkedList昔穴。使用拉鏈法最關(guān)鍵的就是選擇合適長度的數(shù)組镰官，使得因?yàn)殒湵硖L而增加查找時(shí)間，又不會(huì)因?yàn)榭罩玫逆湵淼睦速M(fèi)空間吗货。

開放地址法

這種方法也稱再散列法泳唠，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)，以p為基礎(chǔ)宙搬，產(chǎn)生另一個(gè)哈希地址p₁笨腥，如果p₁仍然沖突，再以p為基礎(chǔ)勇垛，產(chǎn)生另一個(gè)哈希地址p₂脖母，以此類推直到找出一個(gè)不沖突的哈希地址p_i ，將相應(yīng)元素存入其中闲孤。這種方法有一個(gè)通用的再散列函數(shù)形式：
Hi=（H（key）+d_i）% m （i=1谆级，2，…讼积，n)
其中H（key）為哈希函數(shù)肥照，m 為表長，d_i稱為增量序列勤众。增量序列的取值方式不同舆绎，相應(yīng)的再散列方式也不同。主要有以下三種：

1.線性探測再散列法

d_i(i=1们颜，2吕朵，3，…窥突，m-1)
這種方法的特點(diǎn)是：沖突發(fā)生時(shí)努溃，順序查看表中下一單元地址，直到找出一個(gè)空單元或查遍全表波岛。

2.二次探測再散列

d_i=1²茅坛，-1²，2²则拷，-2²贡蓖，…，k²煌茬，-k² ( k<=m/2)
這種方法的特點(diǎn)是：沖突發(fā)生時(shí)斥铺，在表的左右進(jìn)行跳躍式探測，比較靈活坛善。

3.偽隨機(jī)探測再散列

d_i=偽隨機(jī)數(shù)序列晾蜘。具體實(shí)現(xiàn)時(shí)邻眷，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，（如i=(i+p) % m）剔交，并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)肆饶。

例如，已知哈希表長度m=11岖常，哈希函數(shù)為：H（key）= key % 11驯镊，則H（47）=3，H（26）=4竭鞍，H（60）=5板惑，假設(shè)下一個(gè)關(guān)鍵字為69，則H（69）=3偎快，與47沖突冯乘。
如果用線性探測再散列處理沖突，下一個(gè)哈希地址為H₁=（3 + 1）% 11 = 4晒夹，仍然沖突裆馒，再找下一個(gè)哈希地址為H₂=（3 + 2）% 11 = 5，還是沖突惋戏，繼續(xù)找下一個(gè)哈希地址為H₃=（3 + 3）% 11 = 6领追，此時(shí)不再?zèng)_突，將69填入5號單元响逢。
如果用二次探測再散列處理沖突，下一個(gè)哈希地址為H₁=3 + 1²）% 11 = 4棕孙，仍然沖突舔亭，再找下一個(gè)哈希地址為H₂=（3 - 1²）% 11 = 2，此時(shí)不再?zèng)_突蟀俊，將69填入2號單元钦铺。
如果用偽隨機(jī)探測再散列處理沖突，且偽隨機(jī)數(shù)序列為：2肢预，5矛洞，9，……..烫映，則下一個(gè)哈希地址為H₁=（3 + 2）% 11 = 5沼本，仍然沖突，再找下一個(gè)哈希地址為H₂=（3 + 5）% 11 = 8锭沟，此時(shí)不再?zèng)_突抽兆，將69填入8號單元。

再哈希法

這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
H=RH_i（key） （i=1族淮，2辫红，…凭涂，k)
當(dāng)哈希地址H=RH_i（key）發(fā)生沖突時(shí)，再計(jì)算H=RH_i+1（key贴妻，以此類推直到?jīng)_突不再產(chǎn)生切油。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間名惩。

建立公共溢出區(qū)

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分澎胡，凡是和基本表發(fā)生沖突的元素，一律填入溢出表绢片。

哈希碰撞攻擊

我們知道如果哈希函數(shù)選擇不當(dāng)會(huì)使得大量的鍵都會(huì)映射到相同的索引上滤馍，不管是采用拉鏈法還是開放尋址法解決沖突，在后面查找的時(shí)候都需要進(jìn)行多次探測或者查找底循， 在很多時(shí)候會(huì)使得哈希表的查找效率退化巢株，而不再是常數(shù)時(shí)間。下圖清楚的描述了退化后的哈希表：

hash弱化

哈希表攻擊就是通過精心構(gòu)造哈希函數(shù)熙涤，使得所有的鍵經(jīng)過哈希函數(shù)后都映射到同一個(gè)或者幾個(gè)索引上阁苞，將哈希表退化為了一個(gè)單鏈表，這樣哈希表的各種操作祠挫，比如插入那槽，查找都從O(1)退化到了鏈表的查找操作，這樣就會(huì)消耗大量的CPU資源等舔，導(dǎo)致系統(tǒng)無法響應(yīng)骚灸，從而達(dá)到拒絕服務(wù)供給(Denial of Service, Dos)的目的。之前由于多種編程語言的哈希算法的“非隨機(jī)”而出現(xiàn)了Hash碰撞的DoS安全漏洞慌植，在ASP.NET中也曾出現(xiàn)過這一問題甚牲。

堆(優(yōu)先隊(duì)列)

二叉堆

d-堆

左式堆

斜堆

二項(xiàng)隊(duì)列

參考資料

https://blog.csdn.net/v_JULY_v/article/details/6530142/