一、什么是平衡二叉树

1.概述

平衡二叉树（AVL树）是一种带有平衡条件的二叉搜索树。它的特性如下：

• AVL树的左右两个子树的高度差的绝对值不超过1
• AVL树的左右两个子树都是一棵平衡二叉树

举个例子，如上图所示：

• 第一棵树左树高2，右树高1，差值为1，是一颗AVL树；
• 第二棵树左树高2，右树高2，差值为0，是一颗AVL树；
• 第三棵树左树高3，右树高1，差值为2，不是一颗AVL树；

红黑树就是一直AVL树。

2.为什么需要平衡二叉树

当我们使用二叉排序树的时候，当连续插入顺序的节点的时候就会出现问题。比如，我们插入{1,2,3,4,5}这样一个数组：

一、什么是二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树、二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

当我们使用需要对数列进行操作的时候，我们原本有以下选择：

• 数组：不排序的数组插入快而查找慢，排序数组通过算法可以快速查找，但是插入效率又会受到影响
• 链表：不管是否有序，插入都快，但是查找效率都不高
• 哈希表：查找修改都简单，但当哈希冲突严重的时候传统哈希表效率也会下降

而二叉排序树的查找类似二分查找，而插入类似链表，相较以上三种结构可以较好的平衡查找和插入效率

二、代码实现

我们先实现一个节点类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * @Author：CreateSequence
 * @Date：2020-07-20 11:27
 * @Description：二叉排序树节点
 */
public class BinarySortTreeNode {

    int val;
    BinarySortTreeNode left;
    BinarySortTreeNode right;

    public BinarySortTreeNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "{" +
                "val=" + val +
                '}';
    }
}

再实现一个二叉排序树类：

一、什么是赫夫曼编码

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，

使用赫夫曼编码可以有效的压缩数据，通常可以节省20%~90%的空间。

在理解赫夫曼编码前，我们需要对通讯领域的两种编码方式有个粗略的了解。

假设我们需要传输 I'm a jvav programmer and I love programming这样一句话，我们有两种传输方式：

1. 定长编码

   直接转换为对应长度的二进制格式

   1	01101111 00100000 00100000 00100000 00100111 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100111 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000 00100000

   总长度为296个字符

2. 变长编码

   按照各个字符出现的次数进行编码，按出现次数编码，出现次数越多的，则编码越小：

   比如空格出现最多次，然后是a，以此类推......

   1	0= ，1=a，10=i，11=o......

   当传输的信息越多的时候，变长编码实际传输的长度相对定长编码就越小

另外，我们还需要了解一下什么是补码：

计算机里面只有加法器，没有减法器，所以减法必须用加法来完成。 对于 100 以内的十进制数，“-1”就可以用"+99"代替。比如 25 － 1 ＝ 24，可以写成 25 ＋ 99 ＝ (1)24。 如果限定了两位数，那“-1”和“+99”就是等效的。同样，“-2”可以用“+98”代替。

它们之间，称为补数，而100就称为模。

对于8位二进制数：0000 0000~1111 1111(255)，模为256。 －1，可以用 +255(1111 1111)代替。 －2，可以用 +254(1111 1110)代替

这些二进制数，就称为负数的补码

二、赫夫曼编码思路

同样举个例子，我们要传输 i like like like java do you like a java这段话

一、什么是赫夫曼树

给定n个权值作为n个叶子节点，构造一课二叉树，若该树的带权路径长度和（wpl）达到最小，称这样的二叉树为最优二叉树，也就是赫夫曼树。

要理解这句话，我们需要了解几个关键词：

• 路径：从一个节点往下一个节点之间的通路。若根节点层数为1，则根节点通往L层的节点路径长度为L-1
• 带权路径：权可以理解为节点值，而从根节点到某节点之间的路径长度与该点的权的成绩称为带权路径长度

举个例子：

如上图所示，节点13到根节点的路径长度是2，而权是13，所以带权路径长度就是2*13=26，同理，节点7的带权路径长度是14，8是16,3是6，最终该树的带权路径长度之和（wpl）就是26+14+16+6=62。

而该树与上图有相同的叶子节点，但是wpl却是13+16+21+9=59，这是拥有这几个相同叶子节点的树里面wpl最小的，所以这颗树就是一颗赫夫曼树。

我们不难看出，赫夫曼树最大的特点：权越大的节点越靠近根节点

一、什么是堆排序

1.堆，堆排序

对于“堆”我们可以理解为具有以下性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
• 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

在排序时，一般升序采用大顶堆，降序采用小顶堆。

2.大顶堆

我们可以看到，层数从小到大，节点的数字是越来越小的，映射到数组有：{50,45,40,20,25,35,30,10,15}

特点是arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]

一直都用博客园写博客，后面自己曾经想自己写一个博客项目，但是因为各种各样的事情最后做了一半就没能继续做下去。但是中间定制markdawn样式的时候接触到的代码高亮插件highlight.js倒是给我留下了很深的影响，今天有时间于是决定利用当初的经验重新diy一下博客园的代码块样式，算是对夭折的博客项目的一个弥补吧。

一、下载highlight.js

可以去highlight.js官网直接下载。

下载完的文件里有highlight.pack.js，决定你的代码哪里高亮，而styles文件夹存放各种样式，决定你的代码怎么样高亮。

按照官网文档引入三行代码即可生效：

1
2
3
4
5

<!--选择你想要的引入的样式-->
<link rel="stylesheet" href="/path/to/styles/default.css">
<!--引入highlight.js-->
<script src="/path/to/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>

可以自己建一个页面试一试，样式有很多种，我个人比较喜欢darcula.css这个样式，接下来就以这个样式为例。

二、将样式引入博客园

首先自定义css需要开通自定义权限，这个跟着流程来即可，我就不再赘述了。

一、什么是二叉树

1.概述

首先，需要了解树这种数据结构的定义：

树：是一类重要的非线性数据结构，是以分支关系定义的层次结构。每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树

树的结构类似现实中的树，一个父节点有若干子节点，而一个子节点又有若干子节点，以此类推。

2.名词解释

3.二叉树

二叉树就是每个节点最多只有两颗子树的树：

一、什么是哈希表

1.概述

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度这个映射函数叫做散列函数，存放记录的数组叫做散列表。

通俗的理解一下：

• 如果我们有n个元素要存储，那我们就用l个内存单元来存储他们
• 然后我们有一个哈希函数f(x)，我们把元素n用函数计算得到哈希值，也就是f(n)
• f(n)就是存储元素n的那个内存单位的位置，也就是元素在l中的下标

2.为什么哈希表查询速度快

理解了哈希表的基本思路，我们也就不难理解为什么哈希表查询效率高了：

由于每个元素都能通过哈希函数直接计算获得地址，所以查找消耗时间非常少。

举个例子：

什么是查找？

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。

定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

分类：

1. 静态查找和动态查找
   • 静态查找：不对表的数据元素和结构进行任何改变。
   • 动态查找：在查找过程同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
2. 无序查找和有序查找。
   • 无序查找：被查找数列有序无序均可
   • 有序查找：被查找数列必须为有序数列。

一、线性查找

遍历数组并且依次对比值，相等时返回下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * 在给定数组中线性查找指定元素
 * @param arr
 * @param target
 * @return
 */
public static int search(int[] arr,int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

二、二分查找

1.思路分析

什么是排序？

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

1.排序的分类

排序分为两类：

• 内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
• 外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

一般来说，外部排序只有数据量极大时会使用，一般情况下排序指的都是内部排序。

2.空间复杂度

1.类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。

2.空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

3.在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间。

3.排序的稳定