1.數組 線性表

定義的方式

int[] a=new int[10]

為什么查詢快？

????????1.可以借助O(1)時間復雜度訪問某一元素，

????????2.地址連續，邏輯連續

????????3.數組長度一旦確定就不可以被修改

當需要擴容的時候需要將老數組的內容復制過來

在Java中數組是一個對象

ArrayList 數組列表

ArrayList的添加（自動擴容）

????????對應的源碼

????????值得一看的是ensureCapacityInternal方法

????????Ctrl+鼠標右鍵點進去

????????看這個231行的這個方法，modCount這個不用關注，是并發下的一個計數，重點看234行的代碼，minCapacity是新加入的值的位置，如果比數組的長度大就會執行grow()，數組擴容的方法

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//取到老的容量int newCapacity = oldCapacity + (oldCapacity >> 1);//構建新的容量，新的容量是老的容量的+老的容量右移一位（1.5倍）if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);//把老數組的值賦值給新的數組
}

底層就是構建了一個新的數組，并且把老的數組內容復制過來，從而就實現了自動擴容。

總結：初始容量是多少 10

擴容機制： 當elementData已經滿了，才會擴容

擴容的方式：原容量加原容量右移一位

優點：隨機訪問，

缺點：需要連續的空間

2.鏈表

1.可以不斷的擴容

2.由node結點組成，每個node由data和next組成

3.兩種插入方式，頭插法和尾插法

鏈表的構建，以及兩種插入方法（頭插法和尾插法）

class MySingleLinkedList{public Node head;class Node{public int value;public Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}//頭插法public void addFirst(int value){Node node =new Node(value, null);if (head==null){head=node;}else {node.next=head;head=node;}}//尾插法public void addEnd(int value){Node node=new Node(value,null);Node temp=head;if (head==null){head=node;}else {while (temp.next!=null){temp=temp.next;}temp.next=node;}}//循環輸出public void loop(){Node temp=head;while (temp!=null){System.out.println(temp.value);temp=temp.next;}}
}

? ? ? ? ?Java中提供的LinkedList是一個雙端的隊列

? ? ? ? 練習：

? ? ? ? leetcode中

???????????????單鏈表的反轉

????????????????鏈表成環的判斷、環的長度????????

????????????????兩個有序鏈表的合并

3.二叉樹

二叉樹的三種遍歷代碼實現

前序遍歷

中序遍歷

后序遍歷

?3.1 搜索二叉樹

左邊的節點比根小，右邊的節點比根大（不保證平衡）

時間復雜度最好O(log(n)),最壞O(n)

3.2 平衡二叉樹：

搜索二叉樹基礎上，任一節點的左右子樹高度差不超過1.

LL旋轉，RR旋轉，LR旋轉，RL旋轉

3.3 紅黑樹：

紅黑樹是一棵近似平衡的二叉樹，是一種高效的查找樹。

所有的結點要么紅色要么黑色，非黑即紅

根結點是黑色的，葉節點是不存儲數據的黑色 空結點

不能連續兩棵紅色相連

從任意結點到其所有的葉子結點所經過的黑色葉子結點數是一樣的

推導出來，從紅黑樹的葉子結點到另一最近結點上的與到另一最遠結點上，不超過一倍（任一結點的左右子樹的高度差不超過兩倍）

AVL樹(平衡樹)和紅黑樹的對比

AVL嚴格的平衡樹，紅黑樹近似的平衡樹

AVL在查詢上更高效，紅黑樹在插入和刪除上更高效

紅黑樹插入的時候默認結點是紅色的，因為只是有可能會違反根葉黑或者不紅紅的規則

如果插入破壞了規則分以下三種情況：

1）插入結點是根節點

直接把根結點變黑

2）插入結點的叔叔是紅色結點

父親層和爺爺層同時變色，黑色變紅色，紅色變黑色，再看是否破壞紅黑樹的規則。

3）插入結點的叔叔是黑色

(LL,RR,LR,RL)旋轉，然后變色，變色規則是旋轉中心點，旋轉點進行變色

LL：右旋，向右旋轉，沖突的右孩變左孩

RR：左旋，向左旋轉，沖突的左孩子變右孩子

LR： 左旋左孩子，然后右旋

RL：右旋右孩子，然后左旋

4.B樹

紅黑樹雖然是近似平衡的，而且插入，刪除上很高效，但是如果插入數據非常的多，也會出現樹的深度過深，導致內存和磁盤間的I/O次數過多的情況，這時候就可以使用多叉樹。

對于一個m叉樹

(1)樹中每個結點至多有m個孩子結點（m-1個關鍵字）

(2)每個結點的結構

(3)除根結點外，其他結點至少有m/2個孩子結點

(4)若根節點不是葉子結點，則根結點至少有兩個孩子結點

(5)所有的葉子結點都在同一層上，即B樹是所有結點的平衡因子等于0的多路查找樹

B樹的查找

首先我們要了解一個概念，我們讀取磁盤中的數據時，是按照塊或者頁讀取的，比如，一個word文檔大小3.5K，它存儲的時候會按照一個頁的大小的整數倍去存儲，存儲占用4K，讀取的時候也是一樣的。

B樹的訪問結點是在硬盤上解決的，但是B樹對結點內的數據的操作是在內存中使用的。

B樹就是一次性去磁盤中讀取一個塊，數據，指針都在這個塊里了

B+樹

B+樹就是在B樹的基礎上非葉子結點只存儲記錄和指針，葉子結點存儲數據，B+樹的元素個數和分支樹是相同的，也就是一個元素值對應一個子樹。

B+樹的非葉子結點是為了快速定位到葉子結點上的關鍵字，就相當于給葉子結點層建立了索引。

整個B+樹就是一個多級索引結構，目的就是為了加速查詢的速度，查詢的速度是log(n)級別的

B+樹被廣泛用作數據庫的索引結構

B+樹可以用于：順序查找，隨機查找，范圍查找

B樹和B+樹的對比