动画 | 什么是2-3-4树？
source link: http://www.cnblogs.com/wotxdx/p/12180204.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
画了一系列树的动画，从二分搜索树，到AVL树，再到2-3树，再到基于2-3树的红黑树，都可以发现这些树都跟二叉查找树很像啊。
嘿嘿！二分搜索树就是二叉查找树；AVL树也是一颗二分搜索树，只多了高度差的限制；2-3树虽满足二分搜索树的性质，但不是一颗二分搜索树，2-3树由2-节点和3-节点组成的，满足了完美平衡性；基于2-3树的红黑树就是希望不要有3-节点，将3-节点转换成二叉，两个元素之间由红链接相连，并约定谁是子节点谁是红的，如下图。
本篇文章还会继续介绍满足二分搜索树性质的一棵树，它是2-3-4树，和2-3树一样也不是一颗二分搜索树。它在2-3树的基础上可以存储4-节点，4-节点由三个元素组成，有四个子树。
查找元素
和二分搜索树一样，根据元素的大小来决定查找的方向。要判断一个元素是否存在，我们首先将待查找元素和根节点逐一比较，如果它和当前节点中的一个元素相等，就返回查找命中；如果它比当前节点任一元素要大，就选择右递归进行下一个节点；如果它比当前节点任一元素要小，就选择左递归进行下一个节点；直到树底下的空节点，返回查找未命中。
插入元素
我们知道2-3树树底下最多是3-节点，可以直接插入元素然后再判断是否是4-节点，如果是向2-节点插入一个元素，变成3-节点无需分解；如果是向3-节点插入一个元素变成4-节点，进行向上变换将中间的键合并到父节点，如果父节点也变成4-节点，也接着继续分解4-节点，直到根节点，根节点也是4-节点，也接着分解，树高+1。
而2-3-4树的插入算法不一样，它没有向上进行变换分解4-节点的过程，因为2-3-4树可以存储4-节点。不过插入之前，进行查找命中的时候所过路径都要分解4-节点，如果查找未命中，则在此空节点插入一个元素；如果查找命中，说明2-3-4树是存在这个数的，则直接返回，之前的4-节点分解就分解了，没有必要再次合并4-节点。
插入算法同样也需要进行分解4-节点算法，不过是由向上变换变成了向下变换。
沿着链接向下进行变换分解4-节点，分为三种情况：
1）4-节点作为根节点，分解；
2）父节点为2-节点，当前节点为4-节点；
3）父节点为3-节点，当前节点为4-节点。
树底下插入一个元素只有两种情况了：向2-节点中插入元素和向3-节点中插入元素。
动画：插入算法
删除元素
既然是2-3-4树满足二分搜索树性质的，查找算法、插入算法和删除算法很多都是相似的。我们回忆一下二分搜索树的删除算法，它在删除任何一个非叶子节点时，都会获取右子树的最小叶子节点去代替待删除元素，然后进行右子树的删除最小叶子节点。
所以，2-3-4树也是一样，先进行命中查找，如果查找命中，就获取待删除元素的直接后继节点去替换待删除元素，然后进行右子树的删除最小元素。不过在查找待删除元素的同时，需要沿着左链接或者右链接向下进行变换，所过路径分解4-节点。
删除最小元素
从树底下删除一个元素，如果不是2-节点是很好删除的，从3-节点删除一个元素变成2-节点和从4-节点删除一个元素变成3-节点，都不会影响整个2-3-4树的绝对平衡性。如果从2-节点删除一个元素，而这个2-节点只有一个元素，删除之后这个节点变成一条空链接，会破坏树的绝对平衡性。
所以在沿着左链接向下进行变换的时候，确保当前节点不是2-节点（除了根节点）。如果当前节点是2-节点，可以先向兄弟节点借一个位置；如果兄弟节点也是2-节点，没法借，可以借父节点的一个位置。
但借的先后顺序不能弄错了，如果先向父节点借来一个位置，不清楚兄弟节点有多少子树会到时候没法分解的。例如兄弟节点是4-节点，当前节点、父节点一个位置和兄弟节点合并就变成了6-节点，比4-节点分解更加麻烦。
沿着左链接向下进行变换可以分为三种情况：
1）当前节点不是2-节点，跳过；
2）当前节点是2-节点，兄弟节点是2-节点，将当前节点、父节点的最小元素和兄弟节点合并成4-节点；
3）当前节点是2-节点，兄弟节点不是2-节点，将兄弟节点的最小元素移到父节点，父节点的最小元素移到当前节点（兄弟节点的最小元素要比父节点的最小元素要大，不是同一个元素）。
动画：删除最小算法
删除任意元素
删除任意元素首先要查找到这个元素，如果查找未命中则忽略之；如果查找命中，通过右子树中序遍历找到第一个元素（右子树最小元素），将这个元素直接替换掉待删除元素。
删除任意元素除了沿着左链接向下进行变换，还需要沿着右链接向下进行变换。沿着右链接向下进行变换也分为三种情况，将最小元素改为最大元素：
1）当前节点不是2-节点，跳过；
2）当前节点是2-节点，兄弟节点是2-节点，将当前节点、父节点的最大元素和兄弟节点合并成4-节点；
3）当前节点是2-节点，兄弟节点不是2-节点，将兄弟节点的最大元素移到父节点，父节点的最大元素移到当前节点（父节点的最大元素要比兄弟节点的最大元素要大，不是同一个元素）。
动画：删除任意算法
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK