1. package com.zhangyong.DataStructures.Tree.AVL;
    3. import java.util.ArrayList;
    5. /**
    6.  * <p>ClassName:  </p>
    7.  * <p>Description: 平衡二叉树 </p>
    8.  * 在BST基础上添加 自平衡机制;
    9.  *
    10.  * @author zhangyong
    11.  * @version 1.0.0
    12.  * @date 2018/12/13 15:06
    13.  */
    14. public class AVLTree<K extends Comparable<K>, V> {
    15.     private class Node {
    16.         public K key;
    17.         public V value;
    18.         public Node left, right;
    19.         public int height;
    21.         public Node(K key, V value) {
    22.             this.key = key;
    23.             this.value = value;
    24.             left = null;
    25.             right = null;
    26.             height = 1;
    27.         }
    28.     }
    30.     private Node root;
    31.     private int size;
    33.     public AVLTree() {
    34.         root = null;
    35.         size = 0;
    36.     }
    38.     public int getSize() {
    39.         return size;
    40.     }
    42.     public boolean isEmpty() {
    43.         return size == 0;
    44.     }
    46.     //判断二叉树是否是一颗二分搜索树
    47.     private boolean isBST() {
    48.         ArrayList<K> keys = new ArrayList<>();
    49.         inOrder(root, keys);
    50.         for (int i = 1; i < keys.size(); ++i) {
    51.             if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
    52.                 return false;
    53.             }
    54.         }
    55.         return true;
    56.     }
    58.     /**
    59.      * 中序遍历
    60.      *
    61.      * @param node
    62.      * @param keys
    63.      */
    64.     private void inOrder(Node node, ArrayList<K> keys) {
    65.         if (node == null) {
    66.             return;
    67.         }
    68.         inOrder(node.left, keys);
    69.         keys.add(node.key);
    70.         inOrder(node.right, keys);
    71.     }
    73.     //判断一颗二叉树是不是平衡二叉树
    74.     public boolean isBalanced() {
    75.         return isBalanced(root);
    76.     }
    78.     /**
    79.      * 判断一颗二叉树是否是一颗平衡二叉树
    80.      *
    81.      * @param node
    82.      * @return
    83.      */
    84.     private boolean isBalanced(Node node) {
    85.         if (node == null) {
    86.             return true;
    87.         }
    88.         int balanceFactor = getBalanceFactor(node);
    89.         if (Math.abs(balanceFactor) > 1) {
    90.             return false;
    91.         }
    92.         return isBalanced(node.left) && isBalanced(node.right);
    93.     }
    95.     // 向二分搜索树中添加新的元素(key, value)
    96.     public void add(K key, V value) {
    97.         root = add(root, key, value);
    98.     }
    100.     //获取高度;
    101.     //叶子节点高度为0，非叶子节点高度为左右孩子节点最大+1
    102.     private int getHeight(Node node) {
    103.         if (node == null) {
    104.             return 0;
    105.         }
    106.         return node.height;
    107.     }
    109.     // 向以node为根的二分搜索树中插入元素(key, value)，递归算法
    110.     // 返回插入新节点后二分搜索树的根
    111.     private Node add(Node node, K key, V value) {
    112.         if (node == null) {
    113.             size++;
    114.             return new Node(key, value);
    115.         }
    116.         if (key.compareTo(node.key) < 0) {
    117.             node.left = add(node.left, key, value);
    118.         } else if (key.compareTo(node.key) > 0) {
    119.             node.right = add(node.right, key, value);
    120.         } else if (key.compareTo(node.key) == 0) {
    121.             node.value = value;
    122.         }
    123.         //添加节点之后 更新当前node的height
    124.         node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    125.         //计算 平衡因子
    126.         int balanceFactor = getBalanceFactor(node);
    127.         if (Math.abs(balanceFactor) > 1) {
    128.             System.out.println("This tree is unbalanced, the unbalanced coefficient is :" + balanceFactor);
    129.         }
    130.         //平衡维护
    131.         //【1】LL
    132.         /**
    133.          *             a                   b
    134.          *           /  \               /     \
    135.          *          b    c ===>        d       a
    136.          *        /  \               /       /  \
    137.          *       d   e              f       e    c
    138.          *     /
    139.          *    f
    140.          */
    141.         if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
    142.             return rightRotate(node);
    143.         }
    144.         //【2】RR
    145.         /**
    146.          *             a                       c
    147.          *           /  \                    /   \
    148.          *          b    c     ===>         a    e
    149.          *             /  \               /  \    \
    150.          *            d    e             b   d     f
    151.          *                 \
    152.          *                 f
    153.          */
    154.         if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
    155.             return leftRotate(node);
    156.         }
    157.         //【3】LR
    158.         /**
    159.          *             a                         a                         e
    160.          *           /  \                     /     \                   /     \
    161.          *          b    c      ===>         e       c    ===>         b        a
    162.          *        /  \                     /   \                    /    \    /   \
    163.          *       d    e                   b     h                  d     g   h     c
    164.          *          /  \                /   \
    165.          *         g   h              d     g
    166.          */
    167.         if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
    168.             node.left = leftRotate(node.left);
    169.             return rightRotate(node.left);
    170.         }
    171.         // 【4】 RL
    172.         if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
    173.             node.right = rightRotate(node.right);
    174.             return leftRotate(node.right);
    175.         }
    176.         return node;
    177.     }
    179.     /**
    180.      * 右旋转
    181.      * // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    182.      * //        y                              x
    183.      * //       / \                           /   \
    184.      * //      x   T4     向右旋转 (y)        z     y
    185.      * //     / \       - - - - - - - ->    / \   / \
    186.      * //    z   T3                       T1  T2 T3 T4
    187.      * //   / \
    188.      * // T1   T2
    189.      * 节点 y 即为开始不平衡的点;
    190.      *
    191.      * @param y
    192.      * @return
    193.      */
    194.     private Node rightRotate(Node y) {
    195.         Node x = y.left;
    196.         Node T3 = x.right;
    197.         //向右旋转过程;
    198.         x.right = y;
    199.         y.left = T3;
    200.         y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    201.         x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    202.         return x;
    203.     }
    205.     /**
    206.      * 左旋转
    207.      * // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    208.      * //        y                              x
    209.      * //       / \                           /    \
    210.      * //      T4 x     向左旋转 (y)          y      z
    211.      * //        / \                        / \    /  \
    212.      * //      T3  z                      T4  T3  T2  T1
    213.      * //          / \
    214.      * //        T2 T1
    215.      * 节点 y 即为开始不平衡的点;
    216.      *
    217.      * @param y
    218.      * @return
    219.      */
    220.     private Node leftRotate(Node y) {
    221.         Node x = y.right;
    222.         Node T3 = x.left;
    223.         x.left = y;
    224.         y.right = T3;
    225.         y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    226.         x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    227.         return x;
    228.     }
    230.     //获取一个节点的平衡因子
    231.     private int getBalanceFactor(Node node) {
    232.         if (node == null)
    233.             return 0;
    234.         return getHeight(node.left) - getHeight(node.right);
    235.     }
    237.     // 返回以node为根节点的二分搜索树中，key所在的节点
    238.     private Node getNode(Node node, K key) {
    239.         if (node==null) {
    240.             return null;
    241.         }
    242.         if (key.equals(node.key))
    243.             return node;
    244.         else if (key.compareTo(node.key) < 0)
    245.             return getNode(node.left, key);
    246.         else // if(key.compareTo(node.key) > 0)
    247.             return getNode(node.right, key);
    248.     }
    250.     public boolean contains(K key) {
    251.         return getNode(root, key) != null;
    252.     }
    254.     public V get(K key) {
    256.         Node node = getNode(root, key);
    257.         if (node == null) {
    258.             return null;
    259.         }
    260.         return node.value;
    261.     }
    263.     public void set(K key, V newValue) {
    264.         Node node = getNode(root, key);
    265.         if (node == null)
    266.             throw new IllegalArgumentException(key + " doesn't exist!");
    268.         node.value = newValue;
    269.     }
    271.     // 返回以node为根的二分搜索树的最小值所在的节点
    272.     private Node minimum(Node node) {
    273.         if (node.left == null)
    274.             return node;
    275.         return minimum(node.left);
    276.     }
    278.     // 删除掉以node为根的二分搜索树中的最小节点
    279.     // 返回删除节点后新的二分搜索树的根
    280.     private Node removeMin(Node node) {
    282.         if (node.left == null) {
    283.             Node rightNode = node.right;
    284.             node.right = null;
    285.             size--;
    286.             return rightNode;
    287.         }
    289.         node.left = removeMin(node.left);
    290.         return node;
    291.     }
    293.     // 从二分搜索树中删除键为key的节点
    294.     public V remove(K key) {
    296.         Node node = getNode(root, key);
    297.         if (node != null) {
    298.             root = remove(root, key);
    299.             return node.value;
    300.         }
    301.         return null;
    302.     }
    304.     private Node remove(Node node, K key) {
    306.         if (node == null)
    307.             return null;
    309.         if (key.compareTo(node.key) < 0) {
    310.             node.left = remove(node.left, key);
    311.             return node;
    312.         } else if (key.compareTo(node.key) > 0) {
    313.             node.right = remove(node.right, key);
    314.             return node;
    315.         } else {   // key.compareTo(node.key) == 0
    317.             // 待删除节点左子树为空的情况
    318.             if (node.left == null) {
    319.                 Node rightNode = node.right;
    320.                 node.right = null;
    321.                 size--;
    322.                 return rightNode;
    323.             }
    325.             // 待删除节点右子树为空的情况
    326.             if (node.right == null) {
    327.                 Node leftNode = node.left;
    328.                 node.left = null;
    329.                 size--;
    330.                 return leftNode;
    331.             }
    333.             // 待删除节点左右子树均不为空的情况
    335.             // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
    336.             // 用这个节点顶替待删除节点的位置
    337.             Node successor = minimum(node.right);
    338.             successor.right = removeMin(node.right);
    339.             successor.left = node.left;
    341.             node.left = node.right = null;
    343.             return successor;
    344.         }
    345.     }
    347.     public static void main(String[] args) {
    349.         System.out.println("Pride and Prejudice");
    351.         ArrayList<String> words = new ArrayList<>();
    352.         if (FileOperation.readFile("pride-and-prejudice.txt", words)) {
    353.             System.out.println("Total words: " + words.size());
    355.             AVLTree<String, Integer> map = new AVLTree<>();
    356.             for (String word : words) {
    357.                 if (map.contains(word))
    358.                     map.set(word, map.get(word) + 1);
    359.                 else
    360.                     map.add(word, 1);
    361.             }
    363.             System.out.println("Total different words: " + map.getSize());
    364.             System.out.println("Frequency of PRIDE: " + map.get("pride"));
    365.             System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
    367.             System.out.println("is BST ：" + map.isBST());
    368.         }
    370.         System.out.println();
    371.     }
    372. }