从二叉排序树到红黑树

二叉排序树

二叉排序树是一种比较简单的数据结构,即某个节点左边的节点都是比较小的节点,右边的节点都是比较大的节点,并且某一个节点的左右子树都是一颗二叉排序树。利用树的结构特性可以提高查找元素的效率。

但是二叉排序树无法面对一种最坏情况,当树是一颗单支树,这样的树虽然也满足二叉排序树的定义,但是和普通的数组也没有区别了。

所有我们需要一定的策略来保证二叉排序树的结构,提高二叉排序树的查找效率,这就引入了平衡二叉排序树。

平衡二叉树

平衡二叉排序树之于普通的二叉排序树有一个额外的要求就是,任意节点的左右子树的高度之差不能超过1。这样可以避免二叉树成为单支树的最坏情况,还能保证查找某个元素时的时间复杂度基本在\(O(nlogn)\)量级。

但是平衡二叉树也存在一个问题,就是当平衡二叉树的插入和删除操作比较多的时候,维持树平衡时涉及到节点的旋转操作会带来比较大的开销,进而导致这种数据结构的效率降低。因为插入或者删除元素破坏了原来二叉树的结构,可能破坏平衡性条件,因此需要相应的调整措施来保证其符合平衡二叉树的定义。

红黑树

红黑树也是为了避免出现单支树的情况,即为了提高二叉排序树的查找效率。同时也为了改善平衡二叉排序树中的插入和删除操作频繁而导致开销过大的情况。

因此红黑树也有一些规则对二叉排序树的结构进行约束(就像AVL中左右子树高度差不能超过1的约束),首先红黑树定义了一些内容如节点的颜色(红或者黑),外部节点(空树,黑色的),黑边(连向黑色节点的边),黑长度(两个节点中黑边数量),黑高度(任意节点到该节点的黑长度) ,黑深度(根节点到该节点的黑长度),在以上定义下,一颗红黑树要满足如下的约束:

  • 根节点是黑色的
  • 红节点没有红孩子(孩子节点只能是黑色的)
  • 任意一个节点u到外部节点的黑高度相同

可以通过数学证明(证明有空再补上),具有n个节点的红黑树的高度至多为\(2nlog(n+1)\).这样也就是说在红黑树中查找元素的时间复杂度为 \(O(2nlog(n+1)=O(nlogn)\) ,虽然时间复杂度比AVL高,但是数量级和AVL相同。

同时红黑树由于其特殊的约束条件以及对应的元素插入和删除策略,使得调整二叉树结构使其满足约束时的额外开销比较小。因此在实际应用中红黑树的应用很广泛。

红黑树的插入和删除操作策略比较复杂,并且情况也比较多,网上也有很多相应的技术博客进行了介绍,这里简单总结一下,供温习是快速回想起来。

插入元素

  • 插入时插红节点,若插入为根节点则直接改成黑色。
  • 如果父亲节点是黑色,插入成功。
  • 如果父亲节点和叔叔节点都是红色,则父亲叔叔变黑,爷爷变红,并且将爷爷作为新插入节点,向上继续调整。
  • 如果父亲红叔叔黑,则存在一次旋转和两次旋转的问题。

删除元素

  • 删除非叶子节点时,首先将该元素替换成右子树的最小值,然后删除最小值的那个节点。
  • p父亲 s兄弟 l兄弟做孩子 r 兄弟右孩子
  • 分为5种情况(当删除为父亲的左孩子)
    • pslr全黑,s变红,继续向上调整
    • l为红…….
    • p 为红…….
    • r 为红…….
    • s 为红…….
    • 当删除为父亲的右孩子,对称地查看 r p l s

贝叶斯公式的理解

首先上图展示了贝叶斯公式的一个定义和简单的变形。

B:表示证据,或者说结果;A表示理由,原因\(\overline{A}\)则表示除了A之外的原因。

P(A|B)表示一个结果发生了,有多大的概率是A这个原因导致的,即How much you can trust the evidence,你有多大的把握相信B这个结果是由A导致的。

带入实际的场景很很好理解:B表示老板骂你,A表示工作失误。工作失误可能是老板骂你的原因,那么有一天老板骂你了,由多大的概率是因为你工作出现了失误呢?这就是通过P(A|B)进行刻画。

假设\(\overline{A}\)表示老板被家暴了,老板收到家庭中的暴力,迁怒至你的身上也是一种你被骂的原因。

全概率公式展开:P(老板骂你)=P(老板骂你| 老板被家暴)P(老板被家暴)+ P(老板骂你| 工作失误 )P(工作失误) ,可以老板骂你的概率由两个起因来决定。

P( 工作失误|老板骂你)= P(老板骂你| 工作失误 )P(工作失误) /P(老板骂你)
这样就容易理解贝叶斯公式的含义了。

P(老板骂你| 工作失误 ) 这一项如何理解,表示出现工作失误时,老板骂你的概率。这就可能取决于老板的性格。

  • 假设1:如果老板是一个对工作十分严格的人,并且家庭十分和睦。某一天老板骂你了,那么大概率时你工作出现了失误。
  • 假设2:如果老板时对工作很宽容的人,即使你工作出现失误,鲜有骂人的现象,但是你不知到家庭是否和睦。某一天他骂你了,你更应该相信是老板被家暴了。
  • 假设3:如果老板家庭很不和睦,老板是一个由原则的人,不会迁怒至不相干的人。那么有一天老板骂你了,更有可能是你工作出现了失误。

上述假设中,要么假设某种原因的先验概率P(A)很小,要么假设原因和evidence之间的关联P(B|A)很小(似然),这些都会导致最后的后验情况不同。

P(A|B)通常被成为后验概率,即evidence在后项。

e.g. P(θ|x)通常在深度学习中被称为后验概率,表示数据是已有的结果,或者说证据,二参数就是导致数据出现的原因。

再考虑一个现实场景,假设你是一个很优秀的程序员,犯错的概率很小,有一天你的代码编译失败,你更愿意相信是编译器的问题还是你自己犯错倒置编译失败了呢?当然是你自己的问题了,因为P(编译器出现问题)这个先验概率实在是太小啦,你再优秀能和编译器比吗?除非你是写编译器的那个人,嘻嘻。

References:

https://blog.csdn.net/u011508640/article/details/72815981