二叉树、B树、红黑树 结构

发布时间:2022-03-01 12:12:04 作者:yexindonglai@163.com 阅读(57)

    在数据结构中,树这个概念用的非常多,特别是在Map 存储中其实就是一个树的概念, 这种结构也叫树结构,跟线性结构不同,线性结构就是链表,就是一条线就可以表示完了,但是树状结构的分支会有无限多,我们本章就是只要理清楚红黑树的概念,但是要想理清楚红黑树就必须得先知道普通的树和B树的结构,理清楚这两个树可以帮助我们更好地理解红黑树,因为红黑树和B树是可以互相转化的!

 

树没什么好说的,一个图你们就明白了树是怎么回事了!我们入场生活中的树的根是在下面的,但是在数据结构中,树的根节点一般是在上面的, 所以在图片中做了一层转化;我们只需要知道什么是树就可以了;

我们工作中用到的思维导图本质上也是树形结构

 

二叉树

     正常情况下,每棵树的树干都有多个树枝,而二叉树只有2个节点,区别如下:

二叉搜索树

二叉搜索树是二叉树的一种,是非常广泛的二叉树,又被称为二叉查找树,二叉排序树(没错,既然叫排序树,那么它就是有序的)

二叉搜索树的特性如下:

  • 除根节点之外,任意一个节点的2个子节点,左节点的值一定比父节点小,右节点的值一定比父节点的大,
  • 它的左右子树也是一颗二叉搜索树
  • 二叉树可以大大提高数据搜索的效率
  • 二叉搜索树存储的元素 必须是可比较性的 (比如 int、long、double 等。。。。。   如果是自定义类型,需要指定比较方式)

 

B树 (B-Tree 、B-树)

    B树是一种平衡的多路搜索树,多用于文件系统数据库的实现,B树特性:

  • 1个节点可以存储超过2个元素,可以拥有超过2个子节点,
  • 拥有二叉搜索树的一些性质
  • 每个节点的所有子树高度一致
  • 比较矮

B树子节点规则

如果B树内一个节点中有多个元素,那么每个元素的数值之间都会有一个子节点,如下图,

下面的一个节点中有3个元素,分别树60、80、95,那么对应就会有4个子节点,分别是:

  1. 60以下的值 (节点1)
  2. 60~85之间的值(节点2)
  3. 85~95之间的值(节点3)
  4. 95以上的值(节点4)

 

B树和二叉树相互转换

B树和可以二叉树相互转换,通过合并二叉树来得到B树,当然,不只有这一种合并方式,这里只是举例转换的方式;

 

红黑树

红黑树也是一种自平衡的二叉搜索树,以前叫做平衡二叉B树,是平衡二叉树的一种,红黑树必须满足以下5条性质

  1. 节点要么是 RED ,要么是 BLACK;
  2. 叶子节点(外部节点、空节点)都是 BLACK,就是每个 RED 节点下都会增加2个空的 BLACK,单个子节点的会自动增加一个空的 BLACK 节点,(注意:这些为 null 的 BLACK 都是假想出来的,写代码的时候不需要把这些空节点加进去)
  3. 根节点都是 BLACK
  4. RED 节点的子节点都是 BLACK
    1. RED 节点的 parent  都是 BLACK
    2. 从根节点到 叶子节点的所有路径上不能有2个连续的 RED 节点
  5. 从任一节点到 叶子节点 的所有路径都包含相同数目的 BLACK节点

 

   

                                       ↓

 

关键字后端