算法中的基本數(shù)據(jù)結(jié)構(gòu)，從邏輯上分可劃分為兩大類：線性結(jié)構(gòu)、非線性結(jié)構(gòu)。
注：線性和非線性，不代表存儲(chǔ)結(jié)構(gòu)是線性或是非線性，這只是一種邏輯上的劃分，比如可以用數(shù)組存儲(chǔ)二叉樹；一般而言，有前驅(qū)和后繼的，屬線性結(jié)構(gòu)，比如數(shù)組和鏈表。
線性結(jié)構(gòu)
線性結(jié)構(gòu)有：數(shù)組、棧、鏈表、隊(duì)列；
數(shù)組（array）
數(shù)組幾乎在每種語言入門時(shí)都會(huì)學(xué)習(xí)到，這里不再專門介紹；
棧
"棧" 這個(gè)名稱，可類比于一組物體的堆疊，比如一摞書（更直觀的類比，如將子彈壓入彈夾，最后壓入的最先射出）。
棧也是一種受限的序列，只能夠操作棧頂，不管入棧還是出棧，都是在棧頂操作。
計(jì)算機(jī)科學(xué)中，棧 (stack) 是一種抽象數(shù)據(jù)類型，用于表示元素的集合，具有兩種主要操作：
- push, 添加元素到棧的頂端（末尾）；
- pop, 移除棧最頂端（末尾）的元素；
以上兩種操作可簡(jiǎn)單概括為后進(jìn)先出 (LIFO = last in, first out)；
此外，應(yīng)有一個(gè) peek 操作用于訪問棧當(dāng)前頂端（末尾）的元素（只返回不彈出）。
隊(duì)列（queue）
隊(duì)列，這個(gè)名稱，可類比為現(xiàn)實(shí)生活中的排隊(duì)（不插隊(duì)的那種）；
計(jì)算機(jī)科學(xué)中，隊(duì)列 是一種特殊的抽象數(shù)據(jù)類型集合，集合中的實(shí)體按順序保存。
和數(shù)組不同，隊(duì)列是一種受限的序列；
受限就受限于它只能操作 隊(duì)尾和隊(duì)首，并只能在隊(duì)尾添加元素，在隊(duì)首刪除元素，不像數(shù)組可以任意操作。
隊(duì)列作為一種常見數(shù)據(jù)結(jié)構(gòu)，有著非常廣泛的應(yīng)用， 比如消息隊(duì)列。
隊(duì)列的基本操作有兩種：
向隊(duì)列的末端位置添加實(shí)體，稱為入隊(duì)；
從隊(duì)列的前端位置移除實(shí)體，稱為出隊(duì)。
隊(duì)列中的元素先進(jìn)先出 FIFO (first in, first out) ：
隊(duì)列的應(yīng)用
做過性能優(yōu)化的朋友，對(duì)于 “HTTP 1.1 的隊(duì)頭阻塞問題” 應(yīng)該不會(huì)陌生；
具體來說就是 HTTP2 解決了 HTTP1.1 中的隊(duì)頭阻塞問題。
什么是 HTTP1.1 的隊(duì)頭阻塞問題，以及 HTTP2 怎么解決的，這里簡(jiǎn)單說下：
其實(shí)隊(duì)頭阻塞是一個(gè)專有名詞，不僅僅在 HTTP 中存在，交換器等其他地方也會(huì)涉及這個(gè)問題；
實(shí)際上引起這個(gè)問題的根本原因是使用了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。
HTTP 協(xié)議規(guī)定， 對(duì)于同一個(gè) tcp 連接，所有的 http1.0 請(qǐng)求放入隊(duì)列中，只有前一個(gè)請(qǐng)求的響應(yīng)收到了，才能發(fā)送下一個(gè)請(qǐng)求，這個(gè)時(shí)候就發(fā)生了阻塞，并且這個(gè)阻塞主要發(fā)生在客戶端。
就好比等紅綠燈，即使旁邊的綠燈亮了，你當(dāng)前所在的車道依然是紅燈，你還是不能走，還是要等著。
HTTP/1.1 的改進(jìn)
在HTTP/1.0 中每一次請(qǐng)求都需要建立一個(gè) TCP 連接，請(qǐng)求結(jié)束后立即斷開連接；
在HTTP/1.1 中，每一個(gè)連接都默認(rèn)是長(zhǎng)連接 (persistent connection)；
對(duì)于同一個(gè) tcp 連接，允許一次發(fā)送多個(gè) http1.1 請(qǐng)求，也就是說，不必等前一個(gè)響應(yīng)收到，就可以發(fā)送下一個(gè)請(qǐng)求了；
這樣就解決了 http1.0 的客戶端的隊(duì)頭阻塞，這也就是HTTP/1.1中管道 (Pipeline)的概念了。
依然存在的問題
但是，HTTP.1 規(guī)定，服務(wù)器端的響應(yīng)（response）要根據(jù)請(qǐng)求被接收的順序排隊(duì)；
也就是說，先接收到的請(qǐng)求，其對(duì)應(yīng)的響應(yīng)也要先發(fā)送。
這樣造成的問題是，如果最先收到的請(qǐng)求的處理時(shí)間長(zhǎng)的話，響應(yīng)生成也慢，就會(huì)阻塞已經(jīng)生成了的響應(yīng)的發(fā)送，這也會(huì)造成隊(duì)頭阻塞。可見，HTTP1.1 的隊(duì)頭阻塞問題依然沒解決，不過是將問題從 客戶端 轉(zhuǎn)嫁到了 服務(wù)器端。
HTTP/2 相比于 HTTP/1.1 的改進(jìn)
為了解決HTTP/1.1中的服務(wù)端隊(duì)首阻塞，HTTP/2采用了二進(jìn)制分幀 和 多路復(fù)用 等方法。
幀是HTTP/2數(shù)據(jù)通信的最小單位。在 HTTP/1.1 中數(shù)據(jù)包是文本格式，而 HTTP/2 的數(shù)據(jù)包是二進(jìn)制格式的，也就是二進(jìn)制幀。
采用幀的傳輸方式可以將請(qǐng)求和響應(yīng)的數(shù)據(jù)分割得更小，且二進(jìn)制協(xié)議可以被高效解析；
HTTP/2中，同域名下的所有通信都在單個(gè)連接上完成，該連接可以承載任意數(shù)量的雙向數(shù)據(jù)流；
每個(gè)數(shù)據(jù)流都以消息的形式發(fā)送，而消息又由一個(gè)或多個(gè)幀組成，多個(gè)幀之間可以亂序發(fā)送，根據(jù)幀首部的流標(biāo)識(shí)在客戶端重新組裝。
多路復(fù)用，替代了原來的隊(duì)列和阻塞機(jī)制：
在HTTP/1.1中，并發(fā)多個(gè)請(qǐng)求需要多個(gè) TCP 鏈接，且單個(gè)域名有 6-8 個(gè) TCP 鏈接請(qǐng)求的限制（瀏覽器端做的限制，不同瀏覽器的數(shù)量也可能不同）；
在HTTP/2中，同一域名下的所有通信在單個(gè)鏈接完成，僅占用一個(gè) TCP 鏈接，且在這一個(gè)鏈接上可以并行請(qǐng)求和響應(yīng)，互不干擾；
非線性結(jié)構(gòu)
非線性結(jié)構(gòu)有：樹、圖；
樹
樹的遍歷方式有【前中后序遍歷】和層次遍歷，很多人對(duì)前中后這三種遍歷方式的印象比較模糊，其實(shí)換個(gè)方式就很好理解，也容易記?。?br>
所謂的【前中后】其實(shí)指的是遍歷時(shí)的根節(jié)點(diǎn)的位置，其他位置按照先左后右的順序排列即可。
前序遍歷：根左右；
中序遍歷：左根右；
后序遍歷：左右根；
樹的重要性質(zhì)
1、如果有n個(gè)頂點(diǎn)，則有 n-1 條邊；
2、任一子節(jié)點(diǎn)到達(dá)根節(jié)點(diǎn)的路徑【唯一】，且路徑長(zhǎng)度為節(jié)點(diǎn)所處的深度；
二叉樹
二叉樹是節(jié)點(diǎn)不超過二的樹，是樹的一種特殊子集，屬于被限制的樹結(jié)構(gòu)，有意思的是，它卻能夠表示和實(shí)現(xiàn)所有的樹；
二叉樹是LC的主要考點(diǎn)之一，以下為和其相關(guān)的題目列表：
- LC-94.binary-tree-inorder-traversal
- LC-102.binary-tree-level-order-traversal
- LC-103.binary-tree-zigzag-level-order-traversal
- LC-144.binary-tree-preorder-traversal
- LC-145.binary-tree-postorder-traversal
- LC-199.binary-tree-right-side-view
真·二叉樹
所有節(jié)點(diǎn)的度數(shù)只能是偶數(shù)，即0或2；
堆
堆，其實(shí)是一種優(yōu)先級(jí)隊(duì)列，一種典型的實(shí)現(xiàn)就是二叉堆，也是最?？嫉念愋汀?/p>
二叉堆的特點(diǎn)
1、最小堆（min heap）：如果P是C的一個(gè)父節(jié)點(diǎn)，那么P的key或value應(yīng)小于等于C對(duì)應(yīng)的值；基于這個(gè)性質(zhì)，可以得出結(jié)論，堆頂元素一定是最小的；
一般我們可以利用此特性，求最小值或第k小值。
2、最大堆（max heap）：和最小堆相反，P的key或value應(yīng)大于等于C對(duì)應(yīng)的值。
二叉堆相關(guān)考題：
- LC-295.find-median-from-data-stream
注：優(yōu)先隊(duì)列不只是【堆】這一種，還要更為復(fù)雜的，但原理類似。
二叉查找樹
二叉查找樹（Binary Search Tree），又叫做 Binary Sort Tree（二叉排序樹），俗稱，二叉搜索樹。
二叉查找樹性質(zhì)如下：
- 若
左子樹不為空，則左子樹下的所有節(jié)點(diǎn)的值，均小于其根節(jié)點(diǎn)的值； - 若
右子樹不為空，則右子樹下的所有節(jié)點(diǎn)的值，均大于其根節(jié)點(diǎn)的值； - 左右子樹也均為二叉查找樹；
- 沒有鍵值相等的節(jié)點(diǎn)；
對(duì)于一個(gè)二叉查找樹，常規(guī)操作有查找、插入、刪除、尋找父節(jié)點(diǎn)、求最大最小值等。
之所以將其命名為查找樹，是因?yàn)槠浞浅＿m合查找。
舉個(gè)栗子，如下一棵二叉查找樹，愈查找節(jié)點(diǎn)值小于且最接近 58 的節(jié)點(diǎn)，搜索的流程如圖：
[圖片上傳失敗...(image-1c4a10-1653623219302)]
二叉查找樹還有一個(gè)特性是： 中序遍歷的結(jié)果，是一個(gè)有序數(shù)組，有時(shí)候我們可以利用到這個(gè)性質(zhì)。
LC-相關(guān)題目：
- 98.validate-binary-search-tree
二叉平衡樹
平衡樹是計(jì)算機(jī)科學(xué)中的一類數(shù)據(jù)結(jié)構(gòu)，是一種改進(jìn)后的二叉查找樹，一般來講，二叉查找樹的查詢復(fù)雜度取決于目標(biāo)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離，即樹的深度，因此當(dāng)節(jié)點(diǎn)的深度普遍較大時(shí)，查詢的時(shí)間復(fù)雜度也會(huì)隨之提升。
為了實(shí)現(xiàn)更高效的查詢，就誕生了平衡樹。
這里所說的平衡，指的是所有葉子的深度趨于平衡，廣義上指的是在樹上所有可能的查找的均攤復(fù)雜度更低。
一些數(shù)據(jù)庫的引擎使用的就是這種數(shù)據(jù)結(jié)構(gòu)，其目標(biāo)是為了將查詢的時(shí)間復(fù)雜度降到 logn，可以簡(jiǎn)單理解為，樹在數(shù)據(jù)結(jié)果層面實(shí)現(xiàn)了二分查找算法。
二叉平衡樹的基本操作
- 旋轉(zhuǎn)
- 插入
- 刪除
- 查詢前驅(qū)
- 查詢后繼
AVL 樹（大致了解就好）
AVL樹，得名于它的兩個(gè)發(fā)明者的名字首字母，是最早被發(fā)明的自平衡二叉查找樹，其任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。
AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點(diǎn)是：
1.其本身首先是一棵二叉搜索樹。
2.帶有平衡條件：每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值（平衡因子）最多為1（1, 0, -1），所以帶有平衡因子 -2 或 2 的節(jié)點(diǎn)就會(huì)被認(rèn)為是不平衡的，需要重新平衡這棵樹。
也就是說，AVL樹，本質(zhì)上是自帶了平衡功能的二叉查找樹。
紅黑樹
又被稱為"對(duì)稱二叉 B 樹"，紅黑樹的結(jié)構(gòu)復(fù)雜，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中很高效：它可以在 O(logn) 時(shí)間內(nèi)完成查找，插入和刪除（n 是樹中元素的數(shù)目）。
字典樹（前綴樹）
又稱 Trie（[tra?]） 樹，典型應(yīng)用是統(tǒng)計(jì)場(chǎng)景，排序和保存大量的字符串（但并不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。
它的優(yōu)點(diǎn)是：利用字符串的公共前綴來減少查詢時(shí)間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹要高。
特性：
- 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的所有子節(jié)點(diǎn)都只包含一個(gè)字符；
- 將從根節(jié)點(diǎn)到某一子節(jié)點(diǎn)的路徑上的字符串聯(lián)起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；
- 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
LC-相關(guān)算法：
- LC-208.implement-trie-prefix-tree
- LC-211.add-and-search-word-data-structure-design
- LC-212.word-search-ii
