堆排序
堆排序概述
假如一颗完全二叉树有如下性质：每个节点的值都大于等于（或者小于等于）它左右孩子节点的值，那么这种完全二叉树就可以称为堆
堆还分为大顶堆和小顶堆
- 大顶堆：每个节点的值都大于等于其左右子节点的值（左右子节点之间没有大小的规定）
- 小顶堆：每个节点的值都小于等于其左右子节点的值（左右子节点之间没有大小的规定）
我们知道二叉树可以将树进行顺序存储，转换为数组之后，在这里面，i的值就是数组的下标，从0开始
堆排序是利用堆这种数据结构而设计的一种排序算法，它是一种选择排序，他的最好、最坏、平均时间复杂度都为O(nlogn)，它是不稳定排序
一般我们使用升序方式排列一般使用大顶堆，降序方式排列一般使用小顶堆
堆排序的思想
堆排序的基本思路
1、将待排序的序列构建成为一个大顶堆（注意这个大顶堆是数组，只不过顺序是按照二叉树的顺序化来进行的）
2、此时，整个序列的最大值就是堆顶的根节点
3、将其与末尾元素进行交换，此时末尾元素就为最大值
4、然后将剩余的n-1个元素重新构建成一个大顶堆，这样会得到n个元素的次小值，如此反复执行，便能够得到一个有序序列
可以看到，在构建成一个大顶堆的过程中，元素的个数逐渐减小，最后就得到一个有序序列了
堆排序图解
假如现在有一个数组：int[] arr = { 4 , 6 , 8 , 5 , 9 }，要求将这个数组进行升序排列
那么我们为了易于理解，我们分别画出它的数组形式和它对应的树形式
为了进行堆排序（升序排序），我们要做一些准备工作：首先就是将这个数组/这棵树构建成一个大顶堆
构建成一个大顶堆需要以下步骤：
1、根据从上到下，从左到右的顺序，找到最后一个非叶子节点，也就是节点6
怎么找到的呢，这是因为它有一个规律：
假设当前节点的索引为n，那么它的父节点 parent 的索引为：
parent = (n - 1) / 2它的左子节点child的索引为：
leftChild = （ 2 * n） + 1它的右子节点child的索引为：
rightChild = ( 2 * n ) + 2那么我们知道节点的个数，也就是最后节点的索引，直接找到最后的非叶子节点就是找到最后节点索引的父节点
还有，最后一个非叶子节点就是数组的最后一个索引（不是长度）减一除以二，也就是
(arr.length() - 2) / 2
2、使用这个节点与其左右子节点进行比较，在这三个节点里面找到一个最大的，然后将这个最大的节点和节点6进行交换
3、向上继续进行第二步，那这一步就是4、9、8这三个节点进行比较
4、这样就出现一个问题，4和9进行交换之后，4、5、6这三个节点又不是大顶堆模式了，所以要继续改变这三个节点
5、这样构建成一个大顶堆就完成了，那么我们继续进行排序
大顶堆的排序
1、将大顶堆的根节点与末尾元素进行交换，这里就是9和4，在数组上对应的是首元素和尾元素，在树中对应的是前序遍历中的首元素和尾元素
2、将沉底的元素排除，在剩下的元素中重新构建大顶堆，然后进行排序
最后总结：应当的顺序是这样的：
给个建议，假如你上面的写对了，那么试一下下面这个是否能够成功：
代码实现
最后上代码
/**
* 要进行排序的数组
*
* @param arr
*/
public static void sortHeap(int[] arr) {
if (arr == null || arr.length == 1) {
System.out.println("数组元素个数大于1才有排序的意义");
return;
}
// 初始化真实数组的长度为原有的长度
int length = arr.length;
// 当真实数组的长度大于1的时候才有排序的意义
while (length > 1) {
/*
* 初始化index，算出最后一个非叶子节点的下标
* 因为我们是按照索引来进行-1之后算出来的
* 所以最后的非叶子节点的下标应该是长度-2
*/
int index = (length - 2) / 2;
while (index >= 0) {
// 大顶堆排序
adjustHeap(arr, index, length);
// 令index走到它的前一个非叶子节点，进行大顶堆排序
index--;
}
// 排序，将最大的数值和最小的数值交换位置，将最大的数值放到最后
arr[0] = arr[0] + arr[length - 1];
arr[length - 1] = arr[0] - arr[length - 1];
arr[0] = arr[0] - arr[length - 1];
// 真实排序的数组长度-1，将最大的数值排除
length--;
}
}
/**
* 将树排列为堆
*
* @param arr 要排列的数组
* @param index 最后一个非叶子节点的下标
* @param length 真实排列的数组的长度
*/
public static void adjustHeap(int[] arr, int index, int length) {
// 左子节点的下标
int leftChild = 2 * index + 1;
// 右子节点的下标
int rightChild = 2 * index + 2;
/*
* 假如右子节点的下标在length范围内
* - 假如右子节点的下标在范围内， 那么说明左子节点和右子节点都在范围内，那么进行左右节点的比较
* - 假如右子节点 >= 左子节点
* - 右子节点与index节点进行比较
* - 右子节点比index节点大，那么交换（交换完成之后向右递归进行右子节点的大顶堆排序），否则不处理
* - 假如右子节点 < 左子节点，那么左子节点与index节点比较
* - 左子节点比index节点大，那么交换并进行左子节点的大顶堆排序，否则不处理
* - 假如右子节点的下标不在范围内，那么判断左子节点是否在范围内
* - 假如左子节点不在范围内，那么直接进行返回
* - 假如左子节点在范围内，那么进行左子节点的比较
* - 左子节点比index节点大，那么交换并进行左子节点的大顶堆排序，否则不处理
*/
if (rightChild <= length - 1) {
if (arr[rightChild] >= arr[leftChild]) {
if (arr[rightChild] > arr[index]) {
arr[index] = arr[index] + arr[rightChild];
arr[rightChild] = arr[index] - arr[rightChild];
arr[index] = arr[index] - arr[rightChild];
adjustHeap(arr, rightChild, length);
}
} else {
if (arr[leftChild] > arr[index]) {
arr[index] = arr[index] + arr[leftChild];
arr[leftChild] = arr[index] - arr[leftChild];
arr[index] = arr[index] - arr[leftChild];
adjustHeap(arr, leftChild, length);
}
}
} else if (leftChild <= length - 1) {
if (arr[leftChild] > arr[index]) {
arr[index] = arr[index] + arr[leftChild];
arr[leftChild] = arr[index] - arr[leftChild];
arr[index] = arr[index] - arr[leftChild];
adjustHeap(arr, leftChild, length);
}
}
}
赫夫曼树
赫夫曼树概述
几个概念
首先要明白几个概念我们才可以向下进行理解
1、路径和路径长度
2、节点的权（权值）和节点的带权路径长度
3、树的带权路径长度
假如现在有一颗树
路径十分好理解，我们之前讲树的术语时讲过，路径就是根节点到当前节点的通路
比如说当前节点是索引为6的节点，那么路径应当为：0->1->3
路径的长度其实就是走的步数，在上面就是2
其实简单点讲，假如现在一个节点位于第L层，那么路径的长度就是L-1
节点的权其实就是节点的值，比如索引为0的根节点，它的值就是2，权（权值）就是2
节点的带权路径长度，就是说把节点的权和节点的路径长度相乘得到的结果
比如说索引为7的节点，它的权为5，它的路径长度为3，那么它的带权路径长度就是3 * 5 = 15
树的带权路径长度（WPL）就更好理解了，就是把所有叶子节点的带权路径长度相加
下面是几个例子：
什么是赫夫曼树
在理解了上面的内容之后，我们来看赫夫曼树
赫夫曼树，也叫做哈夫曼树、霍夫曼树等等，因为中文翻译的问题不太精确。
赫夫曼树有如下几个特点：
1、必须是二叉树
2、二叉树的所有叶子节点必须有权值
3、树的带权路径长度必须最小
比如上面这几张图，其中第二个的WPL最小，并且无论再怎么排列都不可能比它小了，那么它就是赫夫曼树
4、赫夫曼树的权值较大的节点离根很近
赫夫曼树的创建
赫夫曼树创建步骤说明
赫夫曼树的创建步骤
1、将给定的数列从小到大进行排序，每一个数据都可以看成一个节点，每一个节点都可以看成一颗二叉树
假如是一开始，那么每一个节点都可以看成一个没有左右子树的树，一个空荡荡的光杆司令
2、取出根节点权值最小的两颗二叉树
3、将取出的两颗二叉树组成一颗新的二叉树，这颗新的二叉树的根节点的权是两颗二叉树根节点的权
4、将这颗新的二叉树和原本的那些二叉树再次组成排序，不断重复1-4的步骤，直到所有数据被处理，得到赫夫曼树
赫夫曼树创建步骤图解
假如现在有一棵数列：{13,7,8,3,29,6,1}
1、首先进行排序：1,3,6,7,8,13,29
2、取出最小的，也就是1和3，组成一颗新的树，并进行排序
3、取出最小的，也就是4和6，组成一颗新的树，并进行排序
4、取出最小的，也就是7和8，组成一颗新的树，并进行排序
5、取出最小的，也就是10和13，组成一颗新的树，并进行排序
6、取出最小的，也就是15和23，组成一颗新的树，并进行排序
7、取出29和38，得到最终的赫夫曼树
赫夫曼树代码实现
/**
* 树节点，因为要对节点进行排序
* 为了省事直接继承Comparable接口
*/
class Node implements Comparable<Node> {
// 节点权值
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
/**
* 前序遍历树
*/
public void preOrder() {
// 打印当前节点
System.out.println(this);
// 向左遍历
if (this.getLeft() != null) {
this.getLeft().preOrder();
}
// 向右遍历
if (this.getRight() != null) {
this.getRight().preOrder();
}
}
@Override
public int compareTo(Node o) {
// 从小到大排序
return this.value - o.getValue();
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
public class HuffmanTreeDemo {
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node node = huffmanSort(arr);
node.preOrder();
}
private static Node huffmanSort(int[] arr) {
// 将数组转为Node集合
List<Node> nodeList = Arrays.stream(arr).mapToObj(e -> {
return new Node(e);
}).collect(Collectors.toList());
// 只要节点里面还有数据，那么就进行排序
while (nodeList.size() > 1) {
// 1、排序
Collections.sort(nodeList);
// 2、获取当前树的前两个（也就是最小的）
Node leftNode = nodeList.get(0);
Node rightNode = nodeList.get(1);
// 3、生成这两个节点的父节点
Node parent = new Node(leftNode.getValue() + rightNode.getValue());
parent.setLeft(leftNode);
parent.setRight(rightNode);
// 4、将生成的父节点替换掉两个子节点
nodeList.remove(leftNode);
nodeList.remove(rightNode);
nodeList.add(parent);
}
return nodeList.get(0);
}
}
赫夫曼编码
赫夫曼编码概述
通信领域的几种编码方式
在讲解赫夫曼编码之前，我们需要首先了解在通信领域中比较常用的编码方式，这样才能体会出赫夫曼编码的优越性
定长编码
我们来看定长编码
首先来看一组字符串：
i like like like java do you like a java
在上面这串字符串中，包括空格，一共有四十个字符，那么根据ASCII的翻译，i会被翻译为105，空格会被翻译为32，l会被翻译为108.....，所以它的最终结果应当是这样的：
105 32 108 105 107 101 32 108 105 107 101 32 108 105
107 101 32 10697 118 97 32 100 111 32 121 111 117 32
108 105 107 101 32 97 32 106 97 118 97
那么最终ASCII码要范围为0和1，比如105就会被翻译为01101001，那么最终它的编码方式是这样的：
0110100100000001101100 01101001 01101011 01100101 000000 01101100
01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101
001000000110101001100001 0111011001100001 00000001100100 01101111
000001111001 01101111 01110101 000000 0110110001101001 01101011
01100101 0000001100001 00100000 0110101001100001 0111011001100001
这些二进制的总长度是359（包括空格）
这就是通信方式之一，定长编码，是最垃圾的编码方式之一
变长编码
边长编码也是通信领域中信息的处理方式之一，我们还是以上面的那行字符串为例子：
i like like like java do you like a java
在这里，我们算上空格，统计出它们的长度
d：出现1次，y：出现1次，u：出现1次
j：出现2次，v：出现2次，o：出现2次
l：出现4次，k：出现4次，e：出现4次
i：出现5次，a：出现5次，空格：出现9次
根据上面的排序内容，从大到小排序
{空格,a,i,e,k,l,o,v,j,u,y,d}
那么从索引0开始算起
-
空格是索引0，转为二进制为0
-
a是索引1，转为二进制为1
-
i是索引2，转为二进制为10
-
e是索引3，转为二进制为11
-
......
那么字符串是i like like like java do you like a java
将上面的各种字符使用刚才我们转换的二进制来替换，最终的结果就是：
其中相同颜色的我们看成一个字符，比如i就是10
这就是变长编码的方式，但是这种方式有一个很大的问题，那就是不能够准确地区分最后应该如何解码
比如接收端接受到了这一串字符，它看到第一个是1，那么这个1有可能对应着a，也有可能会和后面的0组成10，对应i
上述这种情况我们叫做二意性：一个字符的编码是另一个字符编码的前缀，比如a是1，而i是10，那么a就是i的编码前缀
我们想要做的就是将这种二意性干掉，那种编码被称为前缀编码
赫夫曼编码
赫夫曼编码概述
- 赫夫曼编码也被称为哈夫曼编码、霍夫曼编码，也是通信领域中的一种编码方式
- 赫夫曼编码是一种编码方式，是一种算法
- 赫夫曼编码广泛应用于数据文件的压缩中，它的压缩率通常在20%-90%之间
- 赫夫曼编码是可变字长编码（VLC）的一种，是赫夫曼在1952年提出的一种编码方式，被称为最佳编码
赫夫曼编码步骤
赫夫曼编码要经历以下的几个步骤
1、得到传输的字符串：
i like like like java do you like a java
2、统计上面字符出现的次数
d：出现1次，y：出现1次，u：出现1次
j：出现2次，v：出现2次，o：出现2次
l：出现4次，k：出现4次，e：出现4次
i：出现5次，a：出现5次，空格：出现9次
3、根据这个字符出现的次数构建一颗赫夫曼树，权值作为次数，我们还可以在节点中加一个属性存放字符
这里注意，根据你排序的方式不同，最终形成的赫夫曼树也有所不同，但是WPL是相同的，这个是133
4、根据赫夫曼树，给每一个叶子节点规定编码，我们规定，从根节点开始，向左的路径为0，向右的路径为1，那么它们的路径如下：
e:000
j:0010
v:0011
空格:01
......
5、根据上面的赫夫曼编码，我们的i like like like java do you like a java的字符串编码为：
1010100101110111010011111110101111110000110001110011011110011001111001001010111011101100000110001110
赫夫曼编码特性
1、赫夫曼编码是前缀编码，也就是说它没有二意性，所以赫夫曼编码能够无损编码
2、赫夫曼编码方式的压缩率是很恐怖的，原来的编码是359，现在是133，整整压缩了62.9%
3、根据生成赫夫曼树的不同，编码方式也有所不同，但是WPL是一样的
赫夫曼编码的实现
将发送的数据转为赫夫曼树
/**
* 赫夫曼树的节点类，因为要排序所以继承Comparable接口
*/
class Node implements Comparable<Node> {
// 节点的真实值，由字符转来
private Byte value;
// 节点的权值
private Integer weight;
// 左右节点
private Node left;
private Node right;
public Node(Byte value, Integer weight) {
this.value = value;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
// 根据权重，从小到大进行排序
return this.weight - o.weight;
}
/**
* 前序遍历
*/
public void preOrder() {
// 输出本节点内容
System.out.println(this.toString());
// 向左遍历
if (this.left != null) {
this.left.preOrder();
}
// 向右遍历
if (this.right != null) {
this.right.preOrder();
}
}
}
/**
* 赫夫曼编码实现
*/
public class HuffmanTreeCodeDemo {
public static void main(String[] args) {
getNodeTree("i like like like java do you like a java").preOrder();
}
/**
* 将要进行编码的字符串传递进来，转换成一颗哈夫曼树
*
* @param str 要进行编码的字符串
* @return 一颗哈夫曼树的根节点
*/
public static Node getNodeTree(String str) {
// 将字符串转换为Node集合
List<Node> nodeList = getNodes(str);
// 将Node集合变为哈夫曼树
while (nodeList.size() > 1) {
// 1、首先进行排序
Collections.sort(nodeList);
// 2、取出最小的两个节点
Node leftNode = nodeList.get(0);
Node rightNode = nodeList.get(1);
/*
* 3、给最小的两个节点创造一个父节点
* 父节点有权值但是没有实际的值
*/
Node parent = new Node(null, leftNode.getWeight() + rightNode.getWeight());
parent.setLeft(leftNode);
parent.setRight(rightNode);
// 4、将两个子节点删除并将父节点添加进去
nodeList.remove(leftNode);
nodeList.remove(rightNode);
nodeList.add(parent);
}
return nodeList.get(0);
}
/**
* 将字符串转换为Node节点并返回
*
* @param str 传递进来的字符串
* @return 返回Node集合
*/
private static List<Node> getNodes(String str) {
if (str == null || "".equals(str)) {
throw new RuntimeException("字符串必须有意义");
}
/*
* 将字符串直接转换为byte数组
* 这个byte数组将会成为Node节点的value
*/
byte[] byteList = str.getBytes();
// 定义一个Map，用于统计字符串中每一个字符出现的次数
Map<Byte, Integer> countMap = new HashMap<>();
for (byte b : byteList) {
// 假如byte以前从未统计过，那么直接给他初始化，否则统计数加一
Integer count = countMap.get(b);
if (count == null) {
countMap.put(b, 1);
continue;
}
countMap.put(b, count + 1);
}
List<Node> nodeList = countMap.keySet()
.stream().map(b -> new Node(b, countMap.get(b))).collect(Collectors.toList());
return nodeList;
}
}
最后输出的结果应当是：叶子节点同时拥有权重和值，但是非叶子节点只有权重
生成赫夫曼编码表
前面在赫夫曼概述的时候我们已经说过了，从根节点到叶子节点，向左的路径我们规定为0，向右左的路径我们规定为1，那么根据这个条件，我们有如下代码
首先我们是根据上面生成的赫夫曼树来进行继续编写的，所以之前有的我在这里不做展示
并且在写代码之前要知道一件事情：赫夫曼编码表的内容和赫夫曼树的生成情况有关系，假如赫夫曼树生成是不同的，那么赫夫曼编码肯定也是不同的
那么如何判断赫夫曼树是否是正确的呢？我们的WPL是一致的，在这个数据中，带权节点路径的值为133
/**
* 赫夫曼树的节点类，因为要排序所以继承Comparable接口
*/
class Node implements Comparable<Node> {
// 节点的真实值，由字符转来
private Byte value;
// 节点的权值
private Integer weight;
// 左右节点
private Node left;
private Node right;
// 用于存放赫夫曼编码表的Map集合
private Map<Byte, String> huffmanCodes = new HashMap<>();
public Node(Byte value, Integer weight) {
this.value = value;
this.weight = weight;
}
/**
* 将赫夫曼树生成的赫夫曼编码存放到huffmanCodes集合中
*
* @param node 节点
* @param code 赫夫曼编码表的值
* @param builder 用于做赫夫曼编码表中路径的拼接
*/
public void getCodes(Node node, String code, StringBuilder builder) {
// 用于拼接路径
StringBuilder stringBuilder = new StringBuilder(builder);
stringBuilder.append(code);
// 假如node为空，说明这是一个叶子节点的下一个节点，直接返回不作处理
if (node == null) {
return;
}
// 因为我们的所有节点都有权值，但是只有叶子节点具有真实值，所以根据真实值就可以判断是否为叶子节点
if (node.value == null) {
// 向左递归处理，在我们赫夫曼中，向左路径为0
getCodes(node.left, "0", stringBuilder);
// 向右递归处理，在我们赫夫曼中，向右路径为1
getCodes(node.right, "1", stringBuilder);
}
// 假如到达了叶子节点
huffmanCodes.put(node.value, stringBuilder.toString());
}
}
/**
* 赫夫曼编码实现
*/
public class HuffmanTreeCodeDemo {
public static void main(String[] args) {
Node node = getNodeTree("i like like like java do you like a java");
node.getCodes(node, "", new StringBuilder());
Map<Byte, String> huffmanCodes = node.getHuffmanCodes();
// 赫夫曼编码表：{null=, 32=01, 97=100, 100=11000, 101=1110, 105=101, 106=0010, 107=1111, 108=000, 111=0011, 117=11001, 118=11011, 121=11010}
System.out.println("赫夫曼编码表：" + huffmanCodes);
}
}
注意，根据赫夫曼树的不同，生成的赫夫曼编码也是有所不同的
二叉排序（查找）树（BST）
二叉排序树概述
二叉排序树：Binary Sort（Search） Tree：BST，也有人叫做二叉查找树
它的要求是：对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小（或者相等），右子节点的值比当前节点的值大（或者相等）
比如一个数列：{7,3,10,12,5,1,9}
假如有相同的值，那么可以将这个节点放到左子节点或者右子节点即可
只要保证左子节点不大于父节点，右子节点不小于父节点即可
这样一来，中序遍历直接输出的就是有序的
二叉排序树的创建和遍历
/**
* 树节点
*/
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
/**
* 添加节点，需要满足二叉排序树的要求
*
* @param node 要添加的节点
*/
public void add(Node node) {
if (node == null) {
return;
}
/*
* 判断当前节点的值和父节点点值的关系
* 假如当前节点的值比父节点的值小，那么向父节点的左子节点进行比较
* - 假如父节点的左子节点为null，那么直接挂上
* - 假如父节点的左子节点不为null，那么递归判断
* 假如当前节点的值大于或等于父节点的值，那么向父节点的右子节点进行比较
* - 假如父节点的右子节点的值为null，那么直接挂上
* - 假如父节点的右子节点的值不为null，那么递归判断
*/
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
return;
}
this.left.add(node);
} else {
if (this.right == null) {
this.right = node;
return;
}
this.right.add(node);
}
}
/**
* 中序遍历
*/
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
/**
* 二叉排序树
*/
class BinarySearchTree {
// 根节点
private Node root;
/**
* 添加节点
*
* @param node 节点
*/
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
/**
* 中序遍历
*/
public void infixOrder() {
if (root == null) {
System.out.println("二叉排序树为null");
return;
}
root.infixOrder();
}
}
/**
* 二叉搜索树
*/
public class BinarySearchTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9};
BinarySearchTree binarySearchTree = new BinarySearchTree();
Arrays.stream(arr).mapToObj(Node::new).forEach(binarySearchTree::add);
binarySearchTree.infixOrder();
}
}
二叉排序树的删除
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑：
1、删除叶子节点（比如2、5、9、12）
2、删除只有一颗子树的节点（比如1）
3、删除有两颗子树的节点（比如7、3、10）
因为三种情况比较复杂，那么在这里进行一次深入的分析，当然这里指的是一切正常的情况，特殊情况暂时不考虑在内，为的就是心中先有个底
情况一：删除的是一个叶子节点
1、找到要删除的节点targetNode
2、找到要删除的节点的父节点parentNode
3、根据确定targetNode是parentNode的左子节点还是右子节点
- 假如targetNode是parentNode的左子节点：parent.left = null
- 假如targetNode是parentNode的右子节点：parent.right = null
情况二：删除的是只有一颗子树的节点
1、找到要删除的节点targetNode
2、找到要删除的节点的父节点parentNode
3、判断targetNode是parentNode的左子节点还是右子节点
3.1、假如targetNode是parentNode的左子节点，继续判断targetNode的子节点childNode是左子节点还是右子节点
- 假如childNode是targetNode的左子节点：parent.left = target.left
- 假如childNode是targetNode的右子节点：parent.left = target.right
3.2、假如targetNode是parentNode的右子节点，继续判断targetNode的子节点childNode是左子节点还是右子节点
- 假如childNode是targetNode的左子节点：parent.right = target.left
- 假如childNode是targetNode的右子节点：parent.right = target.right
情况三：删除的是有两颗子树的节点
1、找到要删除的节点targetNode
2、找到要删除的节点的父节点parentNode
3、在targetNode的rightChild中，找到一个值最小的节点temp和这个节点的父节点tempParent
4、判断temp.right是否有值
- 假如temp.right != null：tempParent.left = temp.right
- 假如temp.right == null：tempParent.left = null
5、temp.left = targetNode.left;
6、temp.right = targetNode.right;
7、判断targetNode是parentNode的左子节点还是右子节点
- 假如targetNode是parentNode的左子节点：parentNode.left = temp;
- 假如targetNode是parentNode的右子节点：parentNode.right = temp;
代码实现
/**
* 树节点
*/
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
/**
* 根据值搜索节点
*
* @param value 节点对应的值
* @return 节点
*/
public Node searchNode(int value) {
// 假如搜索的节点的值和当前节点的值相同，那么返回当前节点
if (this.value == value) {
return this;
}
// 假如搜索节点的值小于当前节点的值，那么说明应该向左递归
if (this.value > value && this.left != null) {
return this.left.searchNode(value);
}
// 假如搜索节点的值大于当前节点的值，那么说明应该向右递归
if (this.value < value && this.right != null) {
return this.right.searchNode(value);
}
return null;
}
/**
* 根据targetNode搜索parentNode
*
* @param node targetNode
* @return targetNode的父节点
*/
public Node searchParent(Node node) {
/*
* 注意，这里不应该再次判断根节点的值如何了，在调用这个方法之前应该早已经判断当前节点是否为root节点了
* 因为root节点是没有父节点的
*/
// 寻找targetNode的父节点并返回
if (this.left == node || this.right == node) {
return this;
}
if (node.value < this.value && this.left != null) {
return this.left.searchParent(node);
}
if (node.value > this.value && this.right != null) {
return this.right.searchParent(node);
}
return null;
}
/**
* 在指定的子树中，搜索一个最小的节点
*
* @return 最小的节点
*/
public Node searchTemp() {
if (this.left != null) {
return this.left.searchTemp();
}
return this;
}
}
/**
* 二叉排序树
*/
class BinarySearchTree {
// 根节点
private Node root;
/**
* 删除节点
*
* @param value 要删除节点的值
*/
public void delNode(int value) {
// 将要删除的目标节点
Node targetNode = this.root.searchNode(value);
// 判断目标节点是否为null
if (targetNode == null) {
throw new RuntimeException("指定的节点不存在!!");
}
/*
* 判断目标节点是否为root节点，假如是，那么有以下三种情况
*
* 1、假如当前root节点没有任何的子节点,那么直接置空，退出方法
* 2、root节点有一个子节点,root节点置为子树的根节点
* 3、root节点有两个子节点
* 3.1、在root节点的右子树找到一个最小的节点temp，并且找到temp的父节点tempParent
* 3.2、判断tempParent是否为root节点
* 3.2.1、 假如tempParent为root节点，那么root = temp，退出方法
* 3.2.2、 假如tempParent不为root节点，那么判断temp是否有右子树
* - 假如temp.right != null,tempParent.left = temp.right
* - 假如temp.right == null,temp.left = null
* 3.3、temp.left = root.left
* 3.4、temp.right = root.right
* 3.5、root = temp
*/
if (this.root == targetNode) {
// 或运算符，有真为真，这里判断的是两者都为null的情况
if (this.root.left == null && this.root.right == null) {
this.root = null;
return;
}
// 异或运算符，相同为false，不同为true，这里判断的就是一个为null，一个不为null的情况
if (this.root.left == null ^ this.root.right == null) {
// 假如root的左子节点!=null，那么就让左子节点为新的root，否则让右子节点为新的root
if (this.root.left != null) {
this.root.left = root;
} else {
this.root.right = this.root;
}
}
// 这里判断的是两者都不为null的情况
if (this.root.left != null && this.root.right != null) {
// 找到root的右子树中最小的temp节点
Node temp = this.root.right.searchTemp();
// 从根节点开始，找到temp的父节点
Node tempParent = this.root.searchParent(temp);
// 假如最小节点的父节点竟然是根节点，那么直接将根节点替换，然后退出方法
if (tempParent == this.root) {
this.root = temp;
return;
}
// 判断最小节点的右子节点是否为null，用于替换其父节点上的位置
if (temp.right == null) {
tempParent.left = null;
} else {
tempParent.left = temp.right;
}
// 替换
temp.left = this.root.left;
temp.right = this.root.right;
this.root = temp;
return;
}
return;
}
/*
* 假如目标节点不是root节点，那么有以下三种情况
*
* 情况一：删除的是一个叶子节点
* 1、找到要删除的节点targetNode
* 2、找到要删除的节点的父节点parentNode
* 3、根据确定targetNode是parentNode的左子节点还是右子节点
* - 假如targetNode是parentNode的左子节点：parent.left = null
* - 假如targetNode是parentNode的右子节点：parent.right = null
*
* 情况二：删除的是只有一颗子树的节点
* 1、找到要删除的节点targetNode
* 2、找到要删除的节点的父节点parentNode
* 3、判断targetNode是parentNode的左子节点还是右子节点
* 3.1、假如targetNode是parentNode的左子节点，继续判断targetNode的子节点childNode是左子节点还是右子节点
* - 假如childNode是targetNode的左子节点：parent.left = target.left
* - 假如childNode是targetNode的右子节点：parent.left = target.right
* 3.2、假如targetNode是parentNode的右子节点，继续判断targetNode的子节点childNode是左子节点还是右子节点
* - 假如childNode是targetNode的左子节点：parent.right = target.left
* - 假如childNode是targetNode的右子节点：parent.right = target.right
*
* 情况三：删除的是有两颗子树的节点
* 1、找到要删除的节点targetNode
* 2、找到要删除的节点的父节点parentNode
* 3、在targetNode的rightChild中，找到一个值最小的节点temp和这个节点的父节点tempParent
* 4、假如tempParent就是要删除的节点，令temp = targetNode.left，然后判断targetNode是是parentNode的左子节点还是右子节点
* - 假如targetNode是parentNode的左子节点：parentNode.left = temp;
* - 假如targetNode是parentNode的右子节点：parentNode.right = temp;
* 5、判断temp.right是否有值
* - 假如temp.right != null：tempParent.left = temp.right
* - 假如temp.right == null：tempParent.left = null
* 6、temp.left = targetNode.left;
* 7、temp.right = targetNode.right;
* 8、判断targetNode是parentNode的左子节点还是右子节点
* - 假如targetNode是parentNode的左子节点：parentNode.left = temp;
* - 假如targetNode是parentNode的右子节点：parentNode.right = temp;
*/
// 找到要删除节点的父节点
Node parentNode = this.root.searchParent(targetNode);
// 假如要删除的节点是叶子节点
if (targetNode.left == null && targetNode.right == null) {
if (parentNode.left == targetNode) {
parentNode.left = null;
} else {
parentNode.right = null;
}
return;
}
// 假如要删除的节点只有一颗子树
if (targetNode.left == null ^ targetNode.right == null) {
// 假如要删除的节点是左子节点，那么就替换对应的父节点的左边
if (parentNode.left == targetNode) {
if (targetNode.left != null) {
parentNode.left = targetNode.left;
} else {
parentNode.left = targetNode.right;
}
}
// 假如要删除的节点是右子节点，那么就替换对应父节点的右边
if (parentNode.right == targetNode) {
if (targetNode.left != null) {
parentNode.right = targetNode.left;
} else {
parentNode.right = targetNode.right;
}
}
return;
}
// 假如要删除的节点有两棵子树
if (targetNode.left != null && targetNode.right != null) {
// 获得要删除的右子树的最小节点和最小节点的父节点
Node temp = targetNode.right.searchTemp();
Node tempParent = this.root.searchParent(temp);
// 假如右子树最小节点的父节点为要删除的节点
if (tempParent == targetNode) {
temp.left = targetNode.left;
// 假如要删除的节点在其父节点的左子节点处，那么temp就为左边；反之在右边
if (parentNode.left == targetNode) {
parentNode.left = temp;
} else {
parentNode.right = temp;
}
return;
} else {
// 判断最小节点的右节点是否为null，用于替换原来最小节点在其父节点的位置
if (temp.right == null) {
tempParent.left = null;
} else {
tempParent.left = temp.right;
}
}
// 替换
temp.left = targetNode.left;
temp.right = targetNode.right;
// 假如要删除的节点在其父节点的左子节点处，那么temp就为左边；反之在右边
if (parentNode.left == targetNode) {
parentNode.left = temp;
} else {
parentNode.right = temp;
}
}
}
}
这一部分确实是有点长，建议复制到IDEA里面好好查看，并且为了方便没有写get和set，并且这里的方法只有一个delNode
平衡二叉树（AVL）
问题描述
现在我们来看BST的一种情况：我们现在有一个数列：{1,2,3,4,5}，它构建为一个BST树，最终结果是这样的：
这颗BST树，只有右子节点，没有左子节点，导致它在形式上来讲更像是一个单链表
虽然在插入和删除方面的效率是可以的，但是它在查询方面的效率还不如链表：他要去判断左子节点，然后才会去遍历右子节点
AVL树概述
平衡二叉树（Self-balancing binary search tree），又被称为AVL树，可以保证查询效率比较高
AVL树有以下特点：
1、AVL树是在二叉排序树的基础上进行实现的，也就是说它符合左子节点<父节点<右子节点的特点
2、它是一颗空树，或者拥有左右子树
3、假如它有子树，那么左右两颗子树的高度差绝对值不超过1，并且左右两颗子树都是一颗平衡二叉树
4、平衡二叉树的常用实现方式有：红黑树，AVL算法，替罪羊树，Treap，伸展树等
AVL的旋转
左旋概述
这里讲一下平衡二叉树的左旋问题
现在我们有一颗二叉排序树，它是这样的：
它当然不是AVL树，因为根据AVL树的定义，任何节点的左右两端的高度差不得超过1
现在左边的高度为1，右边的高度为3。那么我们要将这颗BST树转换为AVL树，有一个专业的方法叫做旋转
那么在根节点的视角中，左右子树的高度明显不符合AVL的定义，其中右子树较高，那么我们就进行左旋
其中现在我们来看根节点，因为我们是以根节点的角度来进行树的左旋，左旋的步骤如下：
1、创建一个新的节点newNode，值为当前的根节点的值
2、将新节点的左子树设置为当前节点（根节点）的左子树
3、将新节点的右子树设置为当前节点（根节点）的右子节点的左子节点
4、当前节点（根节点）的值替换为右子节点的值
5、当前节点（根节点）的右子树设置为右子节点的右子树
6、当前节点（根节点）的左子树设置为新节点
7、最终就是这样的：
8、至于原来的节点6，会被GC
右旋概述
假如理解了坐旋转，那么右旋转就很好立即了，右旋转的目的是降低左子树的高度，以达到一个平衡
有旋转要经历以下步骤：
1、创建一个新的节点newNode
2、newNode的右子树设置为当前节点的右子树
3、newNode的左子树设置为当前节点的左子节点的右子树
4、当前节点的值换为左子节点的值
5、当前节点的左子树设置为左子树的左子树
6、当前节点的右子树设置为新的节点
双旋转
很多时候，哪怕我们进行了左旋转或者右旋转，仍然不能保证这棵树是平衡的，请看下图：
这张图的左边， 进行了右旋，右旋之后发现右边树的高度高了，所以单纯的左旋或者右旋并不能够解决问题
问题分析：
1、当符合右旋转的条件时
2、假如这棵树的左子树的右子树高度大于它的右子树高度
看左图，也就是节点10的左子树7的右子树大于10的右子树
3、假如直接进行右旋转，就会出现上图的情况
问题解决：
1、当符合右旋转的条件时
2、假如这棵树的左子树的右子树高度大于它的右子树高度
3、先对当前节点的左子树进行左旋，然后对当前树进行右旋
就是说，将根节点为7的子树进行左旋，然后将根节点为10的树进行右旋
其实换个说法就非常容易理解了：在将自己变为AVL树之前，要首先将自己的子树全都变为AVL树
前期准备
下面来写代码，我们首先要写节点和树
我们一开始就说，AVL是基于BST来进行的，所以它可以复用BST的代码，如果忘记了，那么去前面再看一下
但是我们的AVL需要树和子树的高度，所以在Node类上，再增加三个新的方法
/**
* 树节点
*/
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
/**
* 以当前节点为根节点，求这棵树的高度
*
* @return 树的高度
*/
public int height() {
return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1;
}
/**
* 求当前节点的左子树的高度
*
* @return 左子树的高度
*/
public int leftHeight() {
return this.left == null ? 0 : this.left.height();
}
/**
* 求当前节点的右子树的高度
*
* @return 右子树的高度
*/
public int rightHeight() {
return this.right == null ? 0 : this.right.height();
}
}
并且我还要将上面的BSTTree改为AVLTree
旋转代码实现
/**
* 树节点
*/
class Node {
int value;
Node left;
Node right;
/**
* 左旋
*/
public void leftRotate() {
// 1、创建一个新的节点newNode
Node newNode = new Node();
// 2、新节点的左子树设置为当前节点的左子树
newNode.left = this.left;
// 3、新节点的右子树设置为当前节点的右子节点的左子树
newNode.right = this.right.left;
// 4、当前节点的值替换为右子节点的值
this.value = this.right.value;
// 5、当前节点的右子树设置为右子节点的右子树
this.right = this.right.right;
// 6、当前节点的左子树设置为新的节点
this.left = newNode;
}
/**
* 右旋
*/
public void rightRotate() {
// 1、创建一个新的节点newNode
Node newNode = new Node();
// 2、newNode的右子树设置为当前节点的右子树
newNode.right = this.right;
// 3、newNode的左子树设置为当前节点的左子节点的右子树
newNode.left = this.left.right;
// 4、当前节点的值换为左子节点的值
this.value = this.left.value;
// 5、当前节点的左子树设置为左子树的左子树
this.left = this.left.left;
// 6、当前节点的右子树设置为新的节点
this.right = newNode;
}
/**
* 添加节点，需要满足二叉排序树的要求
*
* @param node 要添加的节点
*/
public void add(Node node) {
if (node == null) {
return;
}
/*
* 判断当前节点的值和父节点点值的关系
* 假如当前节点的值比父节点的值小，那么向父节点的左子节点进行比较
* - 假如父节点的左子节点为null，那么直接挂上
* - 假如父节点的左子节点不为null，那么递归判断
* 假如当前节点的值大于或等于父节点的值，那么向父节点的右子节点进行比较
* - 假如父节点的右子节点的值为null，那么直接挂上
* - 假如父节点的右子节点的值不为null，那么递归判断
*/
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
return;
}
this.left.add(node);
} else {
if (this.right == null) {
this.right = node;
return;
}
this.right.add(node);
}
// 当添加完一个节点之后，假如右子树-左子树的高度大于1，那么进行左旋
if (rightHeight() - leftHeight() > 1) {
// 假如它的右子树的左子树高度大于它的右子树高度，那么进行双旋
if (right != null && right.leftHeight() > right.rightHeight()) {
right.rightRotate();
leftRotate();
} else {
// 假如不满足，那么直接进行左旋转
leftRotate();
}
return;
}
// 当添加完一个节点之后，假如左子树 -右子树的高度大于1，那么进行右旋
if (leftHeight() - rightHeight() > 1) {
// 假如它的左子树的右子树高度大于它的左子树高度，那么进行双旋
if (left != null && left.rightHeight() > left.leftHeight()) {
// 先对当前节点的左子树进行左旋
left.leftRotate();
// 在对当前节点进行旋转
rightRotate();
} else {
// 假如不满足，那么直接进行右旋转
rightRotate();
}
return;
}
}
}