赞
踩
红黑树是一种自平衡二叉查找树(二叉排序树)。与平衡二叉树(avl树)不同的是,红黑树是弱平衡二叉树,即它的左右子树高度差有可能大于1,但不超过一倍。
总结:根黑叶黑,红不相邻,黑色平衡。
时间复杂度:查询、插入和删除均为O(logn)。
关于红黑树的操作大家可以自己去在线演示网站试试:
中文版:https://rbtree.phpisfuture.com/
英文版:https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
PS:英文版网站还有各种数据结构的在线演示哦:
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
口诀:叔红要变色,叔黑要左右;右子要左旋,左旋自己来;左子要右旋,右旋父亲去。
也就是把节点涂成黑色或红色。
插入的新节点一定是红色,也就是“红插”,后续将根据平衡性变色。
同时由于是红插,插入操作只会破坏第4个性质,也就是“红不相邻”的性质;调整时才会破坏第2或第5个性质。
联系
差别
1、红黑树与AVL树性质(自平衡、查找、插入、删除的时间复杂度)
2、为什么用红黑树不用二叉平衡树
3、证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗?
4、红黑树的插入算法复杂度最坏情况是
解答:B。
5、关于红黑树和AVL树,以下哪种说法不正确?
解答:D。TreeMap是红黑树实现的。
6、 下面描述错误的是____。
解答:B。红黑树是黑色完美平衡,并没有红色完美平衡的说法。
7、请你来说一说红黑树和AVL树的定义,特点,以及二者区别
8、关于红黑树,以下哪种说法是不正确的?
解答:D。红黑树查询效率低于AVL数,插入、删除效率高于AVL树。
9、采用插入方式构建一颗大小为n的红黑树的时间复杂度是多少?
解答C。
10、关于红黑树,下述说法错误的是_______.
解答:D。至多3个操作。
11、以下哪个数据结构底层是用红黑树实现的?
解答:C。
12、包含 8 个内部结点的红黑树中,最多可有几个红色结点,最少可有几个红色结点。
13、红黑树的插入复杂度为( )。
解答:D。
14、红黑树在处理过程中红黑节点会产生冲突,请问在下列操作中解决的冲突中,正确的是
解答:C。
15、证明:在一棵红黑树中,从某节点x到其后代叶节点的所有简单路径中,最长的一条至多是最短一条的2倍。
16、在一棵有 n 个关键字、高度为 h 的红黑树中,根的高度至少是多少?至多是多少?
17、在一棵黑高为k的红黑树中,内部节点最多可能有多少个?最少可能有多少个?
18、将关键字41,38,31,12,19,8连续地插入一棵初始为空的红黑树之后,试画出该节点树。
19、试描述一棵含有n个关键字的红黑树,使其红色内部结点个数与黑色内部结点个数的比值最大。这个比值是多少?该比值最小的数又是怎样呢?比值是多少?
20、考查含有2012个内部节点的红黑树。
a) 该树可能的最小黑高度 dmin 是多少?
b) 该树可能的最大黑高度dmax是多少?
c) 该树可能的最小高度 hmin 是多少?
21、证明红黑树的高度最多为2logN
22、为什么插入的节点一定是红色?红插有可能破坏红黑树的性质,也有可能不破坏,但黑插一定破坏性质5
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。