校招準備系列7-資料結構

線性表定義：

　　1、0個或多個元素的集合

　　2、元素之間是有序的

　　3、元素個數有限

　　4、元素資料的類型必須相同

順序表：線性表的順序存儲結構

連結清單：線性表的鍊式存儲

連結清單

連結清單是一種由節點（Node）組成的線性資料集合，每個節點通過指針指向下一個節點。它是一種由節點組成，并能用于表示序列的資料結構。

• 單連結清單：每個節點僅有一個指針指向下一個節點，最後一個節點指向空（null）。
• 雙連結清單：每個節點有兩個指針p，n。p指向前一個節點，n指向下一個節點；最後一個節點指向空。
• 循環連結清單：每個節點指向下一個節點，最後一個節點指向第一個節點。

• 時間複雜度：

  索引：O(n)

  查找：O(n)

  插入：O(1)

  删除：O(1)

棧

棧是一個元素集合，支援兩個基本操作：push用于将元素壓入棧，pop用于删除棧頂元素。

後進先出的資料結構（Last In First Out, LIFO）

• 時間複雜度

  索引：O(n)

  查找：O(n)

  插入：O(1)

  删除：O(1)

隊列

隊列是一個元素集合，支援兩種基本操作：enqueue 用于添加一個元素到隊列頭，dequeue 用于删除隊列尾的一個元素。

先進先出的資料結構（First In First Out, FIFO）。

• 時間複雜度

  索引：O(n)

  查找：O(n)

  插入：O(1)

  删除：O(1)

二叉樹

二叉樹是一個樹形資料結構，每個節點最多可以有兩個子節點，稱為左子節點和右子節點。

• 滿二叉樹（Full Binary Tree）：每一個層的結點數都達到最大值（國内定義）；二叉樹中的每個節點有 0 或者 2 個子節點（國外定義）。
• 完全二叉樹：二叉樹中除最後一層外其他各層的節點數均達到最大值，最後一層的節點都連續集中在最左邊。
• 完美二叉樹（Perfect Binary Tree）：二叉樹中的每個節點有兩個子節點，并且所有的葉子節點的深度是一樣的。

• 二叉樹的周遊：

  – 先序周遊：根左右。非遞歸方法：用一個輔助棧

  – 中序周遊：左根右

  – 後序周遊：左右根

  已知先序周遊序列和中序周遊序列，求出後序序列 或者 已知中序序列和後序序列，求出先序周遊。但是不能由先序周遊序列+後序周遊序列求出中序周遊序列。

二叉樹的度數和節點數的關系

• 總度數（從上往下找邊的總數）= 節點數-1（從下往上找邊的總數）

  2*n2+n1 = n2 + n1 + n0 - 1

二叉查找樹

二叉查找樹（BST）是一種二叉樹。其任何節點的值都大于等于左子樹中的值，小于等于右子樹中的值。

• 時間複雜度

  索引：O(log(n))

  查找：O(log(n))

  插入：O(log(n))

  删除：O(log(n))

字典樹trie

字典樹，又稱為基數樹或字首樹，是一種用于存儲鍵值為字元串的動态集合或關聯數組的查找樹。樹中的節點并不直接存儲關聯鍵值，而是該節點在樹中的位置決定了其關聯鍵值。一個節點的所有子節點都有相同的字首，根節點則是空字元串。

樹狀數組

樹狀數組，又稱為二進制索引樹（Binary Indexed Tree，BIT），其概念上是樹，但以數組實作。數組中的下标代表樹中的節點，每個節點的父節點或子節點的下标可以通過位運算獲得。數組中的每個元素都包含了預計算的區間值之和，在整個樹更新的過程中，這些計算的值也同樣會被更新。

• 時間複雜度

  區間求和：O(log(n))

  更新：O(log(n))

堆

堆是一種基于樹的滿足某些特性的資料結構：整個堆中的所有父子節點的鍵值都滿足相同的排序條件。堆分為最大堆和最小堆。在最大堆中，父節點的鍵值永遠大于等于所有子節點的鍵值，根節點的鍵值是最大的。最小堆中，父節點的鍵值永遠小于等于所有子節點的鍵值，根節點的鍵值是最小的。

• 時間複雜度

  索引：O(log(n))

  查找：O(log(n))

  插入：O(log(n))：新節點在最右下的位置，作為葉子節點，上浮到合适位置

  删除：O(log(n))：删除堆頂元素。用最後一個節點替換根節點，從根節點自上而下進行堆調整。

  删除最大值/最小值：O(1)

哈希

哈希用于将任意長度的資料映射到固定長度的資料。哈希函數的傳回值被稱為哈希值、哈希碼或者哈希。如果不同的主鍵得到相同的哈希值，則發生了沖突。

Hash Map：hash map 是一個存儲鍵值間關系的資料結構。HashMap 通過哈希函數将鍵轉化為桶或者槽中的下标，進而便于指定值的查找。

• 沖突解決

  鍊位址法（Separate Chaining）：在鍊位址法中，每個桶（bucket）是互相獨立的，每一個索引對應一個元素清單。處理HashMap 的時間就是查找桶的時間（常量）與周遊清單元素的時間之和。

  開放位址法（Open Addressing）：在開放位址方法中，當插入新值時，會判斷該值對應的哈希桶是否存在，如果存在則根據某種算法依次選擇下一個可能的位置，直到找到一個未被占用的位址。開放位址即某個元素的位置并不永遠由其哈希值決定。線性探測，二次探測，随機探測等。

并查集

http://dongxicheng.org/structure/union-find-set/

AVL樹與紅黑樹

紅黑樹

https://blog.csdn.net/ivan_zgj/article/details/51504764

紅黑樹樹是一種二叉搜尋樹。性質：

性質1. 節點是紅色或黑色。

性質2. 根節點是黑色。

性質3 每個葉節點（NIL節點，空節點）是黑色的。

性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

插入的節點是紅色，至多2次旋轉。删除至多3次旋轉。

AVL樹

AVL樹是一種二叉搜尋樹，每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1，是嚴格平衡的。查找、插入、删除操作的複雜度都是O(logn)

紅黑樹也是一種二叉搜尋樹，從根到葉子的最長的可能路徑不多于（<=）最短的可能路徑的兩倍長，是以它隻是大緻平衡的。查找、插入、删除操作的複雜度都是O(logn)

是以紅黑樹的統計性能要優于AVL樹。

http://www.cnblogs.com/skywang12345/p/3245399.html

B樹和B+樹

https://www.cnblogs.com/vincently/p/4526560.html

https://www.sohu.com/a/156886901_479559

B樹（B-tree）是一種樹狀資料結構，它能夠存儲資料、對其進行排序并允許以O(log n)的時間複雜度運作進行查找、順序讀取、插入和删除的資料結構。B樹，概括來說是一個節點可以擁有多于2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B-樹為系統最優化大塊資料的讀和寫操作。B-tree算法減少定位記錄時所經曆的中間過程，進而加快存取速度。普遍運用在資料庫和檔案系統。”

B+樹的非葉子結點隻包含導航資訊，不包含實際的值，所有的葉子結點和相連的節點使用連結清單相連，便于區間/範圍查找和周遊。