当前位置: 首页 > 面试题库 >

请你说一说红黑树的性质还有左右旋转?

荀博
2023-03-14
本文向大家介绍请你说一说红黑树的性质还有左右旋转?相关面试题,主要包含被问及请你说一说红黑树的性质还有左右旋转?时的应答技巧和注意事项,需要的朋友参考一下

参考回答:

参考回答:

考察点:算法

公司:京东,阿里巴巴

1)平衡二叉树(AVL树):

红黑树是在AVL树的基础上提出来的。

平衡二叉树又称为AVL树,是一种特殊的二叉排序树。其左右子树都是平衡二叉树,且左右子树高度之差的绝对值不超过1。

AVL树中所有结点为根的树的左右子树高度之差的绝对值不超过1。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。

2)红黑树:

红黑树是在AVL树的基础上发展而来的。红黑树是一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此,红黑树是一种弱平衡二叉树,相对于要求严格的AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,通常使用红黑树。

性质:

\1. 每个节点非红即黑

\2. 根节点是黑的;

\3. 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的;

\4. 如果一个节点是红色的,则它的子节点必须是黑色的。

\5. 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次,

img

3)红黑树较AVL树的优点:

AVL 树是高度平衡的,频繁的插入和删除,会引起频繁的rebalance,导致效率下降;红黑树不是高度平衡的,算是一种折中,插入最多两次旋转,删除最多三次旋转。

所以红黑树在查找,插入删除的性能都是O(logn),且性能稳定,所以STL里面很多结构包括map底层实现都是使用的红黑树。

4)红黑树旋转:

旋转:红黑树的旋转是一种能保持二叉搜索树性质的搜索树局部操作。有左旋和右旋两种旋转,通过改变树中某些结点的颜色以及指针结构来保持对红黑树进行插入和删除操作后的红黑性质。

左旋:对某个结点x做左旋操作时,假设其右孩子为y而不是T.nil:以x到y的链为“支轴”进行。使y成为该子树新的根结点,x成为y的左孩子,y的左孩子成为x的右孩子。img

右旋:对某个结点x做右旋操作时,假设其左孩子为y而不是T.nil:以x到y的链为“支轴”进行。使y成为该子树新的根结点,x成为y的右孩子,y的右孩子成为x的左孩子。img

 类似资料:
  • 本文向大家介绍请你来说一说红黑树和AVL树的定义,特点,以及二者区别?相关面试题,主要包含被问及请你来说一说红黑树和AVL树的定义,特点,以及二者区别?时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 平衡二叉树(AVL树): 平衡二叉树又称为AVL树,是一种特殊的二叉排序树。其左右子树都是平衡二叉树,且左右子树高度之差的绝对值不超过1。一句话表述为:以树中所有结点为根的树的左右子树高度之差

  • 本文向大家介绍请你说一下黑盒白盒相关面试题,主要包含被问及请你说一下黑盒白盒时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 黑盒测试: 黑盒测试也称功能测试或数据驱动测试,它是在已知产品所应具有的功能,通过测试来检测每个功能是否都能正常使用,在测试时,把程序看作一个不能打开的黑盆子,在完全不考虑程序内部结构和内部特性的情况下,测试者在程序接口进行测试,它只检查程序功能是否按照需求规格说明书

  • 本文向大家介绍请你说一下,B+树和B-树?相关面试题,主要包含被问及请你说一下,B+树和B-树?时的应答技巧和注意事项,需要的朋友参考一下 考察点:树   b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”; b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢); 对于范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历

  • 本文向大家介绍请你说一说有了进程,为什么还要有线程?相关面试题,主要包含被问及请你说一说有了进程,为什么还要有线程?时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 线程产生的原因: 进程可以使多个程序能并发执行,以提高资源的利用率和系统的吞吐量;但是其具有一些缺点: 进程在同一时间只能干一件事 进程在执行的过程中如果阻塞,整个进程就会挂起,即使进程中有些工作不依赖于等待的资源,仍然不会执行

  • 本文向大家介绍请你来说一说协程?相关面试题,主要包含被问及请你来说一说协程?时的应答技巧和注意事项,需要的朋友参考一下 参考回答: 1、概念: 协程,又称微线程,纤程,英文名Coroutine。协程看上去也是子程序,但执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行。 例如: 由协程运行结果可能是12x3yz。在执行A的过程中,可以随时中断,去执行B,B也可能在

  • 本文向大家介绍请你说一说epoll原理?相关面试题,主要包含被问及请你说一说epoll原理?时的应答技巧和注意事项,需要的朋友参考一下 调用顺序: int epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); int epoll_wait(int epfd, struc