赞
踩
1.简介
2-3-4属于一种多路查找树,是一种四阶的B树,它的结果有以下特点
2.三种节点的示意图
①:2-节点:有两个子树的节点
②:3-节点:有三个子树的节点
③:4-节点:有四颗子树的节点
3.构建一颗2-3-4树
2-3-4树中结点添加需要遵守以下规则:
将1 2 3 4 5 6 7 8 9 10 11 12 构建成一个2-3-4树
由于我们是从下到上进行构建的,所以我们能够保证所有叶子节点都拥有相同的深度
1.认识红黑树的特性
1.每个节点不是红色就是黑色
2.根节点是黑色
3.每个叶子节点(NIL节点,空节点)是黑色的
4.如果一个节点是红色的,则他的子节点必须是黑色的
5.从一个节点到该节点的所有子孙节点的所有路径上包含相同数目的黑色节点
特殊说明:我们每次新插入的节点都是红色
将插入的节点写为红色,就不会违背特性5,少违背一条特性,也就意味着我们需要处理的情况也就越少。
2.从2-3-4树到红黑树
2-3-4树的查询操作像普通的二叉搜索树一样,非常简单,但由于其结点元素数不确定,在一些编程语言中实现起来并不方便,实现一般使用它的等同——红黑树。
至于为什么说红黑树是 2-3-4树的一种等同呢,这是因为 2-3-4树的每一个结点都对应红黑树的一种结构,所以每一棵 2-3-4树也都对应一棵红黑树,下图是 2-3-4树不同结点与红黑树子树的对应。
3.通过2-3-4树构建红黑树
如上图所示,虽然向红黑树中插入了一个新结点,但由于旋转和变色,子树的高度保持不变。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。