- 当待删除元素在2节点时,由于删除这个元素会导致2节点失去唯一的元素,引发树中某条路径的高度发生变化,为维持平衡,此时有两种方法。
- 先删除再对2-3树进行平衡调整。
- 想办法让这个被删除的元素不可能出现在2节点中。如果发现删除元素树2节点则会从兄弟节点或父节点借个元素,当前2节点变为3节点或临时4节点,然后再删除目标数据。
和标准的二叉查找树由上向下生长不同,2-3树的生长是由下向上的。
2.6 优点、缺点优点:
- 2-3树在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数,且这两个操作都只会访问一条路径上的结点,所以任何查找或者插入的成本都肯定不会超过对数级别。
- 完美平衡的2-3树要平展的多。例如含有10亿个结点的一颗2-3树的高度仅在19到30之间。我们最多只需要访问30个结点就能在10亿个键中进行任意查找和插入操作。
缺点:
- 我们需要维护两种不同类型的结点,查找和插入操作的实现需要大量的代码,而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
- 平衡一棵树的初衷是为了消除最坏情况,但我们希望这种保障所需的代码能够越少越好,越简单越好,显然2-3树也不太适合。
既然已经懂了2-3树的实现,接下来我们对2-3树稍微变型下就是红黑树了,你可以认为红黑树的本质其实是对概念模型2-3-4树的一种实现。
3 红黑树3.1 2-3树跟红黑树关联由于直接进行不同节点间的转化会造成较大的开销,所以选择以二叉树为基础,在二叉树的属性中加入一个颜色属性来表示2-3树中不同的节点。
- 2-3树中的2节点对应着红黑树中的黑色节点。
- 2-3树中的非2节点是以红节点 黑节点的方式存在,红节点的意义是与黑色父节点结合,表达着2-3树中的3,4节点。有的书上把红色说成了红色链接,也是一直理解方法。
先看2-3树到红黑树的节点转换。2节点直接转化为黑色节点。3节点这里可以有两种表现形式,左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。
由于3节点转化到时候可以左倾也可以右倾,如果查看算法书籍,你会发现为了简单化,算法书籍中统一规定只用左倾红黑树。
红黑树跟2-3树转化到时候,可以认为将红色节点顺时针上升45度,来跟它到父节点保持平衡,再将红色到跟父节点看作一个整体。