数据结构--红黑树

2023-10-20 10:30:45 浏览数 (1)

概念

前面对树已经有了一个认识,现在看下红黑树的定义。 开始之前提几个问题:

  1. 什么是红黑树
  2. 有什么用
  3. 怎么实现
  4. 优缺点

什么是红黑树

红黑树: 又叫二叉平衡树 红黑树又红又黑,真正的意义是什么?为什么要红一下黑一下?

会左旋 和 右旋,不会出现单边增长太多,会平衡。

红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

有什么用

为了实现快速定位而设计的算法。

几乎所有基于二叉树的算法,都是基于二分法进行查找的,只要数据100%是按照一定顺序排列的,那么就可以被二分法查找。

假疫有10亿数据只需要不到30次比较就能查找到目标。

二叉查找树这一数据结构并不难,而红黑树之所以难是难在它是自平衡的二叉查找树,在进行插入和删除等可能会破坏树的平衡的操作时,需要重新自处理达到平衡状态。

红黑树特点:

  1. 节点要么红、要么黑
  2. 根节点是黑色
  3. 叶节点null,都是黑色
  4. 每个红色节点包含的子节点,一定为黑色
  5. 任意一结点到每个叶子结点的路径都包含数量相同的黑子结点。

0 人点赞