1
2
3

BBST的父节点、非祖先节点，都不会因为添加了一个节点而失衡
因为父节点可能没有子节点或者有一个子节点，再添加一个节点并不会导致平衡的坍塌
旋转都是以发现者的子树z

1
2
3

1.将发现者（A）的左节点（B）拎上来作为根节点，把发现者放下去

2.发现者左子树（B）的右子树（Br）的东西放到发现者（A）节点的左边，而发现者左子树的左子树不变

1
2
3
4
5
6

0.将发现者的左子树拎上来
1.g.left = p.right//把发现者左子树的右子树上的东西放到发现者的右子树上
2.p.right = g //把发现者放下去
3.让p成为这颗子树的根节点
4.注意维护g、p、T1//注意维护发现者、发现者的左子树及发现者的左子树的右子树
5.注意更新g、p的高度//注意更新发现者、发现者左子树的高度

1
2
3
4
5
6

0.将发现者的右子树拎上来
1.g.right = p.left//把发现者左子树的右子树上的东西放到发现者的右子树上
2.p.left = g //把发现者放下去
3.让p成为这颗子树的根节点
4.注意维护g、p、T1的parent//注意维护发现者、发现者的右树及发现者的右子树的左左子树
5.注意更新g、p的高度//注意更新发现者、发现者左子树的高度

1
2
3
4
5

1.先将发现者的左子树（B）为选择中心进行右旋转，将C转为B的根
如果麻烦节点（CI）在发现者左子树(B)的右子树(C)的左边(CI)，则将其移动到发现者(A)左子树(B)的右边(CI)
否则保持不动
2.再按照LL的方法进行调整
    BI<B<CI<C<A<Ar

1
2
3
4
5

1.先将发现者的右子树（B）为选择中心进行左旋转，将C转为B的根
如果麻烦节点（CI）在发现者右子树(B)的左子树(C)的右边(图中未画出)，则将其移动到发现者(A)右子树(B)的右子树的左边
否则保持不动
2.再按照LL的方法进行调整
  AI<A<CI<C<B<Br

1
2
3
4
5
6
7
8

 0.创建AVL树类
 1.为AVL树创建构造器 this super 的使用
 2.为AVL树创建《添加之后的操作》（afterAdd）的方法，但add操作是在bst中完成的，而afterAdd要写在AVL里，因为普通bst不需要此方法
   解决办法：在BST的add中写入protected的afterAdd方法，在AVL里override
   //@param 所添加的节点 插入位置：1.添加的是root2.添加的是普通节点
   protected void afterAdd(Node<E> node)
 3.在AVL中如何重写afterAdd(Node<E> node) 具体方法见平衡调整算法

1
2
3
4
5
6
7
8
9

 protected void afterAdd(Node<E> node)
平衡调整算法分析：
   1 明确node是哪个节点--是新添加的node 要根据此node去查找是否祖父里面有没有失衡节点
   2 找哪个失衡节点--找高度最低的失衡节点并将其修复--由此所有失衡节点都会平衡
     2.1 如果node.parent....!= null 就一直往上找（能进去这句的节点一定都是叶子节点的父亲及祖法们）
          判断找到的node是否失衡（见失衡判断算法（见平衡因此算法））
            2.1.1 如果平衡 更新高度（见更新高度算法）
          2.2.2 如果不平衡 恢复平衡 之后break（是高度最低的不平衡节点 恢复方法见恢复平衡算法 恢复完成后整颗树都再次恢复平衡 break即可）
       2.2 否则就从node开始一直往上找都找不到失衡节点，就return

1
2
3
4
5

//使用平衡因子进行失衡判断
private boolean isBalanced(Node<E> node)  -- 写在AVL中
{
        return Math.abs((AVLNode<E>node).balanceFactor()) <=1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

private int balanceFactor() --写在AVLNode中
/**
问题一：在avl树的node里设置height属性（方便查找balance factor），因为在BST里没必要维护height属性
解决办法：在avl树里新建一个node内部静态类（扩展了BT的静态内部类Node<E>）---设置为静态，切断内外关系
       并super父类的构造器
       
*/
/**
问题二：目前的add方法是在BST里创建的BT的Node，但是我们在AVL里面想要获得的是AVLNode
解决办法：在BT里面加入方法protected void creatNode(E element , Node<E> parent)
        在BST的add方法里使用该方法
        在AVL里重写该方法
        
       AVLTree<Integer> avl = new AVLTree<Integer>();
            //在调用add方法时 会调用到creatNode根据多态（avl）会调用在AVLTree里重写的createNode方法
            //afterAdd也同理
       avl.add(***);
*/
//在BT里
protected void createNode(E element , Node<E> parent)
{
  return new Node(element,parent);
}
//在AVL里 这是保证之后强转成功的关键
@override
protected void createNode(E element , Node<E> parent)
{
  return new AVLNode<E>(element, parent)
}

/**
问题三：将平衡因子算法写在哪？如何写？-- 写在AVLNode里
如何写？
1.获取左子节点的高度
2.获取右子节点的高度
3.左子节点的高度-右子节点的高度
*/


leftHeight-rightHeight

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

使用两个方法是为了看起来比较好看而起
private void updateHeight() --在AVLNode中
private void updateHeight(Node<E> node)-- 写在AVL中

  
//如果不对生成节点的高度进行更新，高度将一直保持为0，由此我们要使用高度更新算法
//每次生产一个新的节点，我们就应该对其高度进行更新因此 我们将高度更新算法写在afterAdd中 而afterAdd算法是
//套在BST的Add中的 这样，我们就可以在添加过程中及时更新AVLNode的高度（updateHeight）
//可以说，更新高度算法是非常巧妙的设计，既防止了多余的递归，由可以让每个父亲和祖父的高度都得到更新 因为在判断失衡的时候，只要不失衡都会一直往上找
   /**
   更新自己的高度 public void updateHeight()
   将AVLNode的height属性默认赋值为1，因为刚加入的节点一定为叶子节点
   算法分析:
   1.查看左子节点的高度
   2.查看右子节点的高度
   3.返回自己的高度 = Math.max(左子节点的高度，右子节点的高度) +1；
   */
  
  /**
  更新某个节点的高度
  */
 private void updateHeight(Node<E> node)
{
  (AVLNode)node.updateHeight
}
  

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

private void reBalance(Node<E> grand)
//来到这里，说明是被发现的高度最低的不平衡节点--grand
//找到高度最低的不平衡节点后，如何找他的p和n--找grand高度最高的子节点作为parent，找parent子节点中高度最高的节点做为n 因为失衡导致的 -- 使用找最高子节点算法 可以用反正法 假设grand高度最高的子节点不是parent 那么不平衡肯定就不会在parent这支上
/**
算法分析:
1.先找到grand的parent和node
2.判断是LL LR RR RL
3.分别使用LL RR算法到LL LR RR RL
4.不同情况使用L或者R算法
5.对于为什么LR RL要使用旋转两次见下图情况6 8
*/
private void reBalance(Node<E> node)
{
    //grand parent node 方便下一步操作
        AVLTree.avlNode<E> grandNode = avlNode;
        AVLTree.avlNode<E> parentNode = grandNode.tallerChild();
        AVLTree.avlNode<E> node = parentNode.tallerChild();
        //L
        if (grandNode.left == parentNode)
        {
            //LL
            if (parentNode.left == node)
            {
                clockwiseRotation(grandNode);
            }
            //LR
            if (parentNode.right == node)
            {
                unclockwiseRotation(parentNode);
                clockwiseRotation(grandNode);
            }
        }
        //R
        else
        {
            //RR
            if (parentNode.right == node)
            {
                unclockwiseRotation(grandNode);
            }
            //RL
            if (parentNode.left == node)
            {
                clockwiseRotation(parentNode);
                unclockwiseRotation(grandNode);
            }
        }

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/**
     * 恢复平衡算法
     * @param avlNode
     */
    private void reBalance2(AVLTree.avlNode<E> avlNode)
    {
        //grand parent node 方便下一步操作
        avlNode<E> grandNode = avlNode;
        avlNode<E> parentNode = grandNode.tallerChild();
        avlNode<E> node = parentNode.tallerChild();
        //L
        if (grandNode.left == parentNode)
        {
            //LL
            if (parentNode.left == node)
            {
                //根据笔记中的图写出
                Rotation(node.left,node,node.right,parentNode,parentNode.right,grandNode,grandNode.right,grandNode);
            }
            //LR
            if (parentNode.right == node)
            {
                Rotation(parentNode.left,parentNode,node.left,node,node.right,grandNode,grandNode.right,grandNode);
            }
        }
        //R
        else
        {
            //RR
            if (parentNode.right == node)
            {
                Rotation(grandNode.left,grandNode,parentNode.left,parentNode,node.left,node,node.right,grandNode);
            }
            //RL
            if (parentNode.left == node)
            {
                Rotation(grandNode.left,grandNode,node.left,node,node.right,parentNode,parentNode.right,grandNode);
            }
        }

    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

private AVLNode tallerChild()
/**
算法分析：
1.获取左子节点的高度
2.获取右子节点的高度
3.如果左子节点高度>右子节点的高度 返回左子节点
4.如果左子节点高度<右子节点的高度 返回右子节点
否则我是我父亲的什么节点 我就返回我的什么儿子给tallerChild -- 使用isleftChild、isrightChild进行判断ƒ
*/
private AVLNode tallerChild() -- 写在AVLNode里
{
              int leftHeight = left == null? 0 : ((avlNode<E>)left).height;
            int rightHeight = right == null? 0 : ((avlNode<E>)right).height;
            if (leftHeight>rightHeight) return (avlNode<E>) left;
            if (leftHeight<rightHeight) return (avlNode<E>) right;
            //如果两边高度一样高 我是我父亲的什么节点，我就返回我的什么儿子给tallerchild
            return (avlNode<E>) (isleftChild()? left : right);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/**

*/
protected boolean isleftChild()
{
        return parent!=null && this = this.parent.left;
}

protected boolean isrightChild()
{
        return parent!=null && this = this.parent.right;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

private void rotate(Node<E>a,Node<E>b,Node<E>c,
                   Node<E>d,
                   Node<E>e,Node<E>f,Node<E>g
                   Node<E>r)//r为该子树中根节点是谁b or f
/**
算法分析：
让d成为子树的根节点
1.更新d的parent属性
2.更新r的父亲的left or right属性
a-b-c
3.更新b的left属性 ，并更新a的parent属性 -- a可能为空
4.更新b的right属性，并更新c的parent属性 --c可能为空
5.更新b的高度
e-f-g
6.更新f的left属性，并更新e的parent属性
7.更新f的right属性，并更新g的right属性
8.更新f的高度
b-d-f
9.更新d的left属性，并更新b的parent属性
10.更新d的right属性，并更新f的parent属性
11.更新d的高度
*/