平衡二叉树

定义

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

平衡二叉树

对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为logn,其各操作的时间复杂度(O(logn))同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)

而平衡二叉树在插入的时候,通过左旋/右旋的方式来保证整颗二叉树的高度不会有太大的差别,从而保证高效的查询效率,时间复杂度保持在O(logN).

左旋

Pivot节点左旋

过程:

  1. 将P节点所在右节点的左子树L接到P节点的右子树R(也就是将Y节点的b子树拼接到Pivot的右子树),修改左子树L的parent以及P节点的右子树指向
  2. 将P节点所在右节点的Parent指向P节点的Parent(将Pivot节点的父节点拼接到Y节点)
  3. 如果P为根节点的话,则替换根节点,如果P节点为父节点的左子树/右子树,则将父节点的左子树/右子树拼接原P节点的右子树R(将P节点的左子树指向Y)
  4. 将原P节点的左子树拼接P节点,并且将P节点的父节点指向替换后的P节点(将Y的左子树拼接到Pivot,并且将Pivot的父节点拼接到Y)

左旋的代码:

    /** From CLR */
    private void rotateLeft(TreeMapEntry<K,V> p) {
        if (p != null) {
            //  获取要旋转节点的右子树节点(即r为上图的Y节点)
            TreeMapEntry<K,V> r = p.right;
            //  将右子树节点的左子树拼接到要旋转节点的右子树上(即将b拼接到Pivot节点的右子树上)
            p.right = r.left;
            //  如果右子树节点的左子树节点不为空的话,则更新该节点的父节点(即将b的父节点指向Pivot节点)
            if (r.left != null)
                r.left.parent = p;
            //  修改右子树节点父节点指向要旋转节点的父节点(将Y节点的Parent指向P节点)
            r.parent = p.parent;
            //  如果要旋转的节点原来没有Parent的话,那就意味着它是根节点,则更新根节点
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
            //  如果旋转节点是Parent的左子树的话,则将旋转节点的右子树节点更新到Parent的左子树上(即将P的左子树从原来的指向pivot更新为Y)
                p.parent.left = r;
            else
            //  如果是右子树的话,则将旋转节点的右子树节点更新到Parent的右子树上
                p.parent.right = r;
            //  将旋转节点更新到该节点原右子树的左子树上(即将pivot拼接到Y的左子树上)
            r.left = p;
            //  更新旋转节点的父节点为该节点原右子树(将Pivot节点的parent更新成Y节点)
            p.parent = r;
        }
    }

右旋

Pivot节点右旋

过程:

  1. 将P节点所在左节点的右子树R接到P节点的左子树R(也就是将Y节点的c子树拼接到Pivot的左子树),修改右子树L的parent以及P节点的左子树指向
  2. 将P节点所在左节点的Parent指向P节点的Parent(将Pivot节点的父节点拼接到Y节点)
  3. 如果P为根节点的话,则替换根节点,如果P节点为父节点的左子树/右子树,则将父节点的左子树/右子树拼接原P节点的右子树R(将P的右子树指向Y)
  4. 将原P节点的右子树拼接P节点,并且将P节点的父节点指向替换后的P节点(将Y的右子树拼接到Pivot,并且将Pivot的父节点拼接到Y)
    /** From CLR */
    /** 与左旋逻辑一致,替换即可  **/
    private void rotateRight(TreeMapEntry<K,V> p) {
        if (p != null) {
            TreeMapEntry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

常见的不完全平衡二叉树

AVL树 红黑树

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1834
来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

2415
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

2603
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题19二叉树的镜像

   分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树...

2815
来自专栏Android干货

Python枚举类

Enum可以把一组相关常量定义在一个class中,且class不可变,而且成员可以直接比较。

1062
来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4....

30213
来自专栏琯琯博客

PHP二叉树(一):平衡二叉树(AVL)

平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

3369
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39判断平衡二叉树

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。 分析:所谓平衡二...

2985
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

2358
来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2608

扫码关注云+社区