2021年最好懂的红黑树

程序员张磊:
线性查找 —性能低—>二分查找— 二查叉树会出现退化成链表的问题—>出现AVL平衡二叉树—数据变化有频繁更新节点问题—>出现红黑树

hw-dong:
伪代码： if T is empty: X.color = black; T= X; return; X.Color = red; While(X.parent.color==red): if X.uncle.color==red: X.parent.color=X.uncle.color = black if X. parent. parent is not root: X. parent. parent.color=red; X = X.parent. Parent; else： break else: rotate and recolor；

Mr-Doraemon:
准备实习应聘，看完了老师的红黑树，比自己看文本资料节省了很多时间。老师的内容其实讲的挺细致的。提一个小建议，其实我觉得口音不是问题，但是在ppt上讲的我有时不知道老师指的是哪里。虽然有时候老师会在讲的地方画一下，但因为笔比较细，或者画的比较短，不能及时反应过来。最后感谢。

麦克老师讲算法:
你怎么可以在YouTube上开视频，为什么我进不去！[微笑]

流小术:
u1s1红黑树部分讲的不太行，讲关于高度引理那块太混乱了，黑高的定义一直含混不清，就是包不包括nil叶子，和黑节点包不包括自己这两个问题半天没讲明白。后面讲插入也是，到底几种情况半天都没讲清

onlytimeconvert:
性质1：红黑树是满二叉树（空树叶也看作结点） 性质2：k阶红黑树，从根到叶的简单路径长度，介于【k,2k】，或者说树高介于【k+1，2k+1】之间 性质3：k阶红黑树内部结点数最少时是一棵完全满二叉树，即内部结点数最少是2k-1 用这三条性质可以证明n个内部结点（即不为空的节点）红黑树最大高度：2*log2 (n+1)+1 证明：设红黑树的阶为k，高为h 由性质2得h <= 2k+1 则 k >= (h-1) / 2 由性质3得n >= 2^k – 1 即 n >= 2^ (h-1)/2 – 1 可得出 h <= 2 log2 (n+1)+1

刻舟行远:
总体好评，但观感并不完美，一是口音问题，听得比较累，二是备课不够用心，讲下来不是很流畅，结果就是up明明自己懂但观众反馈不是很好，如果能改进会好很多，总之还是感谢[支持]

撒旦cost:
老师的普通话我一句也听不懂。。。。

心中日月大又圆:
证明复杂度那块，弹幕好像吐槽的比较多，贴一个个人理解 欲证明：任意节点x，至少有2^bh(x)-1; 第一步：这个命题对单独的一个节点显然是成立的。 第二步：假设对于某节点的两个子节点，结论成立，则每个子节点至少有2^bh(child)-1个内节点； 第三步：就是要证明对于这两个子节点的父节点，结论仍然成立。如何证明呢？ 若子节点是红的，则bh(child) = bh(x); 若子节点是黑的，则bh(child) = bh(x) -1 (注意bh(x)的计算不包括x点的) 则bh(child) > bh(x) -1是肯定满足的，所以每个子节点至少有2^(bh(x)-1)-1个内节点 而父节点的内节点就等于两个子节点的内节点之和再加1，即 x>2*【2^(bh(x)-1)-1】+1 化简为 x>2^bh(x)-1 这样就基于子节点满足结论的假设，推出了父节点同样满足结论，这样父节点的父节点显然也同样满足，一直由下向上递归到根节点，结论显然也是满足的。 这里的二三步就是类似于数学归纳法中的，假设n=m成立，来推导n=m+1时也成立。 个人理解，欢迎交流指正。