red-black-tree-遭不住呀

#二叉树

####什么是二叉树?

符合二叉的树形结构,一个父亲结点有两个子节点.

####什么是二叉搜索树?

左结点小于父亲结点,右结点大于父亲结点,没有键值相等的节点.

####为什么要有二叉搜索树,二叉搜索树相对于链表,散列表的效率如何?

二叉搜索树的搜索效率=O(h).(h是这颗树的高度)

因为自顶向下直到找到对应结点都是一条简单路径,树的高度是一个上限.

这里不重点讨论二叉搜索树,只简要提及一些性质,有兴趣可以自己完成一个二叉搜索树的插入删除和搜索.

链表的搜索是线性的,但是插入删除都是常数(这里是指拥有某个节点的引用时,不包括查找某个结点需要的搜索时间,O(1)删节点我还被鄙视过,5555).

而二叉树的删除和插入除了搜索本身之外还有调整平衡,不能达到常数级别.

另外再讨论一下散列表,这也是面试的时候经常问的一个问题,散列表在效果哈希函数效果比较好的时候搜索是常数的.

但是并不能有序,而二叉搜索树是可以有序的,比如寻找0到5000之间的结点,二叉树只要找一头一尾,之间的中序遍历,而散列表则要访问5000次,所以不能够体现其优点,另外在开销上,散列表的空间开销更大.

####为什么希望二叉搜索树平衡?

因为如果二叉搜索树不平衡的话,很容易影响查找效率,特殊情况直接退化成链表.

#红黑树

红黑树的性质:

  • 性质1:节点是红色或黑色.
  • 性质2:根是黑色.
  • 性质3:所有叶子都是黑色(叶子是NIL节点).
  • 性质4:每个红色节点必须有两个黑色的子节点.(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 性质5:从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点.

这次讨论的是一个相对来说比较特殊的一种数据结构红黑树.红黑树是平衡树的一种,因为平凡的二叉搜索树没有一个稳定的搜索效率,所以需要一个每个叶子结点高度能够相近的一种数据结构,达到平衡的效果.

而这里提到的红黑树能够做到非常好的平衡,下面要提到的红黑树是2008年的一篇论文[1]对红黑树的改进,使用递归就能实现,比非递归的更好实现.

###引入23树

23树可以完美平衡的树结构.

2-node,3-node,4-node.

板书演示,23树的平衡,内容参考纸质板书.

###由23树转化为红黑树

稿源:yueyue.gao (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 后端存储 » red-black-tree-遭不住呀

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录