Adblocker

数据结构-核心篇之树

数据结构-核心篇之树

一 树

树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树具有以下特点：
1.每个结点有零个或多个子结点；
2.没有父结点的结点为根结点；
3.每一个非根结点只有一个父结点；
4.每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树；

1.1 树的相关概念

结点的度：
一个结点含有的子树的个数称为该结点的度；
叶结点：
度为0的结点称为叶结点，也可以叫做终端结点
分支结点：
度不为0的结点称为分支结点，也可以叫做非终端结点
结点的层次：
从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
结点的层序编号：
将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。
树的度：
树中所有结点的度的最大值
树的高度(深度)：
树中结点的最大层次
森林：
m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根
结点，森林就变成一棵树

孩子结点：
一个结点的直接后继结点称为该结点的孩子结点
双亲结点(父结点)：
一个结点的直接前驱称为该结点的双亲结点
兄弟结点：
同一双亲结点的孩子结点间互称兄弟结点

1.2 二叉树的种类

二叉树
就是度不超过2的树(每个结点最多有两个子结点)

满二叉树
如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树

完全二叉树
叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二 二叉搜索树

2.1 代码实现

package com.ycc.data.structure.tree;
import cn.itcast.algorithm.linear.Queue;
/**
 * 二叉搜索树
 * 二叉树 拥有两个孩子 ，二叉搜索树 左孩子小于根节点，右孩子大于根节点
 *
 * @author liaozx
 * @description
 * @create 2020-11-27 10:29
 */
public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    private Node root;
    private int current;
    public class Node {
        //存储键
        public Key key;
        //存储值
        private Value value;
        Node left;//左孩子
        Node right;//右孩子
        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * 向树中添加元素key-value
     *
     * @param key
     * @param value
     */
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }
    /**
     * 向指定的树node中添加key-value,并返回添加元素后新的树
     * 其逻辑是，新节点的key比较root的key，大于在右边，小于在左边，等于则替换
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node put(Node node, Key key, Value value) {
        //如果node子树为空
        if (null == node) {
            current++;
            return new Node(key, value, null, null);
        }
        //如果node子树不为空,比较node结点的键和key的大小
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            //如果key大于node结点的键，则继续找node结点的右子树
            node.right = put(node.right, key, value);
        } else if (cmp < 0) {
            //如果key小于node结点的键，则继续找node结点的左子树
            node.left = put(node.left, key, value);
        } else {
            //如果key等于node结点的键，则替换node结点的值为value即可
            node.value = value;
        }
        return node;
    }
    /**
     * 查询树中指定key对应的value
     *
     * @param key
     * @return
     */
    public Value get(Key key) {
        return get(root, key);
    }
    /**
     * 从指定的树node中，查找key对应的值
     *
     * @param node
     * @param key
     * @return
     */
    public Value get(Node node, Key key) {
        //node树为null
        if (node == null) {
            return null;
        }
        //node树不为null,比较key和node结点的键的大小
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            //如果key大于node结点的键，则继续找node结点的右子树
            return get(node.right, key);
        } else if (cmp < 0) {
            //如果key小于node结点的键，则继续找node结点的左子树
            return get(node.left, key);
        } else {
            //如果key等于node结点的键，就找到了键为key的结点，只需要返回node结点的值即可
            return node.value;
        }
    }
    /**
     * 删除树中key对应的value
     *
     * @param key
     */
    public void delete(Key key) {
        delete(root, key);
    }
    //删除指定树node中的key对应的value，并返回删除后的新树
    public Node delete(Node node, Key key) {
        //node树为null
        if (node == null) {
            return null;
        }
        //node树不为null
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            //如果key大于node结点的键，则继续找node结点的右子树
            node.right = delete(node.right, key);
        } else if (cmp < 0) {
            //如果key小于node结点的键，则继续找node结点的左子树
            node.left = delete(node.left, key);
        } else {
            //如果key等于node结点的键，完成真正的删除结点动作，要删除的结点就是node,让元素个数-1
            current--;
            //得找到右子树中最小的结点
            if (node.right == null) {
                return node.left;
            }
            if (node.left == null) {
                return node.right;
            }
            Node minNode = node.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            //删除右子树中最小的结点
            Node n = node.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    //变换n结点即可
                    n = n.left;
                }
            }
            //让node结点的左子树成为minNode的左子树
            minNode.left = node.left;
            //让node结点的右子树成为minNode的右子树
            minNode.right = node.right;
            //让node结点的父结点指向minNode
            node = minNode;
        }
        return node;
    }
    /**
     * 查找整个树中最小的键
     *
     * @return
     */
    public Key min() {
        return min(root).key;
    }
    /**
     * 在指定树node中找出最小键所在的结点
     *
     * @param node
     * @return
     */
    private Node min(Node node) {
        //需要判断node还有没有左子结点，如果有，则继续向左找，如果没有，则node就是最小键所在的结点
        if (node.left != null) {
            return min(node.left);
        } else {
            return node;
        }
    }
    /**
     * 在整个树中找到最大的键
     *
     * @return
     */
    public Key max() {
        return max(root).key;
    }
    /**
     * 在指定的树node中，找到最大的键所在的结点
     *
     * @param node
     * @return
     */
    public Node max(Node node) {
        //判断node还有没有右子结点，如果有，则继续向右查找，如果没有，则node就是最大键所在的结点
        if (node.right != null) {
            return max(node.right);
        } else {
            return node;
        }
    }
    /**
     * 前序遍历 根左右
     * 获取整个树中所有的键
     *
     * @return
     */
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }
    /**
     * 前序遍历 根左右
     * 获取指定树node的所有键，并放到keys队列中
     *
     * @param node
     * @param keys
     */
    private void preErgodic(Node node, Queue<Key> keys) {
        if (node == null) {
            return;
        }
        //把node结点的key放入到keys中
        keys.enqueue(node.key);
        //递归遍历node结点的左子树
        if (node.left != null) {
            preErgodic(node.left, keys);
        }
        //递归遍历node结点的右子树
        if (node.right != null) {
            preErgodic(node.right, keys);
        }
    }
    /**
     * 中序遍历 左根右
     * 使用中序遍历获取树中所有的键
     *
     * @return
     */
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }
    /**
     * 中序遍历 左根右
     * 使用中序遍历，获取指定树node中所有的键，并存放到key中
     *
     * @param node
     * @param keys
     */
    private void midErgodic(Node node, Queue<Key> keys) {
        if (node == null) {
            return;
        }
        //先递归，把左子树中的键放到keys中
        if (node.left != null) {
            midErgodic(node.left, keys);
        }
        //把当前结点node的键放到keys中
        keys.enqueue(node.key);
        //在递归，把右子树中的键放到keys中
        if (node.right != null) {
            midErgodic(node.right, keys);
        }
    }
    /**
     * 后序遍历 左右根
     * 使用后序遍历，把整个树中所有的键返回
     *
     * @return
     */
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }
    /**
     * 后序遍历 左右根
     * 使用后序遍历，把指定树node中所有的键放入到keys中
     *
     * @param node
     * @param keys
     */
    private void afterErgodic(Node node, Queue<Key> keys) {
        if (node == null) {
            return;
        }
        //通过递归把左子树中所有的键放入到keys中
        if (node.left != null) {
            afterErgodic(node.left, keys);
        }
        //通过递归把右子树中所有的键放入到keys中
        if (node.right != null) {
            afterErgodic(node.right, keys);
        }
        //把node结点的键放入到keys中
        keys.enqueue(node.key);
    }
    /**
     * 使用层序遍历，获取整个树中所有的键
     *
     * @return
     */
    public Queue<Key> layerErgodic() {
        //定义两个队列，分别存储树中的键和树中的结点
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();
        //默认，往队列中放入根结点
        nodes.enqueue(root);
        while (!nodes.isEmpty()) {
            //从队列中弹出一个结点，把key放入到keys中
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //判断当前结点还有没有左子结点，如果有，则放入到nodes中
            if (n.left != null) {
                nodes.enqueue(n.left);
            }
            //判断当前结点还有没有右子结点，如果有，则放入到nodes中
            if (n.right != null) {
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }
    //获取整个树的最大深度
    public int maxDepth() {
        return maxDepth(root);
    }
    //获取指定树node的最大深度
    private int maxDepth(Node node) {
        if (node == null) {
            return 0;
        }
        //node的最大深度
        int max = 0;
        //左子树的最大深度
        int maxL = 0;
        //右子树的最大深度
        int maxR = 0;
        //计算node结点左子树的最大深度
        if (node.left != null) {
            maxL = maxDepth(node.left);
        }
        //计算node结点右子树的最大深度
        if (node.right != null) {
            maxR = maxDepth(node.right);
        }
        //比较左子树最大深度和右子树最大深度，取较大值+1即可
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }
    //获取树中元素的个数
    public int size() {
        return current;
    }
}

2.2 折纸代码实现

package com.ycc.data.structure.tree.test;
import com.ycc.data.structure.line.MyLinedQueue;
/**
 * @author liaozx
 * @date 2020-11-27
 */
public class PaperFolding {
    public static void main(String[] args) {
        //构建折痕树
        Node tree = createTree(3);
        //遍历折痕树，并打印
        printTree(tree);
    }
    //3.使用中序遍历，打印出树中所有结点的内容；
    private static void printTree(Node tree) {
        if (tree == null) {
            return;
        }
        printTree(tree.left);
        System.out.print(tree.item + ",");
        printTree(tree.right);
    }
    //2.构建深度为N的折痕树；
    private static Node createTree(int N) {
        Node root = null;
        for (int i = 0; i < N; i++) {
            if (i == 0) {
                //1.第一次对折，只有一条折痕，创建根结点；
                root = new Node("down", null, null);
            } else {
                //2.如果不是第一次对折，则使用队列保存根结点；
                MyLinedQueue<Node> queue = new MyLinedQueue<>();
                queue.enQueue(root);
                //3.循环遍历队列：
                while (!queue.isEmpty()) {
                    //3.1从队列中拿出一个结点；
                    Node tmp = queue.deQueue();
                    //3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；
                    if (tmp.left != null) {
                        queue.enQueue(tmp.left);
                    }
                    //3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
                    if (tmp.right != null) {
                        queue.enQueue(tmp.right);
                    }
                    //3.4判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个 值为down的左子结点，一个值为up的右子结点。
                    if (tmp.left == null && tmp.right == null) {
                        tmp.left = new Node("down", null, null);
                        tmp.right = new Node("up", null, null);
                    }
                }
            }
        }
        return root;
    }
    //1.定义结点类
    private static class Node {
        //存储结点元素
        String item;
        //左子结点
        Node left;
        //右子结点
        Node right;
        public Node(String item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}

三 堆

堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。它对应的数组是按层存储，如图

特点：
父节点索引：i,左孩子索引：2i ,右孩子索引：2i+1，即8号球(索引:4)、7号球(索引:5)、14号球(索引:2)。
原理是他是完全二叉树。

大顶堆：父节点大于子节点，二叉树的根(堆顶)最大。
小顶堆：父节点小于子节点，二叉树的根(堆顶)最小。

3.1 大顶堆

3.1.1 实现原理

主要实现功能有：

1. 新增元素：insert
2. 删除最大元素：delMax

要实现上面两个功能需要理解两个堆化步骤：
上浮：
下面我们在该堆中插入一个新的元素26：

比较父节点的新节点的大小，如果新元素更大则交换两个元素的位置，这个操作就相当于把该元素上浮了一下

递归该操作直到26到了一个满足堆条件的位置，此时就完成了插入的操作：

下沉：
取出堆中的最大元素,最后一个元素替换掉栈顶元素，然后把最后一个元素删除掉.取出62元素。

用最后元素替换掉栈顶元素，然后删除最后一个元素：

然后比较其孩子结点的大小：

如果不满足堆的条件，那么就跟孩子结点中较大的一个交换位置：

递归该步骤，直到16到达合适的位置：

3.1.2代码实现

大顶堆的实现，

package com.ycc.data.structure.heap;
/**
 * 大顶堆
 *
 * @author liaozx
 * @date 2020-11-27
 */
public class MaxHeap<T extends Comparable<T>> {
    //存储堆中的元素
    private final T[] items;
    //记录堆中元素的个数
    private int current;
    public MaxHeap(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.current = 0;
    }
    /**
     * 判断堆中索引i处的元素是否小于索引j处的元素
     * i<j
     *
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }
    /**
     * 交换堆中i索引和j索引处的值
     *
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
    /**
     * 往堆中插入一个元素
     *
     * @param t
     */
    public void insert(T t) {
        items[++current] = t;
        siftUp(current);
    }
    /**
     * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
     *
     * @param k
     */
    private void siftUp(int k) {
        //通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
        while (k > 1) {
            //比较当前结点和其父结点
            if (less(k / 2, k)) {
                swap(k / 2, k);
            }
            //上级节点
            k = k / 2;
        }
    }
    /**
     * 删除堆中最大的元素,并返回这个最大元素
     *
     * @return
     */
    public T delMax() {
        T max = items[1];
        //交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根结点
        swap(1, current);
        //最大索引处的元素删除掉
        items[current] = null;
        //元素个数-1
        current--;
        //通过下沉调整堆，让堆重新有序
        siftDown(1);
        return max;
    }
    /**
     * 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
     *
     * @param k
     */
    private void siftDown(int k) {
        //通过循环不断的对比当前k结点和其左子结点2*k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
        while (2 * k <= current) {
            //获取当前结点的子结点中的较大结点
            int max;//记录较大结点所在的索引
            if (2 * k + 1 <= current) {
                if (less(2 * k, 2 * k + 1)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else {
                max = 2 * k;
            }
            //比较当前结点和较大结点的值
            if (!less(k, max)) {
                break;
            }
            //交换k索引处的值和max索引处的值
            swap(k, max);
            //变换k的值
            k = max;
        }
    }
}

测试代码

package com.ycc.data.structure.heap.test;
import com.ycc.data.structure.heap.MaxHeap;
/**
 * @author liaozx
 * @date 2020-11-27
 */
public class MaxHeapTest {
    public static void main(String[] args) {
        MaxHeap<String> heap = new MaxHeap<String>(20);
        heap.insert("1");
        heap.insert("2");
        heap.insert("3");
        heap.insert("4");
        heap.insert("5");
        heap.insert("6");
        heap.insert("7");
        String del;
        while ((del = heap.delMax()) != null) {
            System.out.print(del + ",");
        }
    }
}

3.2 小顶堆

3.2.1 实现原理

主要实现功能有：

1. 新增元素：insert
2. 删除最小元素：delMin

要实现上面两个功能需要理解两个堆化步骤：
上浮：
参考大顶堆
下沉：
参考大顶堆

3.2.2 代码实现

package com.ycc.data.structure.heap;
/**
 * 小顶堆
 *
 * @author liaozx
 * @date 2020-11-27
 */
public class MinHeap<T extends Comparable<T>> {
    //存储堆中的元素
    private final T[] items;
    //记录堆中元素的个数
    private int current;
    /**
     * 从1开始
     *
     * @param capacity
     */
    public MinHeap(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.current = 0;
    }
    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }
    //交换堆中i索引和j索引处的值
    private void swap(int i, int j) {
        T tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
    //往堆中插入一个元素
    public void insert(T t) {
        items[++current] = t;
        siftUp(current);
    }
    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void siftUp(int k) {
        //通过循环比较当前结点和其父结点的大小
        while (k > 1) {
            if (less(k, k / 2)) {
                swap(k, k / 2);
            }
            k = k / 2;
        }
    }
    //删除堆中最小的元素,并返回这个最小元素
    public T delMin() {
        T min = items[1];
        swap(1, current);
        //最小索引处的元素删除掉
        items[current] = null;
        current--;
        siftDown(1);
        return min;
    }
    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void siftDown(int k) {
        //通过循环比较当前结点和其子结点中的较小值
        while (2 * k <= current) {
            //1.找到子结点中的较小值
            int min;
            if (2 * k + 1 <= current) {
                if (less(2 * k, 2 * k + 1)) {
                    min = 2 * k;
                } else {
                    min = 2 * k + 1;
                }
            } else {
                min = 2 * k;
            }
            //2.判断当前结点和较小值的大小
            if (less(k, min)) {
                break;
            }
            swap(k, min);
            k = min;
        }
    }
}

测试代码

package com.ycc.data.structure.heap.test;
import com.ycc.data.structure.heap.MinHeap;
/**
 * @author liaozx
 * @date 2020-11-27
 */
public class MinHeapTest {
    public static void main(String[] args) {
        MinHeap<String> heap = new MinHeap<String>(20);
        heap.insert("7");
        heap.insert("4");
        heap.insert("2");
        heap.insert("1");
        heap.insert("3");
        heap.insert("5");
        heap.insert("6");
        String del;
        while ((del = heap.delMin()) != null) {
            System.out.print(del + ",");
        }
    }
}

四 优先队列

优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的，底层数据结构就是基于二叉堆的。

4.1 最大优先队列

可以获取并删除队列中最大的值

package com.ycc.data.structure.heap;
/**
 * 最大优先队列
 *
 * @author liaozx
 * @date 2020-11-27
 */
public class MaxPriorityQueue<E extends Comparable<E>> {
    private final MaxHeap<E> maxHeap;
    public MaxPriorityQueue() {
        maxHeap = new MaxHeap<E>(20);
    }
    public void enqueue(E e) {
        maxHeap.insert(e);
    }
    public E dequeue() {
        return maxHeap.delMax();
    }
}

4.2 最小优先队列

可以获取并删除队列中最小的值

package com.ycc.data.structure.heap;
/**
 * 最小优先队列
 *
 * @author liaozx
 * @date 2020-11-27
 */
public class MinPriorityQueue<E extends Comparable<E>> {
    private final MinHeap<E> minHeap;
    public MinPriorityQueue() {
        minHeap = new MinHeap<E>(20);
    }
    public void enqueue(E e) {
        minHeap.insert(e);
    }
    public E dequeue() {
        return minHeap.delMin();
    }
}

4.3 索引优先队列

最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法通过索引访问已存在于优先队列中的对象。但是我们可以给元素关联一个key，然后通过这个key查询这个value。

4.3.1 最小索引优先队列原理

1. 索引关联 | 元数据
   T[]items | 数组的索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 将来需堆化存储 | | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | | value | S | O | R | T | E | X | A | M | P | L | E | 真实的数据无序的 | | 因为上面的数据，不能堆化，如果堆化，则会上浮或者下沉操作，即数据与索引的对应关系发生change，因此我们要堆化索引即可，如下图所示(最小的数据的索引在最上面)： | | | | | | | | | | | | | | |
   将上面的索引保存到下面的数组中
   ⏬ | | | | | | | | | | | | | | | pq存数据索引 | 数组的索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 堆从1开始，不是0 | | | 存储items索引 | 6 | 10 | 4 | 9 | 7 | 1 | 8 | 2 | 0 | 3 | 5 | 堆化后的索引 | | 如果我们查询S元素，即遍历pq，判断value=0，即获取了s元素，但是这个效率很低，需要我们去遍历。
   因此我们还有一个辅助数组，存pq的索引。 | | | | | | | | | | | | | | | qp存pq的索引 | 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | items的索引 | | | 存pq的索引 | 9 | 6 | 8 | 10 | 3 | 11 | 1 | 5 | 7 | 4 | 2 | 存储pq的索引 | | 既然qp数组存储了pq的索引，那么我们很容易定位元素。比如我们需要更新s的值，那么元素S对应的索引是0，我们根据0从qp中获取pq的索引，即9。 | | | | | | | | | | | | | |

4.3.1 最小索引优先队列代码实现

package com.ycc.data.structure.heap;
public class IndexMinPriorityQueue<T extends Comparable<T>> {
    /**
     * 普通数组 存储堆中的元素
     */
    private final T[] items;
    /**
     * 二叉堆，保存每个元素在items数组中的索引，pq数组需要堆有序
     */
    private final int[] pq;
    /**
     * 普通数组 保存qp的逆序，pq的值作为索引，pq的索引作为值
     */
    private final int[] qp;
    //记录堆中元素的个数
    private int current;
    public IndexMinPriorityQueue(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.pq = new int[capacity + 1];
        this.qp = new int[capacity + 1];
        this.current = 0;
        //默认情况下，队列中没有存储任何数据，让qp中的元素都为-1；
        for (int i = 0; i < qp.length; i++) {
            qp[i] = -1;
        }
    }
    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }
    //交换堆中i索引和j索引处的值
    private void swap(int i, int j) {
        //交换pq中的数据
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
        //更新qp中的数据,pq[i]即为items元素的索引，即qp[元素索引]存储pq的索引
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
    //判断k对应的元素是否存在
    public boolean contains(int k) {
        return qp[k] != -1;
    }
    //往队列中插入一个元素,并关联索引i
    public void insert(int i, T t) {
        //判断i是否已经被关联，如果已经被关联，则不让插入
        if (contains(i)) {
            return;
        }
        //元素个数+1
        current++;
        //把数据存储到items对应的i位置处
        items[i] = t;
        //把i对应的索引，存储到pq中，即在末尾存储元数据的索引
        pq[current] = i;
        //通过qp来记录,pq存储元数据（元数据对应的索引）的索引
        qp[i] = current;
        //通过堆上浮完成堆的调整
        siftUp(current);
    }
    //删除队列中最小的元素,并返回该元素关联的索引
    public int delMin() {
        //获取最小元素关联的索引
        int minIndex = pq[1];
        //交换pq中索引1处和最大索引处的元素
        swap(1, current);
        //删除qp中对应的内容
        qp[pq[current]] = -1;
        //删除pq最大索引处的内容
        pq[current] = -1;
        //删除items中对应的内容
        items[minIndex] = null;
        //元素个数-1
        current--;
        //下沉调整
        siftDown(1);
        return minIndex;
    }
    //删除索引i关联的元素
    public void delete(int i) {
        //找到i在pq中的索引
        int k = qp[i];
        //交换pq中索引k处的值和索引N处的值
        swap(k, current);
        //删除qp中的内容
        qp[pq[current]] = -1;
        //删除pq中的内容
        pq[current] = -1;
        //删除items中的内容
        items[k] = null;
        //元素的数量-1
        current--;
        //堆的调整
        siftDown(k);
        siftUp(k);
    }
    //把与索引i关联的元素修改为为t
    public void changeItem(int i, T t) {
        //修改items数组中i位置的元素为t
        items[i] = t;
        //找到i在pq中出现的位置
        int k = qp[i];
        //堆调整
        siftDown(k);
        siftUp(k);
    }
    /**
     * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
     *
     * @param k
     */
    private void siftUp(int k) {
        while (k > 1) {
            if (less(k, k / 2)) {
                swap(k, k / 2);
            }
            k = k / 2;
        }
    }
    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void siftDown(int k) {
        while (2 * k <= current) {
            //找到子结点中的较小值
            int min;
            if (2 * k + 1 <= current) {
                if (less(2 * k, 2 * k + 1)) {
                    min = 2 * k;
                } else {
                    min = 2 * k + 1;
                }
            } else {
                min = 2 * k;
            }
            //比较当前结点和较小值
            if (less(k, min)) {
                break;
            }
            swap(k, min);
            k = min;
        }
    }
}

五 AVL树

AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

右图：7的左子树(即2为根的树)高度为：3 ，右子树(即8为根的树)的高度为：1，则高度差2>1即不是平衡树。

5.1 实现原理

5.1.1 失衡的情况分析

总的来说，AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一，它们都由各自的定义：

LL：LeftLeft，也称为”左左”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。
例如，在上面LL情况中，由于”根节点(8)的左子树(4)的左子树(2)还有非空子节点”，而”根节点(8)的右子树(12)没有子节点”；导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

LR：LeftRight，也称为”左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。
例如，在上面LR情况中，由于”根节点(8)的左子树(4)的左子树(6)还有非空子节点”，而”根节点(8)的右子树(12)没有子节点”；导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

RL：RightLeft，称为”右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。
例如，在上面RL情况中，由于”根节点(8)的右子树(12)的左子树(10)还有非空子节点”，而”根节点(8)的左子树(4)没有子节点”；导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

RR：RightRight，称为”右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。
例如，在上面RR情况中，由于”根节点(8)的右子树(12)的右子树(14)还有非空子节点”，而”根节点(8)的左子树(4)没有子节点”；导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。
_
如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍”LL(左左)，LR(左右)，RR(右右)和RL(右左)”这4种情况对应的旋转方法。

5.1.2 选择平衡分析

LL的旋转：
LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：

RR的旋转：
理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：

LR的旋转：
LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图：

RL的旋转：
RL是与LR的对称情况！RL恢复平衡的旋转方法如下：

5.2 代码实现

package com.ycc.data.structure.tree;
/**
 * https://www.cnblogs.com/skywang12345/p/3577479.html
 *
 * @author liaozx
 * @description 平衡二叉树
 * @create 2020-11-27 11:02
 */
public class AVLTree<T extends Comparable<T>> {
    private Node<T> root;    // 根结点
    // AVL树的节点(内部类)
    private class Node<T extends Comparable<T>> {
        // 关键字(键值)
        private T key;
        // 高度
        private int height;
        // 左孩子
        private Node<T> left;
        // 右孩子
        private Node<T> right;
        public Node(T key) {
            this.key = key;
        }
    }
    // 构造函数
    public AVLTree() {
        root = null;
    }
    /*
     * 获取树的高度
     */
    private int height(Node<T> tree) {
        if (tree != null)
            return tree.height;
        return 0;
    }
    public int height() {
        return height(root);
    }
    /*
     * 比较两个值的大小
     */
    private int max(int a, int b) {
        return a > b ? a : b;
    }
    public Node<T> search(T key) {
        return search(root, key);
    }
    /*
     * (递归实现)查找"AVL树x"中键值为key的节点
     */
    private Node<T> search(Node<T> x, T key) {
        if (x == null)
            return x;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }
    public Node<T> iterativeSearch(T key) {
        return iterativeSearch(root, key);
    }
    /*
     * (非递归实现)查找"AVL树x"中键值为key的节点
     */
    private Node<T> iterativeSearch(Node<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x;
        }
        return x;
    }
    /*
     * 查找最小结点：返回tree为根结点的AVL树的最小结点。
     */
    private Node<T> minimum(Node<T> tree) {
        if (tree == null)
            return null;
        while (tree.left != null)
            tree = tree.left;
        return tree;
    }
    public T minimum() {
        Node<T> p = minimum(root);
        if (p != null)
            return p.key;
        return null;
    }
    /*
     * 查找最大结点：返回tree为根结点的AVL树的最大结点。
     */
    private Node<T> maximum(Node<T> tree) {
        if (tree == null)
            return null;
        while (tree.right != null)
            tree = tree.right;
        return tree;
    }
    public T maximum() {
        Node<T> p = maximum(root);
        if (p != null)
            return p.key;
        return null;
    }
    /*
     * LL：左左对应的情况(右单旋转)。
     *
     *                   10
     *                  *  *
     *                 *    *
     *                6      15
     *               *
     *              *
     *             4
     *            *
     *           *
     *          2
     *
     *
     *             10
     *            *  *
     *           4    15
     *         *  *
     *        2    6
     *       *
     *      1
     *
     *
     * 返回值：旋转后的根节点
     */
    private Node<T> lLRotation(Node<T> k2) {
        //获取左节点,然后k1即将升为根节点
        Node<T> k1 = k2.left;
        //k1的右节点，变成k2的左子节点
        k2.left = k1.right;
        //k1升级为根节点，即上级节点
        k1.right = k2;
        //k2的树高度
        k2.height = max(height(k2.left), height(k2.right)) + 1;
        //k1的树高度
        k1.height = max(height(k1.left), k2.height) + 1;
        return k1;
    }
    /*
     * RR：右右对应的情况(左单旋转)。
     *
     * 返回值：旋转后的根节点
     */
    private Node<T> rRRotation(Node<T> k1) {
        //获取右节点，然后k2即将升为根节点
        Node<T> k2 = k1.right;
        //k1即将变成左子节点，且k1的有孩子，即k2的左孩子
        k1.right = k2.left;
        //k1 变成更节点
        k2.left = k1;
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;
        return k2;
    }
    /*
     * LR：左右对应的情况(左双旋转)。
     *
     *
     *              10
     *              *
     *             *
     *            6
     *              *
     *               *
     *                 8
     * 返回值：旋转后的根节点
     *
     * 左右先掰直，即先左旋变成LL,然后在在右旋
     */
    private Node<T> leftRightRotation(Node<T> k3) {
        k3.left = rRRotation(k3.left); //先左旋,掰直成左斜杠
        return lLRotation(k3);//再右旋，掰弯成倒三角平衡了
    }
    /*
     * RL：右左对应的情况(右双旋转)。
     *
     * 返回值：旋转后的根节点
     */
    private Node<T> rightLeftRotation(Node<T> k1) {
        k1.right = lLRotation(k1.right);//先右旋,掰直成右斜杠
        return rRRotation(k1);//再左旋，掰弯成倒三角平衡了
    }
    public void insert(T key) {
        root = insert(root, key);
    }
    /*
     * 将结点插入到AVL树中，并返回根节点
     *
     * 参数说明：
     *     tree AVL树的根结点
     *     key 插入的结点的键值
     * 返回值：
     *     根节点
     *
     *               16
     *              *  *
     *             *    *
     *            10    20
     *           * *
     *          *   *
     *         6    14
     *        *
     *       *
     *      4
     */
    private Node<T> insert(Node<T> tree, T key) {
        if (tree == null) {
            // 新建节点
            tree = new Node<T>(key);
        } else {
            int cmp = key.compareTo(tree.key);
            if (cmp < 0) {
                // 应该将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.left) - height(tree.right) == 2) {
                    if (key.compareTo(tree.left.key) < 0) // 比左孩子小(如上图 4<6) 则是左左，即右旋
                        tree = lLRotation(tree);//右旋
                    else      //左右  即8>6
                        tree = leftRightRotation(tree);//左双旋
                }
            } else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.right) - height(tree.left) == 2) {
                    if (key.compareTo(tree.right.key) > 0) //比右边孩子大 则是右右，即左旋
                        tree = rRRotation(tree);//左旋
                    else
                        tree = rightLeftRotation(tree);//右双旋
                }
            } else {    // cmp==0
                System.out.println("添加失败：不允许添加相同的节点！");
            }
        }
        tree.height = max(height(tree.left), height(tree.right)) + 1;
        return tree;
    }
    public void remove(T key) {
        Node<T> z;
        if ((z = search(root, key)) != null)
            root = remove(root, z);
    }
    /*
     * 删除结点(z)，返回根节点
     *
     * 参数说明：
     *     tree AVL树的根结点
     *     z 待删除的结点
     * 返回值：
     *     根节点
     */
    private Node<T> remove(Node<T> tree, Node<T> z) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (tree == null || z == null)
            return null;
        int cmp = z.key.compareTo(tree.key);
        if (cmp < 0) {
            // 待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
                Node<T> r = tree.right;
                if (height(r.left) > height(r.right))
                    tree = rightLeftRotation(tree);
                else
                    tree = rRRotation(tree);
            }
        } else if (cmp > 0) {    
            // 待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
                Node<T> l = tree.left;
                if (height(l.right) > height(l.left))
                    tree = leftRightRotation(tree);
                else
                    tree = lLRotation(tree);
            }
        } else {    // tree是对应要删除的节点。
            // tree的左右孩子都非空
            if ((tree.left != null) && (tree.right != null)) {
                if (height(tree.left) > height(tree.right)) {
                    // 如果tree的左子树比右子树高；
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    Node<T> max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                } else {
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                    // 则(01)找出tree的右子树中的最小节点
                    //   (02)将该最小节点的值赋值给tree。
                    //   (03)删除该最小节点。
                    // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    Node<T> min = maximum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            } else {
                Node<T> tmp = tree;
                tree = (tree.left != null) ? tree.left : tree.right;
                tmp = null;
            }
        }
        return tree;
    }
    /*
     * 销毁AVL树
     */
    private void destroy(Node<T> tree) {
        if (tree == null)
            return;
        if (tree.left != null)
            destroy(tree.left);
        if (tree.right != null)
            destroy(tree.right);
        tree = null;
    }
    public void destroy() {
        destroy(root);
    }
    /*
     * 打印"二叉查找树"
     *
     * key        -- 节点的键值
     * direction  --  0，表示该节点是根节点;
     *               -1，表示该节点是它的父结点的左孩子;
     *                1，表示该节点是它的父结点的右孩子。
     */
    private void print(Node<T> tree, T key, int direction) {
        if (tree != null) {
            if (direction == 0)    // tree是根节点
                System.out.printf("%2d is root\n", tree.key, key);
            else                // tree是分支节点
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }
    public void print() {
        if (root != null)
            print(root, root.key, 0);
    }
}