常用数据结构

红黑树(平衡二叉查找树)

首先他是一棵二叉搜索树(左子节点的值小于自身，右子结点的值大于自身，左子树都小于自身，右子树都大于自身，中序遍历是递增有序的)

极端情况下退化为链表，此时高度为n,操作时间复杂读降低。所以需要平衡树

红黑树通过对结点进行黑红标色，旋转及其他操作进行平衡操作

红黑树不具有严格的平衡属性(平衡属性：任意结点左右子树高度相差不大于1)，但是平均使用性能非常良好。适用于频繁插入和删除的的场景。什么时候红黑树进行旋转调整高度呢？当根到叶子结点的最长路径大于最短路径的两倍时，红黑树进行调整。

红黑树与AVL树对比

红黑树规则特点

• 节点分为红色或者黑色；

• 根节点必为黑色；

• 叶子节点都为黑色，且为null(不存储数据)；

• 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；

• 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；

• 新加入到红黑树的节点为红色节点；

这些规则强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长(而AVL平衡二叉搜索树的旋转策略是最大高度差不超过1)，结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

树的高度趋近于logn，从而树上的各种操作(插入/删除/查找)的时间复杂度为logn。

一颗有N的结点的红黑树高度最多不超过(<=)2long(N+1).

红黑树的变色与旋转

回顾红黑色的规则特点，当我们对红黑树进行插入和删除是，可能会破坏这些规则，所以我们需要变色和旋转维护红黑树的规则特点。

变色就是红色—->黑色或者黑色—->红色

旋转分为左旋和右旋

加入要对4结点进行左旋操作其中左旋右两个核心操作

一.4的右节点成为4的父节点

二.4结点的右孩子结点的左子树成为4的右子树

右旋和左旋对称同理

一、Queue和Deque

简介

Queue以及Deque都是继承于Collection，Deque是Queue的子接口。

Queue是FIFO的单向队列，Deque是双向队列。

Queue有一个直接子类PriorityQueue，而Deque中直接子类有两个：LinkedList以及ArrayDeque。

PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的。

ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。

PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。
ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。
LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

api对比

	Queue	Deque
增加	add	add、addFirst、addLast
	offer	offer、offerFirst、offerLast
移除	remove	remove、removeFirst、removeLast
	poll	pop、poll、pollFirst、pollLast
获取	element	element、getFirst、getLast
	peek	peek、peekFirst、peekLast

备注：

1、add和offer区别

• add() : 添加元素，如果添加成功则返回true，如果队列是满的，则抛出异常
• offer() : 添加元素，如果添加成功则返回true，如果队列是满的，则返回false

2、remove和poll

• remove() : 移除队列头的元素并且返回，如果队列为空则抛出异常
• poll() : 移除队列头的元素并且返回，如果队列为空则返回null
• Deque新增了一个pop方法，也是移除队列头的元素并且返回，如果队列为空则抛出异常。

3、element和peek

• element() ：返回队列头元素但不移除，如果队列为空，则抛出异常
• peek() ：返回队列头元素但不移除，如果队列为空，则返回null
• 因此，增加推荐使用add，移除推荐使用poll，获取元素推荐使用peek。

代码实例

1、queue

队列(queue)是一种常用的数据结构，可以将队列看做是一种特殊的线性表，该结构遵循的先进先出原则。Java中，LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高。

初始化：

Queue q = new LinkedList();

**常用方法：
**

**add(E e)?*将指定元素插入此队列尾部，成功返回true。

**offer(E e)?*将指定元素插入队列尾部，成功返回true。当队列有容量 限制时，此方法由于add，因为后者可能无法插入，而只是抛出IllegalStateException异常。

**remove()?*获取并移除队列的头部元素，队列为空抛出异常。

poll()：获取并移除队列的头部元素，队列为空返回null。

**element()?*获取但是不移除队列头部元素，队列为空抛出异常。

**peek()?*获取但是不移除队列头部元素，队列为空返回null。

**isEmpty()?*判断队列是否为空，为空返回true。

**size()?*获取队列元素数量.

实例代码：

public static void test01(){
    Queue<String> queue = new LinkedList<>();
    // add()和remove()方法在失败的时候会抛出异常(不推荐)
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    queue.offer("d");
    queue.offer("e");
    queue.add("f");
    //在队列元素为空的情况下，remove() 方法会抛出NoSuchElementException异常，poll() 方法只会返回 null 。
    String first2 = queue.remove();//返回第一个元素，删除
    System.out.println(first2);//a
    String first1 = queue.poll();//返回第一个元素，删除
    System.out.println(first1);//b
    String first = queue.peek();//返回第一个元素，但不删除
    System.out.println(first);//c
    System.out.println(queue);//[c, d, e, f]
    first = queue.element();//返回第一个元素
    System.out.println(first);//c
}

2、deque

双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则。

初始化：

Deque d = new LinkedList();

**常用方法：
**

**addLast(E e)?*在队列尾部插入元素.

**offerLast(E e)?*在队列尾部插入元素。

**removeFirst()?*获取头部元素。

**pollFirst()?*获取头部元素。

**getFirst()?*获取头部元素。

**peekFirst()?*获取头部元素。

//上述方法均和queue中方法一一对应。
//且queue中的方法，deque中均可用。

**getLast()?*获取但不移除队列最后一个元素。

**offerFirst()?*将指定元素插入队列开头。

**peekLast()?*获取但不移除双端队列最后一个元素。

**pollLast()?*获取并移除双端队列最后一个元素。

**pop()?*从双端队列表示的堆栈 中弹出一个元素。

**push()?*将一个元素推入双端队列表示的堆栈，即队列的头部。成功返回true，如果没有可用空间，抛出IllegalStateException。

**removeLast()?*获取并移除移除双端队列最后一个元素。

**size()?*返回双端队列元素数。

**isEmpty()?*判断队列是否为空，为空返回true。

**remove(Object o)?*从双端队列中移除第一次出现的指定元素。

实例代码：

public static void test02(){
    Deque<String> deque = new LinkedList<>();
    deque.offer("a");
    deque.offer("b");
    deque.offerFirst("c");//在队列头部进行插入
    System.out.println(deque);//[c, a, b]
    deque.offerLast("d");
    System.out.println(deque);//[c, a, b, d]
 
    String ret = deque.element();//返回第一个元素
    System.out.println(ret);//c
 
    ret = deque.getFirst();//返回第一个元素
    System.out.println(ret);//c
    ret = deque.getLast();//返回最后一个元素
    System.out.println(ret);//d
 
    ret = deque.peek();//返回第一个元素，但不删除
    System.out.println(ret);//c
 
    ret = deque.peekFirst();//返回第一个元素，但不删除
    System.out.println(ret);//c
    ret = deque.peekLast();//返回最后一个元素，但不删除
    System.out.println(ret);//d
 
    System.out.println(deque);
 
    ret = deque.poll();//返回第一个元素，删除
    System.out.println(ret);//c
    System.out.println(deque);//[a, b, d]
 
    ret = deque.pop();//返回第一个元素，删除
    System.out.println(ret);//a
    System.out.println(deque);//[b, d]
 
    deque.clear();
    ret = deque.pop();//抛异常
    System.out.println("11111");
    ret = deque.poll();//返回null,但不抛异常
    System.out.println("++"+ret);
    System.out.println("22222");
}