前言
仿佛一下子，2017年就快過去一半了，研一馬上就要成為過去式了，我打算抓住研一的尾巴，好好梳理一下資料結構與算法，畢竟這些基礎知識是很重要的嘛。是以準備在這裡搞一個系列的文章，以期透徹。
本系列将采用Java語言來進行描述。亦即總結常見的的資料結構，以及在Java中相應的實作方法，務求理論與實踐一步總結到位。
首先給出Java集合架構的基本接口/類層次結構：
java.util.Collection [I]
+--java.util.List [I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C] //線程安全
+--java.util.Stack [C] //線程安全
+--java.util.Set [I]
+--java.util.HashSet [C]
+--java.util.SortedSet [I]
+--java.util.TreeSet [C]
+--Java.util.Queue[I]
+--java.util.Deque[I]
+--java.util.PriorityQueue[C]
java.util.Map [I]
+--java.util.SortedMap [I]
+--java.util.TreeMap [C]
+--java.util.Hashtable [C] //線程安全
+--java.util.HashMap [C]
+--java.util.LinkedHashMap [C]
+--java.util.WeakHashMap [C]
[I]：接口
[C]：類
本圖來源于網絡。
數組
數組是相同資料類型的元素按一定順序排列的集合，是一塊連續的記憶體空間。數組的優點是：get和set操作時間上都是O(1)的；缺點是：add和remove操作時間上都是O(N)的。
Java中，Array就是數組，此外，ArrayList使用了數組Array作為其實作基礎,它和一般的Array相比，最大的好處是，我們在添加元素時不必考慮越界，元素超出數組容量時，它會自動擴張保證容量。
Vector和ArrayList相比，主要差别就在于多了一個線程安全性，但是效率比較低下。如今java.util.concurrent包提供了許多線程安全的集合類（比如 LinkedBlockingQueue），是以不必再使用Vector了。
int[] ints = new int[10];
ints[0] = 5;//set
int a = ints[2];//get
int len = ints.length;//數組長度
連結清單
連結清單是一種非連續、非順序的結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的，連結清單由一系列結點組成。連結清單的優點是：add和remove操作時間上都是O(1)的；缺點是：get和set操作時間上都是O(N)的，而且需要額外的空間存儲指向其他資料位址的項。
查找操作對于未排序的數組和連結清單時間上都是O(N)。
Java中，LinkedList 使用連結清單作為其基礎實作。
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("addd");//add
linkedList.set(0,"s");//set，必須先保證 linkedList中已經有第0個元素
String s = linkedList.get(0);//get
linkedList.contains("s");//查找
linkedList.remove("s");//删除
//以上方法也适用于ArrayList
隊列
隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端進行删除操作，而在表的後端進行插入操作，亦即所謂的先進先出（FIFO）。
Java中，LinkedList實作了Deque，可以做為雙向隊列（自然也可以用作單向隊列）。另外PriorityQueue實作了帶優先級的隊列，亦即隊列的每一個元素都有優先級，且元素按照優先級排序。
Deque<Integer> integerDeque = new LinkedList<>();
// 尾部入隊，差別在于如果失敗了
// add方法會抛出一個IllegalStateException異常，而offer方法傳回false
integerDeque.offer(122);
integerDeque.add(122);
// 頭部出隊,差別在于如果失敗了
// remove方法抛出一個NoSuchElementException異常，而poll方法傳回false
int head = integerDeque.poll();//傳回第一個元素，并在隊列中删除
head = integerDeque.remove();//傳回第一個元素，并在隊列中删除
// 頭部出隊，差別在于如果失敗了
// element方法抛出一個NoSuchElementException異常，而peek方法傳回null。
head = integerDeque.peek();//傳回第一個元素，不删除
head = integerDeque.element();//傳回第一個元素，不删除
棧
棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和删除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。它展現了後進先出（LIFO）
的特點。
Java中，Stack實作了這種特性，但是Stack也繼承了Vector，是以具有線程安全線和效率低下兩個特性，最新的JDK8中，推薦用Deque來實作棧，比如：
Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(12);//尾部入棧
stack.push(16);//尾部入棧
int tail = stack.pop();//尾部出棧，并删除該元素
tail = stack.peek();//尾部出棧，不删除該元素
集合
集合是指具有某種特定性質的具體的或抽象的對象彙總成的集體，這些對象稱為該集合的元素，其主要特性是元素不可重複。
在Java中，HashSet 展現了這種資料結構，而HashSet是在MashMap的基礎上建構的。LinkedHashSet繼承了HashSet，使用HashCode确定在集合中的位置，使用連結清單的方式确定位置，是以有順序。TreeSet實作了SortedSet 接口，是排好序的集合（在TreeMap 基礎之上建構），是以查找操作比普通的Hashset要快（log(N)）；插入操作要慢（log（N））,因為要維護有序。
HashSet<Integer> integerHashSet = new HashSet<>();
integerHashSet.add(12121);//添加
integerHashSet.contains(121);//是否包含
integerHashSet.size();//集合大小
integerHashSet.isEmpty();//是否為空
散清單
散清單也叫哈希表，是根據關鍵鍵值(Keyvalue)進行通路的資料結構，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度，這個映射函數叫做散列函數。
Java中HashMap實作了散清單，而Hashtable比它多了一個線程安全性，但是由于使用了全局鎖導緻其性能較低，是以現在一般用ConcurrentHashMap來實作線程安全的HashMap（類似的，以上的資料結構在最新的java.util.concurrent的包中幾乎都有對應的高性能的線程安全的類）。TreeMap實作SortMap接口，能夠把它儲存的記錄按照鍵排序。LinkedHashMap保留了元素插入的順序。WeakHashMap是一種改進的HashMap，它對key實行“弱引用”，如果一個key不再被外部所引用，那麼該key可以被GC回收，而不需要我們手動删除。
HashMap<Integer,String> hashMap = new HashMap<>();
hashMap.put(1,"asdsa");//添加
hashMap.get(1);//獲得
hashMap.size();//元素個數
樹
樹（tree）是包含n（n>0）個節點的有窮集合，其中：
- 每個元素稱為節點（node）；
- 有一個特定的節點被稱為根節點或樹根（root）。
- 除根節點之外的其餘資料元素被分為m（m≥0）個互不相交的結合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹這種資料結構在計算機世界中有廣泛的應用，比如作業系統中用到了紅黑樹，資料庫用到了B+樹，編譯器中的文法樹，記憶體管理用到了堆（本質上也是樹），資訊論中的哈夫曼編碼等等等等，在Java中TreeSet和TreeMap用到了樹來排序（二分查找提高檢索速度），不過一般都需要程式員自己去定義一個樹的類，并實作相關性質，而沒有現成的API。下面就用Java來實作各種常見的樹。
二叉樹
二叉樹是一種基礎而且重要的資料結構，其每個結點至多隻有二棵子樹，二叉樹有左右子樹之分，第i層至多有2^(i-1)個結點（i從1開始）；深度為k的二叉樹至多有2^(k)-1)個結點，對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。
二叉樹的性質：
1) 在非空二叉樹中，第i層的結點總數不超過2^(i-1), i>=1;
2) 深度為h的二叉樹最多有2^h-1個結點(h>=1)，最少有h個結點;
3) 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1;
4) 具有n個結點的完全二叉樹的深度為log2(n+1);
5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：
若I為結點編号則 如果I>1，則其父結點的編号為I/2；
如果2I<=N，則其左兒子（即左子樹的根結點）的編号為2I；若2I>N，則無左兒子；
如果2I+1<=N，則其右兒子的結點編号為2I+1；若2I+1>N，則無右兒子。
6)給定N個節點，能構成h(N)種不同的二叉樹，其中h(N)為卡特蘭數的第N項，h(n)=C(2*n, n)/(n+1)。
7)設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i。
滿二叉樹、完全二叉樹
滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點；
完全二叉樹：若設二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結點數都達到最大個數，第h層所有的結點都連續集中在最左邊，這就是完全二叉樹；
滿二叉樹是完全二叉樹的一個特例。
二叉查找樹
二叉查找樹，又稱為是二叉排序樹（Binary Sort Tree）或二叉搜尋樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
1) 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2) 若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
3) 左、右子樹也分别為二叉排序樹；
4) 沒有鍵值相等的節點。
二叉查找樹的性質：對二叉查找樹進行中序周遊，即可得到有序的數列。
二叉查找樹的時間複雜度：它和二分查找一樣，插入和查找的時間複雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間複雜度。原因在于插入和删除元素的時候，樹沒有保持平衡。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是平衡二叉樹設計的初衷。
二叉查找樹可以這樣表示：
public class BST<Key extends Comparable<Key>, Value> {
private Node root; // 根節點
<span class="hljs-keyword">private</span> class Node {
<span class="hljs-keyword">private</span> Key <span class="hljs-built_in">key</span>; <span class="hljs-comment">// 排序的間</span>
<span class="hljs-keyword">private</span> Value val; <span class="hljs-comment">// 相應的值</span>
<span class="hljs-keyword">private</span> Node left, right; <span class="hljs-comment">// 左子樹，右子樹</span>
<span class="hljs-keyword">private</span> <span class="hljs-built_in">int</span> <span class="hljs-built_in">size</span>; <span class="hljs-comment">// 以該節點為根的樹包含節點數量</span>
<span class="hljs-keyword">public</span> Node(Key <span class="hljs-built_in">key</span>, Value val, <span class="hljs-built_in">int</span> <span class="hljs-built_in">size</span>) {
<span class="hljs-keyword">this</span>.<span class="hljs-built_in">key</span> = <span class="hljs-built_in">key</span>;
<span class="hljs-keyword">this</span>.val = val;
<span class="hljs-keyword">this</span>.<span class="hljs-built_in">size</span> = <span class="hljs-built_in">size</span>;
}
}
<span class="hljs-keyword">public</span> BST() {}
<span class="hljs-keyword">public</span> <span class="hljs-built_in">int</span> <span class="hljs-built_in">size</span>() {<span class="hljs-comment">//獲得該二叉樹節點數量</span>
<span class="hljs-keyword">return</span> <span class="hljs-built_in">size</span>(root);
}
<span class="hljs-keyword">private</span> <span class="hljs-built_in">int</span> <span class="hljs-built_in">size</span>(Node x) {獲得以該節點為根的樹包含節點數量
<span class="hljs-keyword">if</span> (x == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
<span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> x.<span class="hljs-built_in">size</span>;
}
}
查找：
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {//在以x節點為根的樹中查找key
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);//遞歸左子樹查找
else if (cmp > 0) return get(x.right, key);//遞歸右子樹查找
else return x.val;//找到了
}
插入：
public void put(Key key, Value val) {
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {在以x節點為根的樹中查找key，val
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);//遞歸左子樹插入
else if (cmp > 0) x.right = put(x.right, key, val);//遞歸右子樹插入
else x.val = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
删除：
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) return x;
else return min(x.left);
}
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {//删除以x為根節點的子樹最小值
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key) {
root = delete(root, key);
}
private Node delete(Node x, Key key) {
if (x == null) return null;
<span class="hljs-built_in">int</span> cmp = <span class="hljs-built_in">key</span>.compareTo(x.<span class="hljs-built_in">key</span>);
<span class="hljs-keyword">if</span> (cmp < <span class="hljs-number">0</span>) x.left = delete(x.left, <span class="hljs-built_in">key</span>);<span class="hljs-comment">//遞歸删除左子樹</span>
<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cmp > <span class="hljs-number">0</span>) x.right = delete(x.right, <span class="hljs-built_in">key</span>);<span class="hljs-comment">//遞歸删除右子樹</span>
<span class="hljs-keyword">else</span> { <span class="hljs-comment">//該節點就是所要删除的節點</span>
<span class="hljs-keyword">if</span> (x.right == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> x.left;<span class="hljs-comment">//沒有右子樹，把左子樹挂在原節點父節點上</span>
<span class="hljs-keyword">if</span> (x.left == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> x.right;<span class="hljs-comment">//沒有左子樹，，把右子樹挂在原節點父節點上</span>
Node t = x;<span class="hljs-comment">//用右子樹中最小的節點來替代被删除的節點，仍然保證樹的有序性</span>
x = <span class="hljs-built_in">min</span>(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.<span class="hljs-built_in">size</span> = <span class="hljs-built_in">size</span>(x.left) + <span class="hljs-built_in">size</span>(x.right) + <span class="hljs-number">1</span>;
<span class="hljs-keyword">return</span> x;
}
平衡二叉樹
平衡二叉樹又被稱為AVL樹，具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。它的出現就是解決二叉查找樹不平衡導緻查找效率退化為線性的問題，因為在删除和插入之時會維護樹的平衡，使得查找時間保持在O(logn)，比二叉查找樹更穩定。
ALLTree 的 Node 由 BST 的 Node 加上
private int height;
節點高度屬性即可，這是為了便于判斷樹是否平衡。
維護樹的平衡關鍵就在于旋轉。對于一個平衡的節點，由于任意節點最多有兩個兒子，是以高度不平衡時，此節點的兩顆子樹的高度差2.容易看出，這種不平衡出現在下面四種情況：
1、6節點的左子樹3節點高度比右子樹7節點大2，左子樹3節點的左子樹1節點高度大于右子樹4節點，這種情況成為左左。
2、6節點的左子樹2節點高度比右子樹7節點大2，左子樹2節點的左子樹1節點高度小于右子樹4節點，這種情況成為左右。
3、2節點的左子樹1節點高度比右子樹5節點小2，右子樹5節點的左子樹3節點高度大于右子樹6節點，這種情況成為右左。
4、2節點的左子樹1節點高度比右子樹4節點小2，右子樹4節點的左子樹3節點高度小于右子樹6節點，這種情況成為右右。
從圖2中可以可以看出，1和4兩種情況是對稱的，這兩種情況的旋轉算法是一緻的，隻需要經過一次旋轉就可以達到目标，我們稱之為單旋轉。2和3兩種情況也是對稱的，這兩種情況的旋轉算法也是一緻的，需要進行兩次旋轉，我們稱之為雙旋轉。
單旋轉是針對于左左和右右這兩種情況，這兩種情況是對稱的，隻要解決了左左這種情況，右右就很好辦了。圖3是左左情況的解決方案，節點k2不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的左子樹X子樹，是以屬于左左情況。
為使樹恢複平衡，我們把k1變成這棵樹的根節點，因為k2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質，又滿足了平衡二叉樹的性質。
這樣的操作隻需要一部分指針改變，結果我們得到另外一顆二叉查找樹，它是一棵AVL樹，因為X向上一移動了一層，Y還停留在原來的層面上，Z向下移動了一層。整棵樹的新高度和之前沒有在左子樹上插入的高度相同，插入操作使得X高度長高了。是以，由于這顆子樹高度沒有變化，是以通往根節點的路徑就不需要繼續旋轉了。
代碼：
private int height(Node t){
return t == null ? -1 : t.height;
}
//左左情況單旋轉
private Node rotateWithLeftChild(Node k2){
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k1.size = k2.size;
k2.size = size(k2.right)+size(k2.left)+1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
return k1; //傳回新的根
}
//右右情況單旋轉
private Node rotateWithRightChild(Node k2){
Node k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k1.size = k2.size;
k2.size = size(k2.right)+size(k2.left)+1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.right), k2.height) + 1;
return k1; //傳回新的根
}
雙旋轉是針對于左右和右左這兩種情況，單旋轉不能使它達到一個平衡狀态，要經過兩次旋轉。同樣的，這樣兩種情況也是對稱的，隻要解決了左右這種情況，右左就很好辦了。圖4是左右情況的解決方案，節點k3不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的右子樹k2子樹，是以屬于左右情況。
為使樹恢複平衡，我們需要進行兩步，第一步，把k1作為根，進行一次右右旋轉，旋轉之後就變成了左左情況，是以第二步再進行一次左左旋轉，最後得到了一棵以k2為根的平衡二叉樹樹。
//左右情況
private Node doubleWithLeftChild(Node k3){
try{
k3.left = rotateWithRightChild(k3.left);
}catch(NullPointerException e){
System.out.println("k.left.right為："+k3.left.right);
throw e;
}
return rotateWithLeftChild(k3);
}
//右左情況
private Node doubleWithRightChild(Node k3){
try{
k3.right = rotateWithLeftChild(k3.right);
}catch(NullPointerException e){
System.out.println("k.right.left為："+k3.right.left);
throw e;
}
return rotateWithRightChild(k3);
}
AVL查找操作與BST相同，AVL的删除與插入操作在BST基礎之上需要檢查是否平衡，如果不平衡就要使用旋轉操作來維持平衡:
private Node balance(Node x) {
if (balanceFactor(x) < -1) {//右邊高
if (balanceFactor(x.right) > 0) {//右左
x.right = rotateWithLeftChild(x.right);
}
x = rotateWithRightChild(x);
}
else if (balanceFactor(x) > 1) {//左邊高
if (balanceFactor(x.left) < 0) {//左右
x.left = rotateWithRightChild(x.left);
}
x = rotateWithLeftChild(x);
}
return x;
}
private int balanceFactor(Node x) {
return height(x.left) - height(x.right);
}
堆
堆是一顆完全二叉樹，在這棵樹中，所有父節點都滿足大于等于其子節點的堆叫大根堆，所有父節點都滿足小于等于其子節點的堆叫小根堆。堆雖然是一顆樹，但是通常存放在一個數組中，父節點和孩子節點的父子關系通過數組下标來确定。如下圖的小根堆及存儲它的數組：
值： 7,8,9,12,13,11
數組索引： 0,1,2,3, 4, 5
通過一個節點在數組中的索引怎麼計算出它的父節點及左右孩子節點的索引：
public int left(int i) {
return (i + 1) * 2 - 1;
}
public int right(int i) {
return (i + 1) * 2;
}
public int parent(int i) {
// i為根結點
if (i == 0) {
return -1;
}
return (i - 1) / 2;
}
維護大根堆的性質：
public void heapify(T[] a, int i, int heapLength) {
int l = left(i);
int r = right(i);
int largest = -1;
//尋找根節點及其左右子節點，三個元素中的最大值
if (l < heapLength && a[i].compareTo(a[l]) < 0) {
largest = l;
} else {
largest = i;
}
if (r < heapLength && a[largest].compareTo(a[r]) < 0) {
largest = r;
}
<span class="hljs-comment">// 如果i處元素不是最大的，就把i處的元素與最大處元素交換，使得i處元素變為最大的</span>
<span class="hljs-keyword">if</span> (i != largest) {
T temp = a[i];
a[i] = a[largest];
a[largest] = temp;
<span class="hljs-comment">// 交換元素後，以a[i]為根的樹可能不在滿足大根堆性質，于是遞歸調用該方法</span>
heapify(a, largest, heapLength);
}
}
構造堆：
public void buildHeap(T[] a, int heapLength) {
//從後往前看lengthParent處的元素是第一個有子節點的元素，是以從它開始，進行堆得維護
int lengthParent = parent(heapLength - 1);
for(int i = lengthParent; i >= 0; i--){
heapify(a, i, heapLength);
}
}
堆的用途：堆排序，優先級隊列。此外由于調整代價較小，也适合實時類型的排序與變更。
後記
寫着寫着就發現要想總結到位是一項非常龐大的工程，路漫漫其修遠兮。吾将上下而求索啊。
歡迎通路我的首頁 mageek
參考與感謝：
- JDK1.8源碼
- 資料結構與算法——Java語言實作
- 代碼主要來自-算法第四版
- http://www.cnblogs.com/maybe2...
- http://blog.csdn.net/hero_mys...
- http://www.cppblog.com/cxiaoj...
- http://blog.csdn.net/liyong19...
- http://blog.csdn.net/l2942654...
</div>
原文位址：https://segmentfault.com/a/1190000009797159