为什么红黑树比AVL树效率高?

2023-10-23 19:04
文章标签 红黑树 avl 效率高

本文主要是介绍为什么红黑树比AVL树效率高?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 红黑树的提出
  • 都知道的几个定义
  • 理解红黑树的高效
  • 总结

前言

红黑树为什么这么火呢?大家应该都很清楚,面试的时候不管三七二十一,就问你:什么是红黑树,为什么要用红黑树?就好像他很懂,就好像知道红黑树就很牛逼一样。

在这里插入图片描述

whatever,如果还不懂红黑树,不管有没有基础的,希望通过本次的介绍,可以帮助你更容易的理解红黑树。

红黑树的提出

首先,什么是红黑树?红黑树也是一个自平衡的二叉查找树,如果没有基础的,可以先去前面的文章了解一下数据结构以及AVL树。

为什么要用红黑树?相比AVL树红黑树的效率更高。为什么?

我们知道AVL树是在插入或删除节点时通过旋转操作使节点的左右子树高度差不大于1,从而保证了树的平衡。但是AVL树平衡比较严格,基本上每添加或删除一个节点都会旋转一次,频繁的旋转会导致效率低下,为此红黑树就被提出了。

都知道的几个定义

相信大家在学习红黑树的时候都看过以下几个定义:

  • 每个节点必须是红色或黑色。
  • 根节点必须是黑色。
  • 所有叶子结点都是黑色。
  • 两个红节点不能相邻,如果当前节点是红色,子节点必须是黑色。
  • 从任意节点到每个叶子节点的路径中,黑色节点数量是相同的。

还有等等。

这个定义看完之后你能理解为什么红黑树的效率会比AVL树高吗?反正我是理解不了,所以不要被这些定义影响,更不用死记硬背这些东西。

还有红黑树本质是2-3-4树、红黑树利用了缓存这些说法,我个人是没理解。

理解红黑树的高效

说实话,我在刚接触到红黑树的时候,首先是被开篇的定义所影响,其次发现也是通过左旋右旋保持平衡,感觉与AVL树没什么区别,反而比AVL树更加复杂,更加难以理解,所谓的“红黑树比AVL树的效率高”就更不用说了。

如何理解红黑树比AVL树的效率高呢?

红黑树相对AVL树平衡性比较宽松,没有那么严格,也就是红黑树的旋转次数不会那么频繁,这也是红黑树为什么比AVL树效率高的原因。

那么红黑树的平衡性宽松怎么体现?为什么旋转次数相对较少呢?以上的两个定义重点关注一下:

  1. 两个红节点不能相邻,如果当前节点是红色,子节点必须是黑色。
  2. 从任意节点到每个叶子节点的路径中,黑色节点数量是相同的。

这两个定义意味着树上的最长链上的节点是红黑相间,因为上述1。最短链全是黑节点,因为上述2。

在这里插入图片描述

如上图可以看到,最长链(右)和最短链(左)之间的长度差是2:4,如果此时在右树插入一个节点就会进行旋转保持平衡,如下图

在这里插入图片描述

因此可以知道:红黑树的最长链和最短链之间的长度差不会超过两倍,也正因如此,其旋转次数在比AVL树少的情况下也保持了相对宽松的平衡,效率也就较AVL树高一些。但是,红黑树和AVL树两者整体的复杂度都为O(log n)。

总结

  1. 红黑树是为了解决AVL树频繁旋转导致效率低下被提出。
  2. AVL树平衡性取决于左右子树高度差(不能大于1,比较严格),红黑树平衡性取决于红黑节点的分布(模糊,宽松)。
  3. 红黑树效率高于AVL树具体体现在:红黑树的最长链和最短链之间的长度差不会超过两倍。
  4. 红黑树和AVL树两者整体的复杂度都为O(log n)。

这篇关于为什么红黑树比AVL树效率高?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/269860

相关文章

红黑树的旋转

红黑树的基本性质 红黑树与普通的二叉搜索树不同,它在每个节点上附加了一个额外的属性——颜色,该颜色可以是红色或黑色。通过引入这些颜色,红黑树能够维持以下 5 个基本性质,以确保树的平衡性: 每个节点是红色或黑色。根节点是黑色。所有叶子节点(NIL 节点)是黑色。如果一个节点是红色的,那么它的两个子节点都是黑色的(即,红色节点不能有红色子节点)。从任一节点到其每个叶子节点的所有路径上都包含相同数

C++笔记19•数据结构:红黑树(RBTree)•

红黑树 1.简介:         红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。 当搜索二叉树退化为单支树时,搜索效率极低,为了使搜索效率高,建立平衡搜索二叉树就需要"平衡树"来解决。上一篇博客介绍了AVL树,这

AVL 树的旋转

什么是 AVL 树? AVL 树是一种自平衡二叉搜索树(Binary Search Tree, BST),以其发明者 G. M. Adelson-Velsky 和 E. M. Landis 的名字命名。它的特点是对于任意一个节点,其左右子树的高度差(平衡因子)不超过 1,这确保了 AVL 树的高度在 O(log n) 的范围内,从而保证了插入、删除和查找操作的时间复杂度都是 O(log n)。

【C++】【数据结构】一步一步写平衡二叉树[AVL]

转载:有修正,原作者存在一些错误,这里进行了更正。/* 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体第一个引入平衡概念的二叉树。特点:对于每一个结点,它的左右子树的高度之差不能超过1,若插入或删除一个节点之后使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。这个方案很好的解决的了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度

数据结构(13)——平衡二叉树(红黑树)

欢迎来到博主的专栏——数据结构 博主ID:代码小号 文章目录 红黑树红黑树节点之间的关系红黑树的插入uncle节点为红色uncle节点是黑色或者没有uncle节点 红黑树 平衡二叉树最出名的除了AVL树之外就是红黑树(RBTree),所谓红黑树,即拥有以下特性的平衡二叉树 (1)每个节点要么是红色,要么是黑色 (2)根节点必须是黑色 (3)红色节点的子节点必须是黑色 (

hello树先生——红黑树

红黑树 一.什么是红黑树二.红黑树的实现1.创建树节点结构2.插入功能的实现 三.提供一些常见二叉树接口四.进行平衡测试 一.什么是红黑树 红黑树是一种自平衡的二叉搜索树,具有以下特性: 节点颜色:每个节点要么是红色,要么是黑色。根节点:根节点始终是黑色。红色节点:红色节点的子节点不能是红色(即没有两个连续的红色节点)。黑色节点:从任何节点到其每个叶子节点的路径上,必须包含

C++深入理解AVL树的设计与实现:旋转操作详解

C++深入理解AVL树的设计与实现:旋转操作详解 AVL树(Adelson-Velsky and Landis Tree)是一种自平衡二叉搜索树,通过在插入和删除节点时进行旋转操作来保持树的平衡。AVL树的每个节点都维护一个平衡因子,即左右子树的高度差,确保其绝对值不超过1。本文将详细介绍如何实现一个AVL树,并提供旋转操作的实现细节。 一、AVL树的基本概念 AVL树是一种高度平衡的二叉搜

数据分析-第三方库(工具包):Numpy【使用ndarray对象处理多维数组】【比Python原生list运算效率高:①内存块风格;②支持并行化运算;③底层用C编写,内部解除了GIL(全局解释器锁)】

一、Numpy优势 Numpy运算速度上的优势Numpy的数组内存块风格Numpy的并行化运算 1、Numpy介绍 Numpy(Numerical Python)是一个开源的Python科学计算库,用于快速处理任意维度的数组。 Numpy支持常见的数组和矩阵操作。对于同样的数值计算任务,使用Numpy比直接使用Python要简洁的多。 Numpy使用ndarray对象来处理多维数组,

数据结构-高层数据结构:映射/字典(Map)【有序字典:基于二分搜索树、基于平衡二叉树、基于红黑树、基于链表】【无序字典:基于哈希表】

Map.java package map;/*** 映射*/public interface Map<K,V> {/*** 添加元素** @param key* @param value* @return void*/void add(K key,V value);/*** 删除元素** @param key* @return V*/V remove(K key);/*** 查看是

<C++> 红黑树

目录 1. 红黑树的概念 2. 红黑树的性质 3. 红黑树节点的定义 4. 红黑树的插入操作 5. 红黑树的验证 6. 红黑树与AVL树的比较 7. 红黑树的删除         红黑树比AVL树更优一些,因为AVL要求太严格,左右高度差不超过1,而红黑树采用颜色来控制,只要求最长路径不超过最短路径的2倍,属于近似平衡 1. 红黑树的概念         红黑树,是一种二叉搜索