數據結構介紹
數據結構 : 數據用什麼樣的方式組合在一起。
常見數據結構
數據存儲的常用結構有：棧、隊列、數組、鍊表和紅黑樹。我們分別來了解一下：
棧
棧：stack,又稱堆棧，它是運算受限的線性表，其限制是僅允許在標的一端進行插入和刪除操作，不允許在其他任何位置進行添加、查找、刪除等操作。
簡單的說：採用該結構的集合，對元素的存取有如下的特點
先進後出（即，存進去的元素，要在後它後面的元素依次取出後，才能取出該元素）。例如，子彈壓進彈夾，先壓進去的子彈在下面，後壓進去的子彈在上面，當開槍時，先彈出上面的子彈，然後才能彈出下面的子彈。棧的入口、出口的都是棧的頂端位置。
這裡兩個名詞需要注意：
壓棧：就是存元素。即，把元素存儲到棧的頂端位置，棧中已有元素依次向棧底方向移動一個位置。彈棧：就是取元素。即，把棧的頂端位置元素取出，棧中已有元素依次向棧頂方向移動一個位置。
隊列
隊列：queue,簡稱隊，它同堆棧一樣，也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。
簡單的說，採用該結構的集合，對元素的存取有如下的特點：
先進先出（即，存進去的元素，要在後它前面的元素依次取出後，才能取出該元素）。例如，小火車過山洞，車頭先進去，車尾後進去；車頭先出來，車尾後出來。隊列的入口、出口各佔一側。例如，下圖中的左側為入口，右側為出口。
數組
數組:Array,是有序的元素序列，數組是在內存中開闢一段連續的空間，並在此空間存放元素。就像是一排出租屋，有100個房間，從001到100每個房間都有固定編號，通過編號就可以快速找到租房子的人。
簡單的說,採用該結構的集合，對元素的存取有如下的特點：
查找元素快：通過索引，可以快速訪問指定位置的元素
增刪元素慢指定索引位置增加元素：需要創建一個新數組，將指定新元素存儲在指定索引位置，再把原數組元素根據索引，複製到新數組對應索引的位置。如下圖
指定索引位置刪除元素：需要創建一個新數組，把原數組元素根據索引，複製到新數組對應索引的位置，原數組中指定索引位置元素不複製到新數組中。如下圖
鍊表
鍊表:linked list,由一系列結點node（鍊表中每一個元素稱為結點）組成，結點可以在運行時i動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。我們常說的鍊表結構有單向鍊表與雙向鍊表，那麼這裡給大家介紹的是單向鍊表。
簡單的說，採用該結構的集合，對元素的存取有如下的特點：
多個結點之間，通過地址進行連接。例如，多個人手拉手，每個人使用自己的右手拉住下個人的左手，依次類推，這樣多個人就連在一起了。查找元素慢：想查找某個元素，需要通過連接的節點，依次向後查找指定元素增刪元素快：
樹數據結構，樹是有很多節點組成的
樹基本結構介紹
樹具有的特點：
每一個節點有零個或者多個子節點沒有父節點的節點稱之為根節點，一個樹最多有一個根節點。每一個非根節點有且只有一個父節點
二叉樹
如果樹中的每個節點的子節點的個數不超過2，那麼該樹就是一個二叉樹。
二叉查找樹/二叉排序樹
二叉查找樹的特點：
左子樹上所有的節點的值均小於等於他的根節點的值右子樹上所有的節點值均大於或者等於他的根節點的值每一個子節點最多有兩個子樹
案例演示(20,18,23,22,17,24,19)數據的存儲過程；
增刪改查的性能都很高！！！
遍歷獲取元素的時候可以按照"左中右"的順序進行遍歷；
注意：二叉查找樹存在的問題：會出現"瘸子"的現象，影響查詢效率。
平衡二叉樹
（基於查找二叉樹，但是讓樹不要太高，儘量讓樹的元素均衡分布。這樣綜合性能就高了）
概述
為了避免出現"瘸子"的現象，減少樹的高度，提高我們的搜素效率，又存在一種樹的結構："平衡二叉樹"
規則：它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹
如下圖所示：
如下圖所示，左圖是一棵平衡二叉樹，根節點10，左右兩子樹的高度差是1，而右圖，雖然根節點左右兩子樹高度差是0，但是右子樹15的左右子樹高度差為2，不符合定義，
所以右圖不是一棵平衡二叉樹。
旋轉
在構建一棵平衡二叉樹的過程中，當有新的節點要插入時，檢查是否因插入後而破壞了樹的平衡，如果是，則需要做旋轉去改變樹的結構。
左旋：
左旋就是將節點的右支往左拉，右子節點變成父節點，並把晉升之後多餘的左子節點出讓給降級節點的右子節點；
右旋：
將節點的左支往右拉，左子節點變成了父節點，並把晉升之後多餘的右子節點出讓給降級節點的左子節點
舉個例子，像上圖是否平衡二叉樹的圖裡面，左圖在沒插入前"19"節點前，該樹還是平衡二叉樹，但是在插入"19"後，導致了"15"的左右子樹失去了"平衡"，
所以此時可以將"15"節點進行左旋，讓"15"自身把節點出讓給"17"作為"17"的左樹，使得"17"節點左右子樹平衡，而"15"節點沒有子樹，左右也平衡了。如下圖，
由於在構建平衡二叉樹的時候，當有新節點插入時，都會判斷插入後時候平衡，這說明了插入新節點前，都是平衡的，也即高度差絕對值不會超過1。當新節點插入後，
有可能會有導致樹不平衡，這時候就需要進行調整，而可能出現的情況就有4種，分別稱作左左，左右，右左，右右
左左
左左即為在原來平衡的二叉樹上，在節點的左子樹的左子樹下，有新節點插入，導致節點的左右子樹的高度差為2，如下即為"10"節點的左子樹"7"，的左子樹"4"，插入了節點"5"或"3"導致失衡。
左左調整其實比較簡單，只需要對節點進行右旋即可，如下圖，對節點"10"進行右旋，
左右
左右即為在原來平衡的二叉樹上，在節點的左子樹的右子樹下，有新節點插入，導致節點的左右子樹的高度差為2，如上即為"11"節點的左子樹"7"，的右子樹"9"，
插入了節點"10"或"8"導致失衡。
左右的調整就不能像左左一樣，進行一次旋轉就完成調整。我們不妨先試著讓左右像左左一樣對"11"節點進行右旋，結果圖如下，右圖的二叉樹依然不平衡，而右圖就是接下來要
講的右左，即左右跟右左互為鏡像，左左跟右右也互為鏡像。
左右這種情況，進行一次旋轉是不能滿足我們的條件的，正確的調整方式是，將左右進行第一次旋轉，將左右先調整成左左，然後再對左左進行調整，從而使得二叉樹平衡。
即先對上圖的節點"7"進行左旋，使得二叉樹變成了左左，之後再對"11"節點進行右旋，此時二叉樹就調整完成，如下圖:
右左
右左即為在原來平衡的二叉樹上，在節點的右子樹的左子樹下，有新節點插入，導致節點的左右子樹的高度差為2，如上即為"11"節點的右子樹"15"，的左子樹"13"，
插入了節點"12"或"14"導致失衡。
前面也說了，右左跟左右其實互為鏡像，所以調整過程就反過來，先對節點"15"進行右旋，使得二叉樹變成右右，之後再對"11"節點進行左旋，此時二叉樹就調整完成，如下圖:
右右
右右即為在原來平衡的二叉樹上，在節點的右子樹的右子樹下，有新節點插入，導致節點的左右子樹的高度差為2，如下即為"11"節點的右子樹"13"，的左子樹"15"，插入了節點
"14"或"19"導致失衡。
右右只需對節點進行一次左旋即可調整平衡，如下圖，對"11"節點進行左旋。
紅黑樹
就是平衡的二叉查找樹！！
概述
紅黑樹是一種自平衡的二叉查找樹，是計算機科學中用到的一種數據結構，它是在1972年由Rudolf Bayer發明的，當時被稱之為平衡二叉B樹，後來，在1978年被
Leoj.Guibas和Robert Sedgewick修改為如今的"紅黑樹"。它是一種特殊的二叉查找樹，紅黑樹的每一個節點上都有存儲位表示節點的顏色，可以是紅或者黑；
紅黑樹不是高度平衡的，它的平衡是通過"紅黑樹的特性"進行實現的；
紅黑樹的特性：
每一個節點或是紅色的，或者是黑色的。根節點必須是黑色每個葉節點(Nil)是黑色的；（如果一個節點沒有子節點或者父節點，則該節點相應的指針屬性值為Nil，這些Nil視為葉節點）如果某一個節點是紅色，那麼它的子節點必須是黑色(不能出現兩個紅色節點相連的情況)對每一個節點，從該節點到其所有後代葉節點的簡單路徑上，均包含相同數目的黑色節點；
如下圖所示就是一個
在進行元素插入的時候，和之前一樣； 每一次插入完畢以後，使用黑色規則進行校驗，如果不滿足紅黑規則，就需要通過變色，左旋和右旋來調整樹，使其滿足紅黑規則；