散列表和树史上最快入门

阅读数: 次 2020-05-01

概述

你可能不知道一篇文章把散列表和树入门讲透是什么概念，我们一般把这种人称为土块

我经常说一句话，当年林纳斯花了几个月就写出了Linux，我JY用一篇文章讲个入门不是问题

埋伏他一手，这句骚话不能写，这个标签不用创，他死定了。

反手给个概述，闷声发大财！他也来概述？但是不用怕，他赢不了我。

如果把这个概述换成结语，我这波将绝杀，但是换不得。

（未完待续 To Be Continue…….）

散列表

1.概念

散列表(Hash Table)又名哈希表/Hash 表，是根据键（Key）直接访问在内存存储位置的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

2.散列函数

2.1散列函数的要求及特点

散列函数就是一个函数(方法)，能够将给定的 key 转换为特定的散列值，我们可以表示为：

hash(key) = hashValue

散列函数要满足的几个基本要求：

散列函数计算得到的散列值必须是大于等于 0 的正整数，因为 hash 值需要作为数组的下标。
如果 key1== key2，那么经过 hash 后得到的哈希值也必相同即： hash(key1) == hash(key2)
如果 key1 != key2，那么经过 hash 后得到的哈希值也必不相同即：hash(key1) != hash(key2)

好的散列函数应该满足以下特点：

散列函数不能太复杂，因为太复杂度势必要消耗很多的时间在计算哈希值上，
也会间接影响散列表性能。
散列函数计算得出的哈希值尽可能的能随机并且均匀的分布，这样能够将散列
冲突最小化。

2.2散列函数的设计方法

2.2.1直接寻址法：

我们可以取关键字 key 的某个线性函数值为散列地址，即：hash(key) = a x key + b，其中 a,b 为常量

例子：比如我们现在要对 0-100 岁的人口数字统计表，那么我们对年龄这个关键字 key就可以直接用年龄的数字作为地址。此时 hash(key) = key。这个时候，我们可以得出这么个哈希函数： hash(0) = 0， hash(1) = 1， ……， hash(20) = 20。

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字 key 的分布情况，适合査找表较小且连续的情况。由于这样的限制，在现实应用中，直接寻址法虽然简单，但却并不常用。

2.2.2除留余数法

除留余数法此方法为最常用的构造散列函数方法。对于散列表长为 m 的散列函数公式为：
hash( key ) = key % p ( p ≤ m )

使用除留余数法的一个经验是，若散列表表长为 m，通常 p 为小于或等于表长（最好接近 m)的最大质数或不包含小于 20 质因子的合数。总之实践结果证明：当 P 取小于哈希表长的最大质数时，产生的哈希函数较好。

2.2.3平方取中法

这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。 hash(key) = key 平方的中间几位

这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。

2.2.4折叠法

这个没太搞懂，解释不起来，我直接截取原话大家理解理解

有时关键码所含的位数很多，采用平方取中法计算太复杂，则可将关键码分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址，这方法称为折叠法，折叠法可分为两种：
移位叠加：将分割后的几部分低位对齐相加。
边界叠加:从一端沿分割界来回折叠，然后对齐相加。

2.3散列冲突

又名Hash冲突，Hash碰撞

两个不同的关键字（key），由于散列函数值相同，因而被映射到同一表位置上。该现象称为散列冲突或哈希碰撞。

即key1 != key2 hash(key1)==hash(key2)

3.散列冲突的解决方案

3.1开放寻址法

开放寻址法的核心思想是：一旦出现了散列冲突，我们就重新去寻址一个空的散列地址。

3.1.1线性检测：

我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

上述过程其实就是向散列表中插入数据，如果要从散列表中查找是否存在某个元素，这个过程跟插入类似，先根据散列函数求出要查找元素的 key 的散列值，然后比较数组中下标为其散列值的元素和要查找的元素，如果相等则表明该元素就是我们想要的元素，如果不等还要继续向后寻找遍历，如果遍历到数组中的空闲位置还没有找到则说明我们要找的元素并不在散列表中。

散列表删除操作：从散列表中查找是否存在某个元素一旦在对应 hash 值下标下的元素不是我们想要的就会继续在散列表中向后遍历，直到找到数组中的空闲位置，但如果这个空闲位置是我们刚刚删除的，那就会中断向后查找的过程，那这样的话查找的算法就会失效，本来应该认定为存在的元素会被认定为不存在，那删除的问题如何解决呢？我们可以将删除的元素特殊标记为 deleted，当线性检测遇到标记 deleted的时候并不停下来而是继续向后检测。

因此，使用线性检测的方式存在很大的问题：那就是当散列表中的数据越来越多的时候，散列冲突发生的可能性就越来越大，空闲的位置越来越少，那线性检测的时间就会越来越长，在极端情况下我们可能需要遍历整个数组，所以最坏的情况下时间复杂度为 O(n)

3.1.2二次检测

所谓的二次检测跟线性检测的原理一样，只不过线性检测每次检测的步长是 1，每次检测的下标依次是： hash(key)+0， hash(key)+1， hash(key)+2，hash(key)+3………，所谓的二次检测指的是每次检测的步长变为原来的二次方，即 hash(key)+0， hash(key)+1^2， hash(key)+2^2，hash(key)+3^2………

3.1.3双重散列

所谓的双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数hash1(key)， hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

比如先用除余发现此位置有元素，再用平方法

3.2链表法

在散列表中，数组的每个下标位置我们可以称之为“桶（bucket） ”或者“槽（ slot） ”，每个桶(槽)会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

4.应用（HashMap底层解析）

HashMap 的数据结构图 :

hashmap

面试必问：

jdk1.8 中关于 HashMap 的实现跟 jdk1.7 的几点差别：

1.数据结构引入了红黑树，好处是可以提高查询效率(jdk1.7 中极端情况下查询是 O(n)，如果引入红黑树在极端情况下的查询可以降低为 O(log n))，当散列表某一桶内链表节点数>=8 时链表树化成红黑树，红黑树太小时退化成链表，退化的阈值为 6

2.计算 key 的 hash 值的方式不一样，但是思路和原理一样都是对 key 的hashCode 进行扰动让高位和低位一起参与运算计算出更加均匀的 hash 码，降低hash 冲突的概率。

3.插入数据时如果发送了 hash 冲突，优先判断该位置上是否是红黑树，如果是则存入红黑树中，如果是链表则插入链表尾节点上(jdk1.7 是插入到链表头节点上)，插入完成后还判断链表的节点数是否大于等于设定好的链表转红黑树的阈值，如果满足则将链表转换为红黑树。

4.两个版本都会产生扩容操作，只不过 jdk1.8 中扩容涉及到对红黑树的操作以及优化了在 hash 冲突时计算元素新下标的代码，使其非常简单高效！

5.哈希算法

5.1定义

哈希算法又称为摘要算法，它可以将任意数据通过一个函数转换成长度固定的数据串，这个映射转换的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。可见，摘要算法就是通过摘要函数 f()对任意长度的数据 data 计算出固定长度的摘要 digest，目的是为了发现原始数据是否被人篡改过。

摘要函数是一个单向函数，计算 f(data)很容易，但通过 digest 反推 data 却非常困难。而且，对原始数据做
一个 bit 的修改，都会导致计算出的摘要完全不同。

那有没有可能两个不同的数据通过某个摘要算法得到了相同的摘要呢？完全有可能！因为任何摘要算法都是把无限多的数据集合映射到一个有限的集合中。这种情况就是我们说的碰撞。

5.2要求

将任何一条不论长短的信息，计算出唯一的一摘要(哈希值)与它相对应，对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同
摘要的长度必须固定，散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小
摘要不可能再被反向破译。也就是说，我们只能把原始的信息转化为摘要，而不可能将摘要反推回去得到原始信息，即哈希算法是单向的
哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

树

1.概念

1.1定义

树在维基百科中的定义为：，树（英语： Tree）是一种无向图（undirected graph），其中任意两个顶点间存唯一一条路径。或者说，只要没有回路的连通图就是树。在计算机科学中，树（英语： tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

1.2高度，深度及层

节点的高度：节点到叶子节点的最长路径(边数)，所有叶子节点的高度为 0。
节点的深度：根节点到这个节点所经历的边的个数，根的深度为 0。
节点的层数：节点的深度+1
树的高度：根节点的高度

2.二叉树

2.1定义

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

2.2为什么偏偏把最后一层的叶子节点靠左排列的叫完全二叉树

想要存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

链式存储法：

lianshi

顺序存储法：

根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置。

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

shunxu1

如果不按靠左排列

shunxu2

这样无疑多浪费了很多内存空间

如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

2.3二叉树的遍历

前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

二叉树的前序，中序，后序遍历是一个递归的过程，比如前序遍历，就是先答应根节点，然后递归的打印其左子树，然后递归的打印其右子树。

通过我们分析的二叉树的遍历流程我们可以发现，遍历二叉树的时间复杂度跟二叉树节点的个数 n 成正比，因此， 二叉树遍历的时间复杂度是 O(n)。

3.二叉查找树

3.1结构及特点

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值，有如下四个特点：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

3.2查找操作

准备工作：

public class Node {

    public int value;
    public Node left;
    public Node right;
    public Node(Node left,int value, Node right) {
        super();
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
}
private Node createNode(Node left,int value,Node right) {
    return new Node(left, value, right);
}

private Node createNode(int value) {
    return createNode(null, value, null);
}

我们从根节点开始，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

/**
	 * 查找
	 * @param value
	 * @return
	 */
public Node find(int value) {
    Node parent = tree;
    while(parent!=null) {
        if(parent.value>value) {
            parent = parent.left;
        }else if(parent.value<value) {
            parent = parent.right;
        }else {
            return parent;
        }
    }
    return parent;
}

3.3插入操作

从根节点开始依次比较要插入的数据和节点的数据的大小并以此来判断是将数据插入其左子树还是右子树，如果节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

/**
	 * 插入
	 * @param value
	 * @return
	 */
public boolean put(int value) {
    if(tree==null) {
        tree = createNode(value);
        return true;
    }
    Node parent = tree;//临时父节点用来遍历
    while(parent!=null) {
        if(parent.value>value) {
            //存储于左子树
            if(parent.left==null) {
                parent.left = createNode(value);
                return true;
            }
            parent = parent.left;
        }else if(parent.value<value) {
            //存储于右子树
            if(parent.right==null) {
                parent.right = createNode(value);
                return true;
            }
            parent = parent.right;
        }
    }
    return false;
}

3.4删除操作

3.4.1原理

删除有三种情况：

要删除的节点是叶子节点即没有子节点，我们只需将父节点中指向该节点的指针置为 null 即可，这是最简单的一种形式。
要删除的节点只有一个子节点(只有左子节点或者只有右子节点)，我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
要删除的节点有两个子节点，这是最复杂的一种情况，我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。

3.4.2代码实现

/**
 * 删除
 * @param value
 */
public void remove(int value) {
    Node p = tree;//记录要删除的结点
    Node p_parent = null;//记录要删除节点的父节点
    //寻找要删的元素及其父元素
    while(p!=null) {
        if(p.value>value) {
            p_parent = p;
            p = p.left;
        }else if(p.value<value) {
            p_parent = p;
            p = p.right;
        }else {
            break;
        }
    }
    if(p==null) {
        return;//没有找到则返回
    }
    //要删除的节点有两个子节点 这种情况要用右子树中最小节点的值替换当前要删除元素的值，然后删除右侧最小节点
    if(p.left!=null&&p.right!=null) {
        //找到该节点右子树的最小节点----->最左侧的叶子节点
        Node rightTree = p.right;
        Node rightTree_parent = p;
        while(rightTree.left!=null) {
            rightTree_parent = rightTree;
            rightTree = rightTree.left;
        }
        //右子树中最小的节点替换当前要删除的节点
        p.value = rightTree.value;
        //删除右子树中最小的节点,这里可以直接把问题替换成第1，2种要删除的结点没有子节点或者只有右节点的情况
        p = rightTree;
        p_parent = rightTree_parent;
    }
    //删除节点是叶子节点或者仅有一个子节点,都是要删除该节点，将父节点的指针指向当前节点的子节点
    Node child = null;//要删除的元素的子节点
    if(p.left!=null) {
        child = p.left;
    }else if (p.right!=null) {
        child = p.right;
    }else {
        child = null;
    }
    //执行删除
    if(p_parent==null) {//要删除根节点
        tree = child;
    }else if (p_parent.left==p) {
        p_parent.left = child;
    }else {
        p_parent.right =child;
    }
}

3.5其他零碎

后继节点：该节点右子树中最小的节点

前驱节点：该节点左子树中最大的节点

如果中序遍历二叉查找树，能够得到一个有序的数据序列，时间复杂度是 O(n)，非常的高效，因此二叉查找树也叫二叉排序树

在实际的软件开发中我们一般都是存储的包含很多属性的对象，判断的时候利用对象中的某一个属性进行判断，对象中的其他属性我们称为卫星数据，对于有重复数据的二叉查找树，我们应该如何存储和查找呢？有两种方案：

二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理，当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

3.6时间复杂度分析

对于图中第一种情况属于最坏的情况，二叉查找树已经退化成了链表，左右子树极度不平衡，此时查找的时间复杂度肯定是 O(n)。

对于图中第二种或者第三种情况是属于一个比较理想的情况，我们代码的实现逻辑以及图中所示表明插入，查找，删除的时间复杂度其实和树的高度成正比，那也就是说时间复杂度为 O(height)

3.7和散列表对比

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？个人认为原因如下：

散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能也不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)
尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

4.AVL树（平衡二叉树）

4.1概念

平衡二叉查找树：简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。

平衡二叉树必须符合如下俩个性质：

可以是空树。
假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

对于给定结点数为 n 的 AVL 树，最大高度为 O(log2n)。也就说，从 n 个数中，查找一个特定值时，最多需要 log2n 次。因此， AVL 是一种特别适合进行查找操作的树。

4.2失衡的四种情况及调整方法

在平衡二叉树中，当我们插入新的元素时，为了保证二叉搜索树的特性，很容易导致某些结点失衡，即该结点的平衡因子大于 1。而在二叉树中，任意结点孩子最多只有左右两个，而且导致失去平衡的必要条件就是当前结点的两颗子树的高度差等于 2。因此，致使一个结点失衡的插入操作有以下 4种。

在结点的左子树的左子树插入元素,LL 插入；
在结点的左子树的右子树插入元素,LR 插入；
在结点的右子树的左子树插入元素,RL 插入；
在结点的右子树的右子树插入元素,RR 插入。

需要注意的是，LL(二）中，结点 3 插入同样导致结点 8 失衡，这里需要注意子树是从受影响的结点算起，虽然 3 插在了右边，但他依旧是在 8（失衡结点）左子树的左子树上，因此属于 LL 插入。

4.2.1定义 AVL 树的结构(Comparable接口介绍)

AVL 树首先是二叉查找树，因此它的结点也必须是可比较。同时为了方便，加入一个表示当前结点高度的 height 字段，同时定义了返回节点高度和树的高度的方法，也定了一个返回两个高度中最大高度的方法。

public static class AvlNode<T extends Comparable> {
	private T data;
	private AvlNode<T> left;
	private AvlNode<T> right;
	private int height;

	public AvlNode(T data, AvlNode<T> left, AvlNode<T> right, int height) {
		super();
		this.data = data;
		this.left = left;
		this.right = right;
		this.height = height;
	}

	public AvlNode(T data, AvlNode<T> left, AvlNode<T> right) {
		this(data, left, right, 0);
	}

	public AvlNode(T data) {
		this(data, null, null);
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public AvlNode<T> getLeft() {
		return left;
	}

	public void setLeft(AvlNode<T> left) {
		this.left = left;
	}

	public AvlNode<T> getRight() {
		return right;
	}

	public void setRight(AvlNode<T> right) {
		this.right = right;
	}

	public int getHeight() {
		return height;
	}

	public void setHeight(int height) {
		this.height = height;
	}
}

其中，这里的Comparable接口大家可能不大熟悉，我来介绍一下：

官方文档说明：

此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。

实现此接口的对象列表（和数组）可以通过 Collections.sort)（和 Arrays.sort)）进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。
1
2
>int compareTo(T o)
>比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。 

我的理解：

当一个类实现了Comparable接口，里面实现了compareTo方法，就按照某种规则能够进行排序。

4.2.2LL旋转

/**
 * LL旋转
 * 
 * @param node失衡结点
 * @return左旋后的根节点
 */
public AvlNode leftRotate(AvlNode node) {
	// 临时变量，失去了结点的左子树，该节点也是左旋后的根子树
	AvlNode node_left = node.left;
	// 将失衡节点左子树的右子树作为失衡节点的左子树
	node.left = node_left.right;
	// 将失衡节点作为旋转后根节点的右子树
	node_left.right = node;
	// 重新计算失衡节点和旋转后根节点的高度
	node.height = getMax(height(node.left), height(node.right)) + 1;
	node_left.height = getMax(height(node_left.left), height(node)) + 1;
	return node_left;
}

4.2.3RR旋转

/**
 * RR旋转
 * 
 * @param node失衡结点
 * @return右旋后的根节点
 */
public AvlNode rightRotate(AvlNode node) {
	AvlNode node_right = node.right;
	node.right = node_right.left;
	node_right.left = node;
	node.height = getMax(height(node.left), height(node.right)) + 1;
	node_right.height = getMax(height(node_right.right), height(node)) + 1;
	return node_right;
}

4.2.4LR旋转

/**
 * LR旋转
 * 
 * @param node失衡结点
 * @return旋后的根节点
 */
public AvlNode leftRightRotate(AvlNode node) {
	// LR 旋转可以拆分为一次 RR 旋转和一次 LL 旋转来完成
	node.left = rightRotate(node.left);
	return leftRotate(node);
}

4.2.5RL旋转

/**
 * RL旋转
 * 
 * @param node失衡结点
 * @return旋后的根节点
 */
public AvlNode rightLeftRotate(AvlNode node) {
	// LR 旋转可以拆分为一次 LL 旋转和一次 RR 旋转来完成
	node.right = leftRotate(node.right);
	return rightRotate(node);
}

4.3插入操作

/**
 * 插入操作
 * 
 * @param value
 */
public void insert(T value) {
	this.tree = insert(tree, value);
}

private AvlNode insert(AvlNode node, T data) {
	// 将data添加到node子节点上
	if (node == null) {
		node = new AvlNode<T>(data);
	} else {
		int compared = data.compareTo(node.getData());
		if (compared > 0) {// 要添加的值大于当前节点的值,将 data 存储到当前节点的右子树上 递归的插入
			node.right = insert(node.right, data);
			// 如插入后 avl 树变得不平衡,则应该重新调节该树的结构---旋转
			if (height(node.right) - height(node.left) == 2) {
				// 判断是RR还是RL
				if (data.compareTo(node.right.getData()) > 0) {
					// RR
					node = rightRotate(node);
				} else {
					// RL
					node = rightLeftRotate(node);
				}
			}
		} else if (compared < 0) {// 插左子树
			node.left = insert(node.left, data);
			if (height(node.right) - height(node.left) == 2) {
				// 判断是LL还是LR
				if (data.compareTo(node.right.getData()) > 0) {
					// LR
					node = leftRightRotate(node);
				} else {
					// LL
					node = leftRotate(node);
				}
			}
		} else {
			// 要添加的值和该节点的值相同，不做处理
		}
	}
	// 计算结点node的高度
	node.height = getMax(height(node.left), height(node.right)) + 1;
	return node;
}

结语

愿中国青年都摆脱冷气，只是向上走，不必听自暴自弃者流的话，能做事的做事，能发声的发声，有一分热，发一分光，就令萤火一般，也可以在黑暗里发一点光，不必等候炬火，此后如竟没有炬火，我便是唯一的光。

——鲁迅《热风，随感录四十一》

概述

散列表

1.概念

2.散列函数

2.1散列函数的要求及特点

2.2散列函数的设计方法

2.2.1直接寻址法：

2.2.2除留余数法

2.2.3平方取中法

2.2.4折叠法

2.3散列冲突

3.散列冲突的解决方案

3.1开放寻址法

3.1.1线性检测 ：

3.1.2二次检测

3.1.3双重散列

3.2链表法

4.应用（HashMap底层解析）

面试必问：

5.哈希算法

5.1定义

5.2要求

树

1.概念

1.1定义

1.2高度，深度及层

2.二叉树

2.1定义

2.2为什么偏偏把最后一层的叶子节点靠左排列的叫完全二叉树

2.3二叉树的遍历

3.二叉查找树

3.1结构及特点

3.2查找操作

3.3插入操作

3.4删除操作

3.4.1原理

3.4.2代码实现

3.5其他零碎

3.6时间复杂度分析

3.7和散列表对比

4.AVL树（平衡二叉树）

4.1概念

4.2失衡的四种情况及调整方法

4.2.1定义 AVL 树的结构(Comparable接口介绍)

4.2.2LL旋转

4.2.3RR旋转

4.2.4LR旋转

4.2.5RL旋转

4.3插入操作

结语

3.1.1线性检测：