平衡二叉树(avl)

概念

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

高度和平衡因子

如下就是一棵AVL树：

高度：规定叶子节点的高度为1。非叶子节点，取左右子树中高度最高的节点高度值并加一(+1其实加的是自身的高度)
平衡因子：左右子树的高度差。

高度计算举例：

如5这个节点的高度为: 4节点的高度+1,4是叶子节点则4节点的高度为1，而+1其实是5自身的高度即5节点高度为： 1+1 = 2，所以5这个节点的高度为2。
再如8这个节点的高度为:左右子树高度最高的值+1，8的左节点高度为2，右节点高度为1，左右节点高度最高为2 即5节点的高度为：2 + 1 = 3
平衡因子计算举例：
4节点的平衡因子为0，因为该节点没有左右子树。
5节点的平衡因子为1，左右子树高度值相减取绝对值。

实现一个AVLTree

成员变量如下:

public class AVLTree<K extends Comparable<K>, V> {

    private class Node {
        public K key;
        public V value;
        public Node left, right;
        // 节点高度
        public int height;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }
    }

    private Node root;
    private int size;

    public AVLTree() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 计算节点高度
     *
     * @param node
     * @return
     */
    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }
}

如上定义了一个Node类，主要有树的节点的key，value，以及左右子树，还有此节点的高度。

接下来向节点中添加元素：


/**
  * 向以node为根的二分搜索树中插入元素(key, value) ，递归
  * 返回插入新节点后二分搜索树的根
  *
  * @param node
  * @param key
  * @param value
  * @return
  */
  private Node add(Node node, K key, V value) {
      if (node == null) {
          size++;
          return new Node(key, value);
      }

      if (key.compareTo(node.key) < 0) {
          // 当要添加的节点的值小于当前节点时向左子树中添加节点
          node.left = add(node.left, key, value);
      } else if (key.compareTo(node.key) > 0) {
          // 当要添加的节点的值大于当前节点时向右子树中添加节点
          node.right = add(node.right, key, value);
      } else {
          // 当值相等时，替换原有值
          node.value = value;
      }

      // 更新height
      node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

      // 计算平衡因子
      int balanceFactor = getBalanceFactor(node);
      // 当该节点的平衡因子大于1时 && 该节点的左子树的平衡因子大于1时 此时需要做右旋转来保证左右子树的高度差不超过1
      if (Math.abs(balanceFactor) > 1 && Math.abs(getBalanceFactor(node.left)) > 0) {
          return rightRotate(node);
      }
      // 判断是否需要右旋转，当该节点的平衡因子大于1时 && 该节点的右子树的平衡因子大于1时，此时需要左旋转来保证左右子树的高度差不超过1
      if (Math.abs(balanceFactor) > 1 && Math.abs(getBalanceFactor(node.right)) > 0) {
          return leftRotate(node);
      }
      return node;
  }

左旋转与右旋转

左旋转和右旋转都需要满足一个条件：当左右子树高度差超过1时，即此节点的平衡因子大于1。

如下此棵树，当添加T1 或T2节点时就会满足旋转的条件。这里T1和T2同时存在是为了看起来整棵树对称些，其实当Z节点添加任意一个子节点时，就满足了需要旋转的条件了。

当Z添加任意子节点后，会计算层层往上计算节点的高度值：

Z节点插入T节点后高度值变为2，X节点高度值变为3，Y节点高度变为4，Y节点的平衡因子为：X高度-T4高度 = 2
此时已不满足一棵平衡二叉树的定义，故需要进行旋转操作。
当满足旋转条件后还需要判断要做哪种旋转，如果是y的右子树的节点的平衡因子大于0，证明其是右子树高度过高导致的不平衡，故需要进行左旋转，如果是y的左子树的节点的平衡因子大于0，证明其是左子树的高度过高导致的不平衡，故需要做右旋转，下面这棵树是右子树的节点X的平衡因子大于0 故需要做左旋转。

左旋转的过程：


      y                              X
    /   \                          /   \
   T4    X         左旋转          y     Z
        / \      =========>      / \   /  \
       T3  Z                    T4 T3 T1  T2
          / \
         T1  T2
过程：
1. Node X = y.right;
2. Node T3 = X.left;
3. X.left = y;
4. y.right = T3;

旋转后为何还能保证是一棵二叉搜索树？
旋转前：  T4 < Y < T3 < X < T1 < Z < T2
旋转后：  T4 < Y < T3 < X < T1 < Z < T2  节点之间的大小关系不会变化，保证了其还是一个二叉搜索树

旋转后为何可以保证其是一个平衡二叉树（AVL树）？
旋转前后 T1，T2, T3, T4 都是叶子节点，前后高度值未变化，都是1, 只有X和Y节点的高度变化了，
而每次旋转的过程都是在添加元素后，递归的一层一层往上查找的不满足平衡的节点，
保证了添加元素后最近的那个不满足平衡的节点并进行旋转处理。

private Node leftRotate(Node y) {
    Node x = y.right;
    Node T3 = x.left;
    x.left = y;
    y.right = T3;

    // 重新计算X和Y的节点高度
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

    return x;
}

右旋转的过程：


         y                       x              过程：
        / \                    /   \             1. Node x = y.left;
       x   T4    右旋转        z     y            2. Node T3 = x.right;
      / \      =========>    / \   /  \          3. x.right = y;
     z   T3                 T1 T2 T3  T4         4. y.left = T3;
    / \
   T1  T2
  
private Node rightRotate(Node y) {
    Node x = y.left;
    Node t3 = x.right;
    x.right = y;
    y.left = t3;

    // 重新计算高度(先计算y节点的高度因为x节点的高度依赖于y)
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    return x;
}

树的遍历

树的遍历有两种方式：

广度优先遍历：也叫层序遍历，一层一层的访问每个节点。
深度优先遍历（前序遍历，中序遍历，后续遍历），访问根节点的顺序决定了其是什么遍历方式。

层序遍历

层序遍历也叫广度优先遍历，一般借助于队列去实现。

树结构如下：

            18
          /    \
        16      30
       /  \    /   \
      15  17  20    34
             /  \   / \
            19  28 32  36

1. [18] 入队后出队，并将18的左右节点16，30节点添加到队列中：| 16 | 30 |。
2. 16 出队，将16的左右子树节点15，17依次入队，| 30 | 15 | 17 |。
3. 30 出队，将30的左右子树节点20，34依次入队：| 15 | 17 | 20 | 34 | 此时队列中就是第三层的树了。 
4. 依此类推，遍历完整棵树，最后的结果为：[18, 16, 30, 15, 17, 20, 34, 19, 28, 32, 36]

code :
private void printNode(Node node) {
    if (node == null) {
        return;
    }
    // 队列进行层序遍历
    Queue<Node> list = new ArrayDeque<>();
    // push根节点
    list.add(node);
    // 存放结果的list
    List<K> resultList = new ArrayList<>();
    // 进行广度优先遍历
    printNodeLoop(list, resultList);
    // 输出结果
    System.out.println(resultList);
}


/**
* 广度优先遍历(层序遍历)
* 使用队列实现
* @param list
*/
private void printNodeLoop(Queue<Node> list, List<K> resultList) {
    while (list.size() > 0) {
        Node pop = list.remove();
        resultList.add(pop.key);
        if (pop.left != null) {
            list.add(pop.left);
        }
        if (pop.right != null) {
            list.add(pop.right);
        }
    }
}

深度优先遍历

这里使用递归的方式，进行中序遍历：

            18
          /    \
        16      30
       /  \    /   \
      15  17  20    34
private void inOrder(Node root, List<K> keys) {
    if (root == null) {
        return;
    }

    inOrder(root.left, keys);
    keys.add(root.key);
    inOrder(root.right, keys);
}

递归的遍历上述整棵树的过程：
每一次的递归调用，都会有系统栈去暂存此时的变量。

先去递归的遍历左子树，直至此节点的左子树为null时，添加此节点的值。
再去递归遍历此节点的右子树，直至此节点的右子树为null时，返回到上一此的系统栈。
到上一层的系统栈时，添加此节点的值，因为此时该节点左子树已填加故需要添加根节点了，再去递归遍历右子树的值…。

测试

/*
* 测试用例：
* // 根节点
* avlTree.add(20, "Y");
* // 左子树
* avlTree.add(18, "X");
* avlTree.add(30, "X4");
* avlTree.add(16, "Z");
* avlTree.add(19, "X3");
* avlTree.add(15, "X1");
* avlTree.add(17, "X2");
* // 右子树
* avlTree.add(30, "B");
* avlTree.add(28, "Q3");
* avlTree.add(34, "A");
* avlTree.add(32, "Q1");
* avlTree.add(36, "Q3");
* <p>
* <p>
* 第一次右旋转（添加15节点）后：
*       18
*      /  \
*     16  20
*    /    / \
*   15   19  30
* 添加32节点前：
*          18
*        /    \
*       16     20
*      /  \   /  \
*     15  17 19  30
*               /  \
*              28  34
* <p>
* 第一次左旋转（添加32节点）后：
*            18
*          /    \
*        16      30
*       /  \    /   \
*      15  17  20    34
*             /  \   / 
*            19  28 32
*/

public static void main(String[] args) {

    AVLTree<Integer, String> avlTree = new AVLTree<>();
    // 根节点
    avlTree.add(20, "Y");
    // 左子树
    avlTree.add(18, "X");
    avlTree.add(30, "X4");
    avlTree.add(16, "Z");
    avlTree.add(19, "X3");
    avlTree.add(15, "X1");
    avlTree.add(17, "X2");
    // 右子树
    avlTree.add(28, "Q3");
    avlTree.add(34, "A");
    avlTree.add(32, "Q1");
    avlTree.add(36, "Q3");

    List<Integer> keys = new ArrayList<>();

    avlTree.inOrder(avlTree.root, keys);
    System.out.println("中序遍历：" + keys);

    System.out.print("层序遍历：");
    avlTree.printNode(avlTree.root);
    System.out.println();

    System.out.println("是否是一棵平衡二叉树：" +avlTree.isBalanced());

}

最终的树的结构如下：
            18
          /    \
        16      30
       /  \    /   \
      15  17  20    34
             /  \   / \
            19  28 32  36

结果：

中序遍历：[15, 16, 17, 18, 19, 20, 28, 30, 32, 34, 36]
层序遍历：[18, 16, 30, 15, 17, 20, 34, 19, 28, 32, 36]

是否是一棵平衡二叉树：true