二叉搜索树和平衡二叉树

  • 二叉搜索树：树中的每一个节点x的左子树中的所有结点的值都小于x的值，右子树中所有节点的值都不小于x的值

  • 插入简单，删除后的调整：

    1. 该节点只有1个儿子或没有儿子：直接让儿子代替它或不需要调整
    2. 有两个儿子：用右子树中的最小值节点替代它

  • 平衡二叉树：每个节点的左子树和右子树的高度最多差1的二叉搜索树

  • 平衡二叉树的构建与维护：只有1或2个节点肯定是平衡树。之后的插入可能会破坏平衡。对于辈分最小的违背平衡的节点，记作a。插入新节点之前，a是符合平衡要求的。插入后违背了平衡。

    1. 对a的左儿子的左子树插入
    2. 对a的左儿子的右子树插入
    3. 对a的右儿子的左子树插入
    4. 对a的右儿子的右子树插入

  • 平衡调整：

单旋转

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容