数据结构算法--017：平衡二叉树

1. 概述

如果是已经按照升序排列的数据，此时使用⼆叉排序树，就会出现一些极端情况

例如：将[36, 37, 47, 51, 58, 62, 73, 88, 93, 99]使用二叉排序树结构存储：

• 此时的二叉排序树极为不平衡，生成为一棵右斜树，所有的左孩子都为空

在这种情况下，查询效率会变得非常低下。我们需要将⼆叉排序树进行优化，使它的结构变得平衡，而优化后的树则称之为平衡⼆叉树

1.1 名词解释

平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree）：它是⼆叉排序树的一种，其中每⼀个结点的左⼦树和右⼦树的⾼度差最多等于1。它同样具备了⼆叉排序树的特性

平衡⼆叉树由两位俄罗斯数学家G.M.Adelson - Velskii和E.M.Landis共同发明，是⼀种解决平衡⼆叉树的算法。也称之为AVL树

平衡二叉树是指我们在设计一棵树的时候，让它的结构达到高度平衡

⾼度平衡的定义：要么它是⼀颗空树，要么它的左⼦树和右⼦树都是平衡⼆叉树。且左⼦树和右⼦树的深度之差的绝对值不超过1。我们将⼆叉树上结点的左⼦树深度减去右⼦树深度的值，称之为平衡因⼦BF（Balance Factr）

示例1：

• 图1是平衡二叉树，因为左子树深度减去右子树深度等于0

• 图2不是平衡二叉树，虽然深度之差也是0，但它不符合二叉排序树的特性。因为59 > 58，应该为58的右⼦树

示例2：

• 不是平衡二叉树，因为58结点的左子树深度为3，而右子树深度为0，此时58结点的BF为3

示例3：

• 是平衡二叉树，因为所有结点的左子树与右子树的深度之差的绝对值不超过1，同时也符合二叉排序树的特性

1.2 最小不平衡树

构建一颗平衡二叉树，插入的逻辑是最复杂的。而它的查找与删除操作，和普通的二叉排序树没有什么区别

想要构建一颗平衡二叉树，需要先找到树结构中的最小不平衡树。即：距离插⼊点最近的，且平衡因⼦的绝对值⼤于1的结点为根的⼦树

示例：

• 假设新插入的结点为37，结点37属于结点35的右子树，此时结点35的BF为-1，它不符合最小不平衡树。结点47的BF为1，同样不符合最小不平衡树。而结点58，左子树深度为3，右子树深度为1，它的BF为2，所以结点58为最小不平衡树

1.3 基本思想

平衡二叉树构建的基本思想：在构建⼆叉排序树的过程中，每当插⼊⼀个结点时，先检查是否因插⼊⽽破坏了树的平衡性

若是，则找到最⼩不平衡⼦树。在保持⼆叉排序树特性的前提下，调整最⼩不平衡⼦树中各结点之间的链接关系，进⾏相应的旋转，使之成为新的平衡⼦树

2. 模拟平衡树的构建

假设：数组a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8}，它所生成的二叉排序树极为不平衡

为了提高查找效率，我们希望将它优化成一棵平衡二叉树

2.1 结点插入

【步骤一】插入结点3、2、1的过程，当我们插入结点3和结点2，此时并没有失衡。当插入结点1后，它会导致结点3的平衡因子为2，这时结点3就成为了最小不平衡树

• 将图1优化为图2，将结点3进行右旋即可。优化后结点2成为根节点，此时结点2的平衡因子为0

【步骤二】插入结点4的过程，结点4会成为结点3的右⼦树，但此时并没有失衡，所以不需要优化

【步骤三】插入结点5的过程，结点5会成为结点4的右⼦树。此时结点3的平衡因子为-2，结点3成为了最小不平衡树

• 将图4优化为图5，将结点3进行左旋即可。优化后结点4成为根节点，此时结点4的平衡因子为0

【步骤四】插入结点6的过程，结点6会成为结点5的右⼦树。此时结点2的平衡因子为-2，结点2成为了最小不平衡树

• 将图6优化为图7，将结点2进行左旋即可。优化后结点4成为根节点，此时结点4的平衡因子为0。之前结点3为结点4的左子树，优化后变为结点2的右子树

【步骤五】插入结点7的过程，结点7会成为结点6的右⼦树。此时结点5的平衡因子为-2，结点5成为了最小不平衡树

• 将图8优化为图9，将结点5进行左旋即可。优化后结点6成为根节点，此时结点6的平衡因子为0

【步骤六】插入结点10的过程，结点10会成为结点7的右⼦树，但此时并没有失衡，所以不需要优化

【步骤七】插入结点9的过程，结点9会成为结点10的左⼦树。此时结点7的平衡因子为-2，结点7成为了最小不平衡树

将图11优化为图12，将结点7进行右旋即可。但是它会打破二叉排序树的特性，由于结点9⽐结点10⼩，所以不能成为结点10的右⼦树

• 导致左旋无法得到正确结果的原因是，结点7的BF为-2，而结点10的BF为1，二者之间是互异的。当遇到一正一负符号不统一的情况，单纯靠左旋或右旋，都无法得到正确的结果。此时，我们应对结点7进行双旋处理

双旋的目的：第一次旋转，先将符号统一。既然结点10的BF为正数，我们先对结点10进行一次右旋，得到以下结构的二叉排序树

经过第一次旋转后，结点7和结点9的BF都统一成负数，我们可对结点7进行第二次旋转

• 将图13优化为图14，将结点7进行左旋即可。优化后结点9成为根节点，此时结点9的平衡因子为0

【步骤八】插入结点8的过程，结点8会成为结点7的右⼦树。此时结点6的平衡因子为-2，结点6成为了最小不平衡树

由于结点9的平衡因子为1，它与结点6的符号不统一，我们应对结点6进行双旋处理

第一次旋转，先将符号统一。既然结点9的BF为正数，我们先对结点9进行一次右旋

• 将图15优化为图16，优化后结点7为结点6的右子树，而结点8以前是结点7的右子树，此时只能作为结点9的左子树

经过第一次旋转后，结点9的BF变得平衡，我们可对结点6进行第二次旋转

• 将图16优化为图17，将结点6进行左旋即可。此时我们将所有结点全部插入，最终得到一棵优化后的平衡二叉树

2.2 旋转方式

旋转方式和最小不平衡树中结点的平衡因子有关：

• 如果都为正数，则对其进行右旋

• 如果都为负数，则对其进行左旋

• 如果符号不统一，则对其进行双旋

3. 平衡二叉树的实现

3.1 数据结构

平衡二叉树的结点结构定义：

class SelfBalancingTree {
    fileprivate class BiTNode {
        var data : Int;
        var bf : Int;
        var leftChild : BiTNode?;
        var rightChild : BiTNode?;
        init(data : Int){
            self.data = data;
            self.bf = 0;
            self.leftChild = nil;
            self.rightChild = nil;
        }
        deinit {
            print("结点已释放：\(self.data)")
        }
    }
}

• data：结点数据

• bf：平衡因子

• leftChild：左孩⼦指针

• rightChild：右孩⼦指针

3.2 右旋的实现

如果平衡因子都为正数，将其进行右旋操作

3.2.1 思路分析

插⼊N前的平衡⼆叉树：

插⼊N后平衡性被打破，此时p为最小不平衡树的根节点。为了优化它的平衡性，将其进行右旋操作：

• 让结点L的右子树，成为结点p的左子树

• 让结点p成为结点L的右子树

• 结点L成为二叉排序树的新根节点

经过右旋优化之后的平衡二叉树：

3.2.2 代码实现

class SelfBalancingTree {

    fileprivate func rightRotate(node : inout BiTNode) {

        let p = node;
        let l = node.leftChild;
        let lr = l?.rightChild;

        p.leftChild = lr;
        l?.rightChild = p;
        node = l!;
    }
}

3.3 左旋的实现

如果平衡因子都为负数，将其进行左旋操作

3.3.1 思路分析

插⼊N前的平衡⼆叉树：

插⼊N后平衡性被打破，此时p为最小不平衡树的根节点。为了优化它的平衡性，将其进行左旋操作：

• 让结点R的左子树，成为结点p的右子树

• 让结点p成为结点R的左子树

• 结点R成为二叉排序树的新根节点

经过左旋优化之后的平衡二叉树：

3.3.2 代码实现

class SelfBalancingTree {

    fileprivate func leftRotate(node : inout BiTNode) {

        let p = node;
        let r = node.rightChild;
        let rl = r?.leftChild;

        p.rightChild = rl;
        r?.leftChild = p;
        node = r!;
    }
}

3.4 左子树失衡

判断失衡不会直接比较bf值，而是给出以下三个常量：

• LH：左⾼

• EH：等⾼

• RH：右⾼

当遇到LH时，意味着bf值为负数，也就是左子树高，我们需要进行右旋。而右⾼与之相反，我们需要进行左旋。通过三个常量，表示二叉排序树的旋转状态

左失衡分为两种情况：

• 结点的符号统一，只需要进行一次右旋即可

• 结点的符号不统一，需要进行双向处理

3.4.1 符号统一

插⼊结点1后左⼦树失衡

• 判断T的BF值与L的BF值是否是符号相同

• 将T的BF值与L的BF值更新为平衡后的BF值，等于0

• 将最⼩不平衡⼦树T进⾏右旋

3.4.2 符号不统一

插⼊结点N导致平衡性被打破，左⼦树失衡。由于符号不统一，需要进行双旋处理

• 判断结点T的BF值与L的BF值是否是同符合

  • 根结点T为正（LH），而左⼦树L为负（RH），所以要进⾏双旋处理

• 获取左⼦树L的右⼦树Lr，修改T与左孩⼦L的BF值，⽬的是将符号改为⼀致

  • 如果Lr.BF为正（LH）时，将根结点T的BF值改为RH，L的BF值改为EH

  • 如果Lr.BF为0（EH）时，将根结点T与左⼦树L的BF值都改为EH

  • 如果Lr.BF为负（RH）时，将根结点T的BF值改为EH，L的BF值改为LH

• 将Lr的BF值改为0（EH）

• 对T的左⼦树进⾏左旋处理

• 对T做右旋处理

2.4.3 代码实现

class SelfBalancingTree {

    // 左平衡树失衡处理
    fileprivate func leftBalance(node : inout BiTNode) {

        let t = node;
        let l = t.leftChild!;

        // 当左平衡树失衡时，T的BF值一定为LH
        // 判断T的BF值与L的BF值是否是符号相同
        switch(l.bf){
            case TreeBalance.LH:
                // 符号统一，进行右旋即可
                // 将T的BF值与L的BF值更新为平衡后的BF值，等于0
                t.bf = TreeBalance.EH;
                l.bf = TreeBalance.EH;
                // 将最⼩不平衡⼦树T进⾏右旋
                rightRotate(node: &node);
                break;
            case TreeBalance.RH:
                // 符号不统一，进行双旋操作
                // 获取左⼦树L的右⼦树Lr，修改T与左孩⼦L的BF值，⽬的是将符号改为⼀致
                let lr = l.rightChild!;
                switch(lr.bf){
                    case TreeBalance.LH:
                        // 将根结点T的BF值改为RH
                        t.bf = TreeBalance.RH;
                        // 将L的BF值改为EH
                        l.bf = TreeBalance.EH;
                        break;
                    case TreeBalance.EH:
                        // 将根结点T与左⼦树L的BF值都改为EH
                        t.bf = TreeBalance.EH;
                        l.bf = TreeBalance.EH;
                        break;
                    default:
                        // 将根结点T的BF值改为EH
                        t.bf = TreeBalance.EH;
                        // 将L的BF值改为LH
                        l.bf = TreeBalance.LH;
                        break;
                }

                lr.bf = TreeBalance.EH;
                // 对T的左⼦树进⾏左旋处理
                leftRotate(node: &node.leftChild!);
                // 对T做右旋处理
                rightRotate(node: &node);
                break;
            default:
                break;
        }
    }
}

3.5 右子树失衡

右子树失衡和左子树失衡的逻辑一致，区别在于修改的为结点T的右孩子

3.5.1 符号统一

符号统一时，失衡右⼦树进⾏左旋即可达到平衡

• 判断最⼩不平衡⼦树T的BF值与根结点T的右⼦树R的BF值符合是否⼀致（都为负数）

• 将T的BF值与R的BF值更新为平衡后的BF值，等于0

• 将最⼩不平衡⼦树T进⾏左旋

3.5.2 符号不统一

符号不统一时，失衡右⼦树需要进⾏双旋才可达到平衡

• 判断T的BF值与R的BF值是否是同符合

  • 根结点T为负（RH），右⼦树R为正（LH），所以要进⾏双旋处理

• 获取右⼦树R的左⼦树RL，修改T与右孩⼦R的BF值，⽬的是将符号改为⼀致

  • 如果RL.BF为负（RH）时，将根结点T的BF值改为LH，R的BF值改为EH

  • 如果RL.BF为0（EH）时，将根结点T与左⼦树R的BF值都改为EH

  • 如果RL.BF为正（LH）时，将根结点T的BF值改为EH，R的BF值改为RH

• 将RL的BF值改为0（EH）

• 对T的右⼦树进⾏右旋处理

• 对T做左旋处理

3.5.3 代码实现

class SelfBalancingTree {

    // 右平衡树失衡处理
    fileprivate func rightBalance(node : inout BiTNode) {

        let t = node;
        let r = t.rightChild!;

        // 当右平衡树失衡时，T的BF值一定为RH
        // 判断T的BF值与R的BF值是否是符号相同
        switch(r.bf){
            case TreeBalance.RH:
                // 符号统一，进行左旋即可
                // 将T的BF值与R的BF值更新为平衡后的BF值，等于0
                t.bf = TreeBalance.EH;
                r.bf = TreeBalance.EH;
                // 将最⼩不平衡⼦树T进⾏左旋
                leftRotate(node: &node);
                break;
            case TreeBalance.LH:
                // 符号不统一，进行双旋操作
                // 获取右⼦树R的左⼦树rl，修改T与右孩⼦R的BF值，⽬的是将符号改为⼀致
                let rl = r.leftChild!;
                switch(rl.bf){
                    case TreeBalance.RH:
                        // 将根结点T的BF值改为LH
                        t.bf = TreeBalance.LH;
                        // 将R的BF值改为EH
                        r.bf = TreeBalance.EH;
                        break;
                    case TreeBalance.EH:
                        // 将根结点T与右⼦树R的BF值都改为EH
                        t.bf = TreeBalance.EH;
                        r.bf = TreeBalance.EH;
                        break;
                    default:
                        // 将根结点T的BF值改为EH
                        t.bf = TreeBalance.EH;
                        // 将R的BF值改为RH
                        r.bf = TreeBalance.RH;
                        break;
                }

                rl.bf = TreeBalance.EH;
                // 对T的左⼦树进⾏左旋处理
                rightRotate(node: &node.rightChild!);
                // 对T做右旋处理
                leftRotate(node: &node);
                break;
            default:
                break;
        }
    }
}

3.6 插入结点

若在平衡的⼆叉排序树T中不存在和e有相同关键字的结点，则插⼊⼀个数据元素为e的新结点，并返回1，否则返回0

若因插⼊⽽使⼆叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T⻓⾼与否

3.6.1 思路分析

• 如果T为空时，则创建⼀个新结点

• 如果T不为空，判断是否存在相同的结点。如果⼆叉树中存在相同结点，则不需要插⼊

• 如果新结点值e⼩于T的根结点值，则在T的左⼦树查找

• 如果能在左⼦树中查找到，则不插⼊进去，返回False。如果没有找到，则插⼊

• 插⼊成功taller为TRUE，说明新结点e已经插⼊进去，此时需要判断T的平衡因⼦

• 如果平衡因⼦是1，则说明左⼦树⾼于右⼦树，那么需要调⽤leftBalance进⾏左平衡旋转处理

• 如果为0或者-1，则说明新插⼊的结点没有让整颗⼆叉排序树失去平衡性，只需要修改BF值即可

• 如果新结点值e⼤于T的根结点值，则在T的右⼦树查找

• 如果能在右⼦树中查找到，则不插⼊进去，返回False。如果没有找到，则插⼊

• 插⼊成功taller为TRUE，说明新结点e已经插⼊进去，此时需要判断T的平衡因⼦

• 如果平衡因⼦是-1，则说明右⼦树⾼于左⼦树，那么需要调⽤RightBalance进⾏右平衡旋转处理

• 如果为0或者1，则说明新插⼊的结点没有让整颗⼆叉排序树失去平衡性，只需要修改BF值即可

3.6.2 代码实现

实现结点的插入方法：

class SelfBalancingTree {

    func insert(key : Int) -> Bool{
        return insertNode(node : &_root, key: key, taller: &taller);
    }

    fileprivate func insertNode(node : inout BiTNode?, key : Int, taller : inout Bool) -> Bool {

        // 判断当前结点是否存在
        if(node == nil){
            // 不存在，创建新结点
            node = BiTNode(data: key);
            // 二叉树⻓⾼
            taller = true;
            // 返回结点插入成功
            return true;
        }

        // 判断新结点在二叉树中是否已存在
        if(node!.data == key){
            // 已存在，不插入，二叉树没有长高
            taller = false;
            // 返回结点插入失败
            return false;
        }

        // 新结点小于当前结点
        if(key < node!.data) {

            // 将新结点插入当前结点的左孩子
            let result = insertNode(node: &node!.leftChild, key: key, taller: &taller);

            // 判断是否插入成功
            if(!result){
                // 插入失败，直接返回结果
                return result;
            }

            // 判断二叉树是否因为新插入结点而长高
            if(!taller){
                // 没有长高，直接返回结果
                return result;
            }

            // 当二叉树长高，判断父节点的平衡因子
            switch(node!.bf){
                case TreeBalance.LH:
                    // 父结点左子树高，向左孩子插入新结点，会导致失衡，进行左平衡树失衡处理
                    leftBalance(node: &node!);
                    // 处理后二叉树恢复平衡，将标记修正为没有长高
                    taller = false;
                    break;
                case TreeBalance.RH:
                    // 父结点右子树高，向左孩子插入新结点，父结点变为平衡
                    node?.bf = TreeBalance.EH;
                    // 二叉树没有长高
                    taller = false;
                    break;
                default:
                    // 父结点平衡，向左孩子插入新结点，父结点变为左子树高
                    node?.bf = TreeBalance.LH;
                    // 二叉树长高
                    taller = true;
                    break;
            }
        }
        else {

            // 将新结点插入当前结点的右孩子
            let result = insertNode(node: &node!.rightChild, key: key, taller: &taller);

            // 判断是否插入成功
            if(!result){
                // 插入失败，直接返回结果
                return result;
            }

            // 判断二叉树是否因为新插入结点而长高
            if(!taller){
                // 没有长高，直接返回结果
                return result;
            }

            // 当二叉树长高，判断父节点的平衡因子
            switch(node!.bf){
                case TreeBalance.RH:
                    // 父结点右子树高，向右孩子插入新结点，会导致失衡，进行右平衡树失衡处理
                    rightBalance(node: &node!);
                    // 处理后二叉树恢复平衡，将标记修正为没有长高
                    taller = false;
                    break;
                case TreeBalance.LH:
                    // 父结点左子树高，向右孩子插入新结点，父结点变为平衡
                    node?.bf = TreeBalance.EH;
                    // 二叉树没有长高
                    taller = false;
                    break;
                default:
                    // 父结点平衡，向右孩子插入新结点，父结点变为右子树高
                    node?.bf = TreeBalance.RH;
                    // 二叉树长高
                    taller = true;
                    break;
            }
        }

        // 返回结点插入成功
        return true;
    }
}

实现平衡二叉树中的元素查找：

class SelfBalancingTree {

    func search(key : Int) -> Bool {
        var target : BiTNode? = _root;
        let result = search(key: key, parent: nil, target: &target);
        return result;
    }

    fileprivate func search(key : Int, parent : BiTNode?, target : inout BiTNode?) -> Bool {

        // 判断当前结点是否为空
        if(target == nil){
            // 结点为空，表示未找到，将父节点赋值给目标结点
            target = parent;
            // 返回查找失败
            return false;
        }

        // 判断key是否等于当前结点
        if(key == target!.data){
            // 相等，表示当前目标结点就是要查找的结点，返回查找成功
            return true;
        }

        let parent = target;

        // 判断key是否小于当前结点
        if(key < target!.data){
            // 小于，在当前结点的左子树中查找
            target = target?.leftChild;
            return search(key: key, parent: parent, target: &target);
        }

        // 否则大于，在当前结点的右子树中查找
        target = target?.rightChild;
        return search(key: key, parent: parent, target: &target);
    }
}

总结

概述：

• 平衡二叉树：是⼆叉排序树的一种，其中每⼀个结点的左⼦树和右⼦树的⾼度差最多等于1。它同样具备了⼆叉排序树的特性

• 平衡二叉树是指我们在设计一棵树的时候，让它的结构达到高度平衡

• ⾼度平衡的定义：要么它是⼀颗空树，要么它的左⼦树和右⼦树都是平衡⼆叉树。且左⼦树和右⼦树的深度之差的绝对值不超过1。我们将⼆叉树上结点的左⼦树深度减去右⼦树深度的值，称之为平衡因⼦BF

• 最小不平衡树：想要构建一颗平衡二叉树，需要先找到树结构中的最小不平衡树。即：距离插⼊点最近的，且平衡因⼦的绝对值⼤于1的结点为根的⼦树

• 平衡二叉树构建的基本思想：在构建⼆叉排序树的过程中，每当插⼊⼀个结点时，先检查是否因插⼊⽽破坏了树的平衡性。若是，则找到最⼩不平衡⼦树。在保持⼆叉排序树特性的前提下，调整最⼩不平衡⼦树中各结点之间的链接关系，进⾏相应的旋转，使之成为新的平衡⼦树

旋转方式和最小不平衡树中结点的平衡因子有关：

• 如果都为正数，则对其进行右旋

• 如果都为负数，则对其进行左旋

• 如果符号不统一，则对其进行双旋

平衡二叉树的结点结构定义：

• data：结点数据

• bf：平衡因子

• leftChild：左孩⼦指针

• rightChild：右孩⼦指针

右旋的实现：

• 让结点L的右子树，成为结点p的左子树

• 让结点p成为结点L的右子树

• 结点L成为二叉排序树的新根节点

左旋的实现：

• 让结点R的左子树，成为结点p的右子树

• 让结点p成为结点R的左子树

• 结点R成为二叉排序树的新根节点

子树的失衡判断：

• 判断失衡不会直接比较bf值，而是给出以下三个常量：

  • LH：左⾼

  • EH：等⾼

  • RH：右⾼

左子树失衡：

• 符号统一：

  • 判断T的BF值与L的BF值是否是符号相同

  • 将T的BF值与L的BF值更新为平衡后的BF值，等于0

  • 将最⼩不平衡⼦树T进⾏右旋

• 符号不统一：

  • 判断结点T的BF值与L的BF值是否是同符合

    • 根结点T为正（LH），而左⼦树L为负（RH），所以要进⾏双旋处理

  • 获取左⼦树L的右⼦树Lr，修改T与左孩⼦L的BF值，⽬的是将符号改为⼀致

    • 如果Lr.BF为正（LH）时，将根结点T的BF值改为RH，L的BF值改为EH

    • 如果Lr.BF为0（EH）时，将根结点T与左⼦树L的BF值都改为EH

    • 如果Lr.BF为负（RH）时，将根结点T的BF值改为EH，L的BF值改为LH

  • 将Lr的BF值改为0（EH）

  • 对T的左⼦树进⾏左旋处理

  • 对T做右旋处理

右子树失衡：

• 符号统一：

  • 判断最⼩不平衡⼦树T的BF值与根结点T的右⼦树R的BF值符合是否⼀致（都为负数）

  • 将T的BF值与R的BF值更新为平衡后的BF值，等于0

  • 将最⼩不平衡⼦树T进⾏左旋

• 符号不统一：

  • 判断T的BF值与R的BF值是否是同符合

    • 根结点T为负（RH），右⼦树R为正（LH），所以要进⾏双旋处理

  • 获取右⼦树R的左⼦树RL，修改T与右孩⼦R的BF值，⽬的是将符号改为⼀致

    • 如果RL.BF为负（RH）时，将根结点T的BF值改为LH，R的BF值改为EH

    • 如果RL.BF为0（EH）时，将根结点T与左⼦树R的BF值都改为EH

    • 如果RL.BF为正（LH）时，将根结点T的BF值改为EH，R的BF值改为RH

  • 将RL的BF值改为0（EH）

  • 对T的右⼦树进⾏右旋处理

  • 对T做左旋处理

插入结点：

• 如果T为空时，则创建⼀个新结点

• 如果T不为空，判断是否存在相同的结点。如果⼆叉树中存在相同结点，则不需要插⼊

• 如果新结点值e⼩于T的根结点值，则在T的左⼦树查找

• 如果能在左⼦树中查找到，则不插⼊进去，返回False。如果没有找到，则插⼊

• 插⼊成功taller为TRUE，说明新结点e已经插⼊进去，此时需要判断T的平衡因⼦

• 如果平衡因⼦是1，则说明左⼦树⾼于右⼦树，那么需要调⽤leftBalance进⾏左平衡旋转处理

• 如果为0或者-1，则说明新插⼊的结点没有让整颗⼆叉排序树失去平衡性，只需要修改BF值即可

• 如果新结点值e⼤于T的根结点值，则在T的右⼦树查找

• 如果能在右⼦树中查找到，则不插⼊进去，返回False。如果没有找到，则插⼊

• 插⼊成功taller为TRUE，说明新结点e已经插⼊进去，此时需要判断T的平衡因⼦

• 如果平衡因⼦是-1，则说明右⼦树⾼于左⼦树，那么需要调⽤RightBalance进⾏右平衡旋转处理

• 如果为0或者1，则说明新插⼊的结点没有让整颗⼆叉排序树失去平衡性，只需要修改BF值即可