数据结构之红黑树

数据结构之红黑树
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

数据结构之红黑树

二叉查找树(二叉排序树)
特性:

  • 1.左子树的所有结点的值均小于或者等于它的根结点的值
  • 2.右子树上所有结点的值均大于或者等于它的根结点的值
  • 3.左右树同时也是二叉查找数

由于这样的特性,可以使用二分法的方式快速定位到10
这里写图片描述

二叉查询树的缺陷:

  • 递减插入数据时。会造成线性化。

这里写图片描述

为此引入了红黑树的概念,在二叉查询树上引入:

  • a.节点是红色或者黑色
  • b.根节点是黑色的
  • c.每个叶子节点都是黑色的空节点
  • d.每个红色节点的两个节点都是黑色(不可以有两个连续的红节点)
  • f.从任何一节点到每个叶子的所有路径都包含相同数目的黑色节点。

df 让解决了二叉查询树 可能导致的线性化问题
这里写图片描述

在进行 节点的删除或者添加 可能会导致 不满足df要求:
1.通过变色的方式:
尝试把红色节点变为黑色,或者把黑色节点变为红色。
2.通过旋转的方式
左旋转: 父节点被自己的右孩子取代,而自己成为自己的左孩子。
右孩子会带着 右孩子的右孩子c
这里写图片描述

右旋转:
父节点被自己的左孩子取代,而自己成为自己的右孩子。
左孩子会带着 左孩子的右孩子b
这里写图片描述

红黑树是:
TreeSet、TreeMap、HashMap等的底层基础。

举个栗子:

TreeSet
TreeSet 根据指定的属性进行排序
这里写图片描述
插入数据的基本原则:

  • 1.左孩子的值要小于 父类 右孩子的值要大于父类
  • 2.所有结点都要和根节点进行比较 ,小于根节点的放在左侧,大于根节点的放在右侧

*在这里插入图片描述*

本文来源蹊源的奇思妙想,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/14726

发表评论