我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平衡状态。频繁的左旋转和右旋转操作一定会影响整个AVL树的性能,除非是平衡与不平衡变化很少的情况下,否则AVL树所带来的搜索性能提升不足以弥补平衡树所带来的性能损耗。
那有没有绝对平衡的一种树呢?没有高度差也不会有平衡因子,没有平衡因子就不会调整旋转操作。2-3树正是一种绝对平衡的树,任意节点到它所有的叶子节点的深度都是相等的。
2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质,但它不属于二分搜索树。
2-3树定义
一颗2-3树或为一颗空树,或有以下节点组成:
2-节点,含有一个元素和两个子树(左右子树),左子树所有元素的值均小于它父节点,右子树所有元素的值均大于它父节点;
3-节点,还有两个元素和三个子树(左中右子树),左子树所有元素的值均小于它父节点,中子树所有元素的值都位于父节点两个元素之间,右子树所有元素的值均大于它父节点;
2-3树查找元素
2-3树的查找类似二分搜索树的查找,根据元素的大小来决定查找的方向。要判断一个元素是否存在,我们先将待查找元素和根节点比较,如果它和其中任意一个相等,那查找命中;否则根据比较的结果来选择查找的方向。
2-3树插入元素
插入元素首先进行查找命中,若查找命中则不予插入此元素,如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中,则在叶子节点中插入这个元素。
空树的插入很简单,创建一个节点即可。如果不是空树,插入的情况分为4种:
1.向2-节点中插入元素;
2.向一颗只含有一个3-节点的树中插入元素;
3.向一个父节点为2-节点的3-节点中插入元素;
4.向一个父节点为3-节点的3-节点中插入元素。
向2-节点中插入元素
如果未命中查找结束于2-节点,直接将2-节点替换为3-节点,并将待插入元素添加到其中。
向一颗只含有一个3-节点的树中插入元素
如果命中查找结束于3-节点,先临时将其成为4-节点,把待插入元素添加到其中,然后将4-节点转化为3个2-节点,中间的节点成为左右节点的父节点。如果之前临时4-节点有父节点,就会变成向一个父节点为2-节点的3-节点中插入元素,中间节点与父节点为2-节点的合并。
向一个父节点为3-节点的3-节点中插入元素
插入元素后一直向上分解临时的4-节点,直到遇到2-节点的父节点变成3-节点不再分解。如果达到树根节点还是4-节点,则进行分解根节点,此时树高+1(只有分解根节点才会增加树高),下面动画2-3树插入会出这个例子。
动画:2-3树插入
2-3树删除元素
2-3树删除元素相对比较复杂,删除元素也和插入元素一样先进行命中查找,查找成功才进行删除操作。删除操作大致分为三种情况:
1.删除元素位于非叶子节点
2.删除元素位于不为2-节点的叶子节点
3.删除元素位于2-节点的叶子节点
删除元素位于非叶子节点
删除非叶子节点上的元素,使用中序遍历得到后面第一个元素即直接后继元素,然后后继元素直接覆盖到待删除元素,再去删除后继元素(可做递归处理)。删除后再将删除元素的兄弟节点合并到父节点,父结点上的兄弟节点也合并到父节点的父节点,如果生成4-节点,直接分解。
删除元素位于不为2-节点的叶子节点
这个比较简单,直接删除即可。
删除元素位于2-节点的叶子节点
删除元素位于2-节点的叶子节点的步骤比较复杂,有四种情形:
1.父节点为2-节点,兄弟节点为3-节点;
2.父节点为2-节点,兄弟节点为2-节点;
3.父节点为3-节点;
4.整个树为满二叉树。
父节点为2-节点,兄弟节点为3-节点,删除元素位于2-节点的叶子节点
这种情况下将父节点向下合并,再去删除待删除元素,生成4-节点,有分解3个2-节点,中间的节点成为父节点。如果在Coding情况下,可以将父节点的元素覆盖到待删除元素所在的节点上,然后兄弟邻近的元素覆盖到父元素。
父节点为2-节点,兄弟节点为2-节点,删除元素位于2-节点的叶子节点
这种情况下需要通过中序遍历拿到直接后继元素,将这个后继元素向下合并,不断地向下合并直到合并到待删除元素的兄弟叶子节点。然后父元素覆盖到待删除元素所在的节点,兄弟节点邻近的元素覆盖到父元素。
父节点为3-节点,删除元素位于2-节点的叶子节点
元素11通过中序遍历得到后面第一个元素即直接后继元素,后继元素目的是为了替换待删除元素。拿到后继元素后,也一样向下合并,再去删除待删除元素,如果这个节点是4-节点时就去分解成3个2-节点,中间的节点与父节点合并。如果待删除元素位于最后一个节点的话(最下边最右边处),就采取父节点中与待删除元素邻近的元素。
2-3树为满二叉树时,删除叶子节点
2-3树满二叉树的情况下,删除叶子节点是比较简单的。将某叶子节点删除后,把当前删除节点的兄弟节点合并到父节点,同时将父节点的兄弟节点也合并到父节点的父节点中,如果合并过程中生成了4-节点,再分解了就是。
动画:2-3树删除
-----END---