面試準備-資料結構（持續更新）

1、二叉查找樹

若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

任意節點的左、右子樹也分别為二叉查找樹。

沒有鍵值相等的節點（no duplicate nodes）。

2、二叉平衡樹，AVL樹：

首先是二叉查找樹，并且左右兩個子樹都是一棵平衡二叉樹，左右子樹高度差不超過1

3、紅黑樹：

首先是二叉查找樹，

每個結點要麼是紅的要麼是黑的。

根結點是黑的。

每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。

如果一個結點是紅的，那麼它的兩個兒子都是黑的。

且每個節點到葉子節點路過的黑色節點個數一緻

4、B樹

平衡多叉樹，一顆最小度為t的B樹，

每個節點最多包含2t−1個關鍵字；除根節點外的每個節點至少有t−1個關鍵字，根節點至少有一個關鍵字

節點中的關鍵字非降序排列

設節點有n個關鍵字，則該節點有n+1個子樹

所有葉子節點在同一高度

5、B+樹

一顆階數為m的B+樹

除根節點外的内部節點，每個節點最多有m個關鍵字，最少有⌈m/2⌉個關鍵字。其中每個關鍵字對應一個子樹（也就是最多有m棵子樹，最少有⌈m/2⌉棵子樹）；

根節點要麼沒有子樹，要麼至少有2棵子樹；

所有的葉子節點包含了全部的關鍵字以及這些關鍵字指向檔案的指針，并且：

所有葉子節點中的關鍵字按大小順序排列

相鄰的葉子節點順序連結（相當于是構成了一個順序連結清單）

所有葉子節點在同一層

所有分支節點的關鍵字都是對應子樹中關鍵字的最大值

6、跳躍表

• 一個跳躍表應該有若幹個層（Level）連結清單組成；
• 跳躍表中最底層的連結清單包含所有資料； 每一層連結清單中的資料都是有序的；
• 如果一個元素X出現在第i層，那麼編号比 i 小的層都包含元素X；
• 第 i 層的元素通過一個指針指向下一層擁有相同值的元素；
• 在每一層中，-∞ 和 +∞兩個元素都出現(分别表示INT_MIN 和 INT_MAX)；
• 頭指針（head）指向最高一層的第一個元素；

示意圖可參考：https://blog.csdn.net/DERRANTCM/article/details/79063312

代碼實作可參考：https://www.jianshu.com/p/60d2561b821c