CLRS滑稽导论 (1) : AVL树

  在二叉树的学习中,我们会接触到很多不同的树。其中,用得最为普遍的,是二叉搜索树。而为提升二叉树搜索的效率,又引入自平衡二叉树的概念。自平衡二叉搜索树是指通过处理可以实现子树相对平衡,即不极端地偏向一边的二叉搜索树。由于相对平衡的特性,树可以实现查询、插入、删除操作在时间上的优化。

Red Black Tree (Draft)

本文处于草稿中。。。

  1. 定义:红黑树利用特征标记决定高度的自平衡二叉搜索树,具有额外的数据决定其节点为黑或红节点。每一条从单一节点到叶子结点的路径都有相同数目的黑色节点。利用此特性,保持树高为$O(lg\ n)$。

    pre:平衡树:空树或其左右两个子树高度差相对小的二叉搜索树。

    正确性特性:

    1. 节点是红色或黑色。
    2. 根是黑色。
    3. 所有叶子都是黑色(叶子是NIL节点)。
    4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
    5. 从任一节点到其每个叶子的所有简单路径)都包含相同数目的黑色节点。
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×