首页算法

    我是基于ChatGPT-turbo-3.5实现的AI助手，在此网站上负责整理和概括文章

    文章总结了二叉搜索树、红黑树、顺序统计树和区间树的相关概念和性质。二叉搜索树中包括前趋、后继、祖先等概念，操作的时间复杂度与树的高度相关。红黑树具有四条性质，插入、删除操作需要修复以保持性质。顺序统计树中插入、删除操作时间复杂度为O(lg(n))。区间树通过区间三分法来判断区间的位置关系。

    ---

    # 1 二叉搜索树

    名称 概念
    前趋 比当前节点小的最大节点
    后继 比当前节点大的最小节点
    祖先 该节点的父节点及以上

    定理：

    • 如果 x 是一个含有 n 个结点的子树的根，那么调用 INORDER-TREE-WALK (中序遍历) 需要时间θ(n)\theta(n)

    • 在一棵高度为 h 的二叉搜索树上，动态集合上的操作 SEARCH,MINIMUM,MAXMUN,SUCCESSOR (后继),PREDECESSOR（前趋）需要时间 O (h)

    • 在一棵高度为 h 的二叉搜索树上，实现动态集合 INSERT（插入）和 DELETE（删除）操作需要时间 O (h)

    # 2 红黑树

    红黑树四条性质：（红黑树中可以没有黑色，但有红色必须满足其性质）
    1. 每个结点为红色或黑色。
    2. 根节点和叶结点都是黑色的。
    3. 每个红色节点的叶结点都是黑色的。
    4. 从一个节点 X 到 X 的子孙叶结点，所有到子孙叶结点的路径，都有相等的黑结点数。
    5. 红色结点的儿子必定是黑的。

    一棵有 n 个内结点的红黑树高度至多为2lg⁡（n+1）2\lg（_{}{n+1}）

    结点的秩是树中小于或等于该结点的结点数量。

    从某个结点 x 出发（不含该结点），到达叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高，记为 bh (x)。

    旋转操作：
    旋转操作图示

    插入或删除后的修复操作（满足所有红黑树性质）：
    修复操作图示

    # 3 顺序统计树

    对于一颗含有 n 个结点的顺序统计树，插入，删除操作，包括维护 size 域，都需要 O (lg (n)) 时间。

    # 4 区间树

    区间三分法
    1. 完全位于左子树的区间。已知区间的右端点小于当前结点区间的左端点。
    2. 与当前结点区间重叠的区间。已知区间与当前结点区间有交集。
    3. 完全位于右子树的区间。已知区间的左端点大于当前结点区间的右端点。