备案 网站名称 重复,农大南路网络营销推广优化,大恒建设集团有限公司网站,锦州做网站的个人目录 一、红黑树的定义#xff08;一#xff09;黑/红结点、叶子节点#xff08;二#xff09;黑色完美平衡 二、红黑树的性质#xff08;一#xff09;黑高和高度#xff08;二#xff09;叶子结点个数 三、红黑树与AVL对比 一、红黑树的定义
红黑树是一棵二叉排序树… 目录 一、红黑树的定义一黑/红结点、叶子节点二黑色完美平衡 二、红黑树的性质一黑高和高度二叶子结点个数 三、红黑树与AVL对比 一、红黑树的定义
红黑树是一棵二叉排序树满足结点值中左子树根结点右子树每个结点都带有颜色属性即黑或红。可以简单地说它是一棵“ 平衡二叉树 ”但由于它的左、右子树高度差的绝对值有可能超过 1所以并不是严格意义上的平衡二叉树只能说是一棵弱平衡二叉树相对于正常的平衡二叉树在进行插入、删除操作后二叉树的平衡调整中由于不要求完全平衡其所需的代价更低。
一黑/红结点、叶子节点
在红黑树中根结点一定是黑结点其余结点为黑或红树中不允许有相邻的两个红结点另外树中也存在叶子结点它是黑结点是实际意义上不存在的空结点且任一结点不包括到叶子结点的路径上所经过的黑结点的个数相同注意叶子结点也算作黑结点计入。
二黑色完美平衡
若红黑树中左子树和右子树的层数相等则称为黑色完美平衡如下
二、红黑树的性质
一黑高和高度
任意一结点不包括到叶子结点所经过的黑结点的个数称为该结点的黑高而根结点的黑高即为红黑树的高度黑高用bh表示例如下图这棵红黑树的高度即为根结点3的黑高即bh2 由于根结点到叶子结点的最长路径不大于最短路径的两倍且至少有一半结点为黑结点即树的黑高至少为h/2所以对于一个含有n个结点的红黑树其高度为h ≤ 2log2(n1)即最大高度为2log2(n1)。
二叶子结点个数
红黑树中叶子结点空结点与二分判定树和B树中的外部结点相同都不是实际存在的结点是虚构的。若红黑树的结点总数为n则外部结点的个数为n1。
三、红黑树与AVL对比
与平衡二叉树AVL相比红黑树只追求大致上的平衡通过引入红、黑颜色属性以及相应的规则来保证平衡性所以红黑树在插入和删除结点时只需进行少量的颜色调整和旋转操作从而比AVL实现更简便而AVL必须遵从严格的平衡条件使得在进行插入和删除结点操作后需要多次旋转调整来保证平衡可能会增加操作的时间复杂度。另外AVL与红黑树相同两者查找、插入和删除操作的时间复杂度均为O(log2n)。 由于每一棵红黑树都是一颗二叉排序树因此在对红黑树进行查找时可以采用运用于普通二叉排序树上的查找算法在查找过程中不需要颜色信息。
