1. 2-3-4樹的定義
2-3-4樹是一種階為4的B樹。它是一種自平衡的數(shù)據(jù)結(jié)構(gòu)，可以保證在O(lgn)的時(shí)間內(nèi)完成查找、插入和刪除操作。它主要滿足以下性質(zhì)：
（1）每個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)有1、2或3個(gè)key，分別稱為2（孩子）節(jié)點(diǎn)，3（孩子）節(jié)點(diǎn)，4（孩子）節(jié)點(diǎn)。
（2）所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的長(zhǎng)度一致（也就是說葉子節(jié)點(diǎn)都在同一層）。
（3）每個(gè)節(jié)點(diǎn)的key從左到右保持了從小到大的順序，兩個(gè)key之間的子樹中所有的
key一定大于它的父節(jié)點(diǎn)的左key，小于父節(jié)點(diǎn)的右key。
2. 插入操作
（1）如果2-3-4樹中已存在當(dāng)前插入的key，則插入失敗，否則最終一定是在葉子節(jié)點(diǎn)中進(jìn)行插入操作
（2）如果待插入的節(jié)點(diǎn)不是4節(jié)點(diǎn)，那么直接在該節(jié)點(diǎn)插入
（3）如果待插入的節(jié)點(diǎn)是個(gè)4節(jié)點(diǎn)，那么應(yīng)該先分裂該節(jié)點(diǎn)然后再插入。一個(gè)4節(jié)點(diǎn)可以分裂成一個(gè)根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)（這三個(gè)節(jié)點(diǎn)各含一個(gè)key）然后在子節(jié)點(diǎn)中插入，我們把分裂形成的根節(jié)點(diǎn)看成向上層插入的節(jié)點(diǎn)，然后重復(fù)第2步和第3步。
如果是在4節(jié)點(diǎn)中進(jìn)行插入，每次插入會(huì)多出一個(gè)分支，如果插入操作導(dǎo)致根節(jié)點(diǎn)分裂，則2-3-4樹會(huì)生長(zhǎng)一層。
延伸閱讀
學(xué)習(xí)是年輕人改變自己的最好方式