源碼分享說明
- 本人非常熱衷于源碼研究，同時也非常願意将自己在源碼方面研究的心得進行分享，如果讀者也想對源碼進行研究，可以關注我的分享的文章。
- 在進行源碼解析的過程中，将會選擇庖丁解牛式的剖析，将會解析清楚每一行核心代碼，讓讀者能夠真正透徹了解，這樣無論是在以後的面試中還是獨立開發中間件都會有很大好處。
序言
本小節主要通過圖形的形式形象的描述二叉樹，2-3-4樹，讓讀者能夠輕松準确了解相關概念，希望讀者能夠多閱讀幾遍，徹底了解整個操作流程，本小節不會展示代碼，後面我們在分析hashmap,treemap源碼的時候會詳細解析每一步操作在代碼中是怎樣落地的
1. 2叉樹定義
二叉樹，每個節點最多有兩個“叉”，也就是兩個子節點，分别是左子節點和右子節點。不過并不要求每個節點都有兩個子節點，節點可以隻有左子節點或者右子節點。例如下面都是合法的二叉樹。
2. 2叉樹存儲
鍊式存儲法
每個節點有三個字段，其中一個存儲資料，另外兩個是指向左右子節點的指針。我們隻要拎住根節點，就可以通過左右子節點的指針，把整棵樹都串起來。大部分二叉樹代碼都是通過這種結構來實作的。
順序存儲法
如果二叉樹是一棵完全二叉樹，則非常适用順序存儲(基于數組存儲)，堆就是一種完全二叉樹，其使用的存儲方式就是順序存儲(數組)。堆這種資料結構以後我們在講解優先隊列時會詳細介紹。
我們把根節點存儲在下标 i = 1 的位置，那左子節點存儲在下标 2 * i = 2 的位置，右子節點存儲在 2 * i + 1 = 3 的位置。以此類推，B 節點的左子節點存儲在 2 * i = 2 * 2 = 4 的位置，右子節點存儲在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
3. 2叉查找樹
在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值。
二叉查找樹除了插入、删除、查找操作之外，還可以支援快速地查找最大節點和最小節點、前驅節點和後繼節點。中序周遊二叉查找樹，可以輸出有序的資料序列，時間複雜度是 O(n)，非常高效。是以，二叉查找樹也叫作二叉排序樹
下面展示根據輸入數組建構的2叉查找樹
1）如果數組元素順序為[9,8,7,6,5,4,3,2,1],形成左邊2叉查找樹結構
2）如果數組元素順序為[8,9,5,6,4,7,2,3,1],形成中間2叉查找樹結構
3）如果數組元素順序為[6,8,4,9,7,5,2,3,1],形成右邊2叉查找樹結構
在二叉查找樹中，查找、插入、删除等很多操作的時間複雜度都跟樹的高度成正比。兩個極端情況的時間複雜度分别是 O(n) 和 O(logn)，分别對應二叉樹退化成連結清單的情況和完全二叉樹。如果退化為連結清單，嚴重影響了性能，為了避免這種現象，通過左/右旋使二叉查找樹具有平衡性質，例如AVL樹，2-3-4樹，紅黑樹。
4. 2叉樹左/右旋
旋轉是二叉樹的基本操作，可以對任意一個存在父親節點的子節點進行旋轉（設被旋轉節點為x，其父親節點為p）
注意:左/右旋是對稱操作
我們可以通過檢查選擇前x是p的左兒子還是右兒子來判斷該次旋轉是左旋還是右旋。
左旋
旋轉前，x是p的右兒子。
旋轉後，x的左兒子（若存在）變為p的右兒子，p變為x的左兒子。
右旋
旋轉前，x是p的左兒子。
旋轉後，x的右兒子（若存在）變為p的左兒子，p變為x的右兒子。
5. 2-3-4樹的定義
2-3-4樹是一種階為4的B樹，是一種自平衡樹，滿足以下性質：
- 每個節點每個節點有1、2或3個key，分别稱為2（孩子）節點，3（孩子）節點，4（孩子）節點。
- 所有葉子節點到根節點的長度一緻（也就是說葉子節點都在同一層）。
- 每個節點的key從左到右保持了從小到大的順序，兩個key之間的子樹中所有的key一定大于它的父節點的左key，小于父節點的右key。
- 下面通過一張圖直覺展示2-3-4樹結構
6. 2-3-4樹檢索操作
整個檢索過程跟2叉查找樹一樣
下面通過一張圖直覺展示2-3-4樹檢索過程
如果我們需要在2-3-4樹查找33這個數字，則依次通過下面标紅色的節點就查詢到節點33
7. 2-3-4樹插入操作
（1）如果2-3-4樹中已存在目前插入的key，則插入失敗，否則一定在葉子節點中進行插入
（2）如果待插入的節點不是4節點，那麼直接在該節點插入
（3）如果待插入的節點是個4節點，那麼應該先分裂該節點然後再插入。
具體過程如下：
将4節點可以分裂成一個根節點和兩個子節點（節點各含一個key），在子節點進行插入，插入完成後，将分裂的根節點中的key向上層插入，然後重複第2步和第3步。
結論：
如果在4節點中進行插入，每次插入多出一個分支。
如果插入操作導緻根節點分裂，則2-3-4樹會生長一層。
下面通過片圖直覺展示2-3-4樹插入新節點整個過程
8. 2-3-4樹删除操作
（1）如果2-3-4樹中不存在目前需要删除的key，删除失敗。
（2）如果目前需要删除的key不位于葉子節點上。
（2.1）首先找目前節點的後繼，用後繼key覆寫，然後在它後繼key所在的子支中删除該後繼key。
（3）如果目前需要删除的key位于葉子節點上:
（3.1）該節點不是2節點，删除key，結束
（3.2）該節點是2節點，通過如下過程删除該節點：
具體過程如下：
（3.2.1）如果兄弟節點不是2節點，則父節點中的key下移到該節點，兄弟節點中的一個key上移
（3.2.2）如果兄弟節點是2節點，父節點是個3節點或4節點，父節點中的一個key向下與兄弟節點合并
（3.2.3）如果兄弟節點是2節點，父節點是個2節點，父節點中的key與兄弟節點中的key合并，形成一個3節點，把此節點看成目前節點（此節點實際上是下一層的節點），重複步驟3.2.1到3.2.3
結論：
如果是在2節點（葉子節點）中進行删除，每次删除會減少一個分支，
如果删除操作導緻根節點參與合并，則2-3-4樹會降低一層。
下面通過片圖直覺展示2-3-4樹删除節點整個過程
9. 2-3-4樹帶有預分裂的插入操作
上面的插入以及删除操作在某些情況需要不斷回溯來調整樹的結構以達到平衡。為了消除回溯過程，在插入操作過程中我們可以采取預分裂的操作，即我們在插入的搜尋路徑中，遇到4節點就分裂（分裂後形成的根節點的key要上移，與父節點中的key合并）這樣可以保證找到需要插入節點時可以直接插入（即該節點一定不是4節點）
下面通過片圖直覺展示2-3-4樹帶預分裂插入新節點整個過程
10. 2-3-4樹帶有預合并的删除操作
在删除過程中，我們同樣可以采取預合并的操作，即我們在删除的搜尋路徑中（除根節點，因為根節點沒有兄弟節點和父節點），遇到目前節點是2節點，如果兄弟節點也是2節點就合并（該節點的父節點中的key下移，與自身和兄弟節點合并）；如果兄弟節點不是2節點，則父節點的key下移，兄弟節點中的key上移。這樣可以保證，找到需要删除的key所在的節點時可以直接删除（即要删除的key所在的節點一定不是2節點）。
下面通過片圖直覺展示2-3-4樹帶預合并删除節點整個過程