再回首数据结构—红黑树(一)

栏目: 数据库 · 发布时间: 4年前

内容简介:红黑树与AVL树一样同为二分搜索树,红黑树又称为是保持“黑平衡”的二叉树,红黑树最大高度为:2logn,红黑树由这么几个独特的特征:1、每个节点或黑或红2、根节点为黑色

红黑树与AVL树一样同为二分搜索树,红黑树又称为是保持“黑平衡”的二叉树,红黑树最大高度为:2logn,红黑树由这么几个独特的特征:

1、每个节点或黑或红

2、根节点为黑色

3、每个叶子节点(最后的空节点)都为黑色

4、如果一个节点为红色,则他孩子节点全为黑色

5、从任意节点到叶子节点,经过的黑色节点为一样多的

6、所有红色节点都向左倾斜

再回首数据结构—红黑树(一)

在之前的二叉搜索树中我们在实现的节点结构中定义了用于存储元素的e、用于存放左子树的left、用于存放右子树的right等对象,而在AVL树中比二叉搜索树有所不同由于AVL需要维护左右子树的节点高度所以多了一个元素height用于存放节点的高度;

红黑树也是基于之前二叉搜索树变体而来的,在红黑树中节点也只比二叉搜索树多一个元素,二叉搜索树的节点由以下元素组成:

e :用于存储节点元素

left:用于存储左子树

right:用于存储右子树

color:用于标志节点颜色,节点是红色或黑色

红黑树的代码定义:

type RBT struct {
    root    *RBTNode
    size    int
    compare Comparable
 }

 type RBTNode struct {
    e     interface{}
    left  *RBTNode
    right *RBTNode
    color bool
 }

根据红黑树的特性、定义可知:

1、大小为N的红黑树其高度不超过2logN

2、最坏情况下插入、查找元素的时间复杂度为:2logN

3、平均情况下插入、查找元素的平均复杂度为:logN

这里只简单介绍了红黑树的相关概念,下面将从代码实现的角度具体分析红黑树的实现;


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

垃圾收集

垃圾收集

琼斯 / 谢之易 / 人民邮电出版社 / 2004-4-1 / 45.00元

书围绕着动态内存自动回收的话题,介绍了垃圾收集机制,详细分析了各种算法和相关技术。 本书共12章。第1章首先介绍计算机存储器管理的演化和自动内存回收的需求,并引入了本书所使用的术语和记法。第2章介绍了3种“经典”的垃圾收集技术:引用计数(reference counting)、标记-清扫(mark-sweep)和节点复制(copying)。 随后的4章更详细地讨论了上述这些垃圾收集方式......一起来看看 《垃圾收集》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

MD5 加密
MD5 加密

MD5 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具