动画 | 什么是2-3-4树?
画了一系列树的动画,从二分搜索树,到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-节点,将兄弟节点的最大元素移到父节点,父节点的最大元素移到当前节点(父节点的最大元素要比兄弟节点的最大元素要大,不是同一个元素)。
动画:删除任意算法