树结构实际应用
1. 堆排序
基本介绍
1、堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序。
2、堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
3、每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4、大顶堆举例说明
将无序序列构建成一个大顶堆。
首先我们将现在的无序序列看成一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。
5、小顶堆举例说明
6、一般升序采用大顶堆，降序采用小顶堆
堆排序基本思想
堆排序的基本思想是：
- 将待排序序列构造成一个大顶堆
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序
序列了。 - 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
堆排序步骤图解
要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。
步骤一： 构造初始堆将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)
- .假设给定无序序列结构如下
- .此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点
arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上 进行调整。
- 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
- 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无序序列构造成了一个大顶堆。
步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
- .将堆顶元素9和末尾元素4进行交换
- 重新调整结构，使其继续满足堆定义
- 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
- 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
动图演示
再简单总结下堆排序的基本思路：
（1）将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
（2）将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
（3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
堆排序代码实现
要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。
说明：
1)堆排序不是很好理解，可以通过 Debug 帮助理解堆排序
2)堆排序的速度非常快，在我的机器上 8 百万数据 3 秒左右。O(nlogn)
3)代码实现：下面给出两种实现方式（原理是一样的）
public class HeapSort {
public static void main(String[] args) {
//要求将数组进行升序排序
int arr[] = {4, 6, 8, 5, 9};
System.out.println("排序后=" + Arrays.toString(arr));
}
//编写一个堆排序的方法
public static void heapSort(int arr[]) {
int temp = 0;
System.out.println("堆排序!!");
// //分步完成
// adjustHeap(arr, 1, arr.length);
// System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
//
// adjustHeap(arr, 0, arr.length);
// System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4
//完成我们最终代码
//将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
for(int i = arr.length / 2 -1; i >=0; i--) {
adjustHeap(arr, i, arr.length);
}
/*
* 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
*/
for(int j = arr.length-1;j >0; j--) {
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
//System.out.println("数组=" + Arrays.toString(arr));
}
//将一个数组(二叉树), 调整成一个大顶堆
/**
* 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆
* 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}
* 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}
* @param arr 待调整的数组
* @param i 表示非叶子结点在数组中索引
* @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
*/
public static void adjustHeap(int arr[], int i, int lenght) {
int temp = arr[i];//先取出当前元素的值，保存在临时变量
//开始调整
//说明
//1. k = i * 2 + 1 k 是 i结点的左子结点
for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
if(k+1 < lenght && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值
k++; // k 指向右子结点
}
if(arr[k] > temp) { //如果子结点大于父结点
arr[i] = arr[k]; //把较大的值赋给当前结点
i = k; //!!! i 指向 k,继续循环比较
} else {
break;//!
}
}
//当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
arr[i] = temp;//将temp值放到调整后的位置
}
}//菜鸟教程：https://www.runoob.com/w3cnote/heap-sort.html
思路分析图：
public class HeapSort {
public static void main(String[] args) {
//要求将数组进行升序排序
int arr[] = {4, 6, 8, 5, 9};
int[] ret = heapSortFunc(arr);
System.out.println(Arrays.toString(ret));
}
//堆排序方法
public static int[] heapSortFunc(int arr[]) {
// 对 arr 进行拷贝，不改变参数内容
int[] newarr = Arrays.copyOf(arr, arr.length);
int len = newarr.length;
for (int i = (int)Math.floor(len / 2); i >=0 ; i--) {
adjustHeap(newarr,i,len);
}
for (int i = len-1; i >0 ; i--) {
swap(newarr,0,i);
len--;
adjustHeap(newarr,0,len);
}
return newarr;
}
//将一个数组(二叉树), 调整成一个大顶堆
/**
* 功能：完成将以 i 为非叶子节点的树调整为大顶堆
* 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}
* 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}
* @param arr 待调整的数组
* @param i 表示非叶子结点在数组中索引
* @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
*/
public static void adjustHeap(int arr[], int i, int lenght) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
if(left < lenght && arr[left] > arr[largest]){
largest = left;
}
if(right < lenght && arr[right] > arr[largest]){
largest = right;
}
if(largest != i){
swap(arr,i,largest);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}2. 赫夫曼树
参考：https://baijiahao.baidu.com/s?id=1663514710675419737
基本介绍
（1）给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小达到最小，称这样的二叉树为
最优二叉树，也称为哈夫曼树(Huffman Tree) 或 霍夫曼树。
（2）赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近
几个重要概念
- 路径
在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。
上面的二叉树当中，从根结点A到叶子结点H的路径，就是A，B，D，H。
- 路径长度
在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。
仍然用刚才的二叉树举例子，从根结点A到叶子结点H，共经过了3条边，因此路径长度是3。
- 结点的带权路径长度
树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。
结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。
假设结点H的权重是3，从根结点到结点H的路径长度也是3，因此结点H的带权路径长度是 3 X 3 = 9。
- 树的带权路径长度
在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。
仍然以这颗二叉树为例，树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53。
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明，这到底是一颗什么样的树呢？
刚才我们学习了树的带权路径长度（WPL），而哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。
举个例子，给定权重分别为1，3，4，6，8的叶子结点，我们应当构建怎样的二叉树，才能保证其带权路径长度最小？
原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。
下图左侧的这棵树就是一颗哈夫曼树，它的WPL是46，小于之前例子当中的53：
需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，下面这几棵树都是哈夫曼树：
赫夫曼树创建思路图解
假设有6个叶子结点，权重依次是2，3，7，9，18，25，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？
第一步：构建森林
我们把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），这样就形成了一个森林：
在上图当中，右侧是叶子结点的森林，左侧是一个辅助队列，按照权值从小到大存储了所有叶子结点。至于辅助队列的作用，我们后续将会看到。
第二步：选择当前权值最小的两个结点，生成新的父结点
借助辅助队列，我们可以找到权值最小的结点2和3，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和：
第三步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列
也就是从队列中删除2和3，插入5，并且仍然保持队列的升序：
第四步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是5和7，生成新的父结点权值是5+7=12：
第五步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这是对第三步的重复操作，也就是从队列中删除5和7，插入12，并且仍然保持队列的升序：
第六步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是9和12，生成新的父结点权值是9+12=21：
第七步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这是对第三步的重复操作，也就是从队列中删除9和12，插入21，并且仍然保持队列的升序：
第八步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是18和21，生成新的父结点权值是18+21=39：
第九步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这是对第三步的重复操作，也就是从队列中删除18和21，插入39，并且仍然保持队列的升序：
第十步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是25和39，生成新的父结点权值是25+39=64：
第十一步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列
这是对第三步的重复操作，也就是从队列中删除25和39，插入64：
此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树：
代码实现
package com.xjt.javase.dataStructure.huffmantree;
import lombok.Data;
import java.util.ArrayList;
import java.util.Collections;
public class HuffmanTreeDemo {
public static void main(String[] args) {
int arr[] = {2,3,7,9,18,25};
Node root = createHuffManTree(arr);
testPreOrder(root);
}
/**
* 测试树的前序遍历方法
* @param root
*/
public static void testPreOrder(Node root){
if(root != null){
root.preOrder();
}else{
System.out.println("是空树，不能遍历~~");
}
}
/**
* 将数组arr 转为哈夫曼树
* @param arr
* @return
*/
public static Node createHuffManTree(int[] arr){
// 第一步 为了操作方便 将arr数组转为list集合
// 1. 遍历 arr 数组
// 2. 将arr的每个元素构成成一个Node
// 3. 将Node 放入到ArrayList中
ArrayList<Node> nodes = new ArrayList<>();
for (int val:arr){
nodes.add(new Node(val));
}
while(nodes.size() > 1){
//1、对ArrayList进行排序
Collections.sort(nodes);
System.out.println("列表nodes =" + nodes);
//2、取出ArrayList中节点权值最小的两颗树
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
//3、构建一颗新的二叉树
Node parent = new Node(leftNode.getValue() + rightNode.getValue());
parent.setLeft(leftNode);
parent.setRight(rightNode);
//4、从ArrayList中删除处理过的二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
//5、将parent加入到nodes
nodes.add(parent);
}
//返回哈夫曼树的root节点
return nodes.get(0);
}
}
@Data
class Node implements Comparable<Node>{
private int value;
private Node left;
private Node right;
public Node() {
}
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 String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
//从小到大排序
return this.getValue() - o.getValue();
}
}3. 赫夫曼编码
基本介绍
- 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
- 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
- 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间
- 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码
原理剖析
通信领域中信息的处理方式 1-定长编码
通信领域中信息的处理方式 2-变长编码
通信领域中信息的处理方式 3-赫夫曼编码
4. 二叉排序树(二叉搜索树)
给你一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加
解决方案分析：
- 使用数组
- 数组未排序， 优点：直接在数组尾添加，速度快。 缺点：查找速度慢
- 数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位
置后，后面的数据需整体移动，速度慢
- 使用链式存储-链表
不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。 - 使用二叉排序树
二叉排序树介绍
二叉排序树也叫做二叉搜索树：BST: (Binary Sort(Search) Tree)，
对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：
二叉排序树创建和遍历
一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ， 创建成对应的二叉排序树为 :
Node节点类：
@Data
@NoArgsConstructor
class Node{
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
//添加节点
public void add(Node node){
if(node == null){
return;
}
//判断传入的结点的值，和当前子树的根结点的值关系
if(node.value < this.value){
if(this.left == null){
this.left = node;
}else{
//递归的向左子树添加
this.left.add(node);
}
}else{ //node值 不小于当前节点值
if(this.right == null){
this.right = node;
}else{
//递归的向右子树添加
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();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}二叉排序树类：
//定义二叉排序树
class BinarySortTree{
private Node root;
public Node getRoot(){
return this.root;
}
//添加结点的方法
public void BSTAdd(Node node){
if(this.root == null){
this.root = node;
}else{
this.root.add(node);
}
}
//中序遍历
public void BSTInfixOrder(){
if(this.root == null){
System.out.println("空树无法遍历...");
}else{
this.root.infixOrder();
}
}
}删除节点(!!!)
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
- 删除叶子节点 (比如：2, 5, 9, 12)
- 删除只有一颗子树的节点 (比如：1)
- 删除有两颗子树的节点. (比如：7, 3，10 )
操作的思路分析
//思路：
（1）删除叶子节点 (比如：2, 5, 9, 12)
1.1 需要先去找到要删除的结点targetNode
1.2 找到 targetNode 的 父结点 parent
1.3 确定 targetNode 是 parent 的左子结点 还是右子结点
1.3.1 如果targetNode是parent的左子节点
左子结点 parent.left = null
1.3.2 如果targetNode是parent的右子节点
右子结点 parent.right = null;
（2）删除只有一颗子树的节点 (比如：1)
1、需求先去找到要删除的结点targetNode
2、找到 targetNode 的 父结点 parent
3、确定 targetNode 的子结点是左子结点还是右子结点
4、确定 targetNode 是 parent 的左子结点还是右子结点
5、如果 targetNode 有左子结点
5. 1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.left;
5.2如果 targetNode 是 parent 的右子结点
parent.right = targetNode.left;
6、 如果 targetNode 有右子结点
6.1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.right;
6.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right
（3）删除有两颗子树的节点. (比如：7, 3，10 )
1、需求先去找到要删除的结点targetNode
2、找到 targetNode 的 父结点 parent
3、从 targetNode 的右子树找到最小的结点
4、用一个临时变量，将 最小结点的值保存 temp = 11
5、删除该最小结点（最小节点应该在右子树的最左侧叶子上）
6、targetNode.value = temp完整代码
package com.xjt.javase.dataStructure.binarysorttree;
import lombok.Data;
import lombok.NoArgsConstructor;
//二叉排序树测试Demo
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.BSTAdd(new Node(arr[i]));
}
//中序遍历二叉排序树
System.out.println("中序遍历二叉排序树~");
binarySortTree.BSTInfixOrder(); // 1, 3, 5, 7, 9, 10, 12
//查找值为 3的节点及其父节点
System.out.println("值为3的节点===》");
System.out.println(binarySortTree.BSTSearch(3));
System.out.println("值为3的节点的父节点===》");
System.out.println(binarySortTree.BSTSearchParent(3));
//测试一下删除叶子结点
binarySortTree.delNode(5);
binarySortTree.delNode(9);
binarySortTree.delNode(1);
System.out.println("删除节点之后中序遍历二叉排序树~");
binarySortTree.BSTInfixOrder();
}
}
//定义二叉排序树
class BinarySortTree{
private Node root;
public Node getRoot(){
return this.root;
}
public Node BSTSearch(int val){
if(root == null){
return null;
}else{
return this.root.search(val);
}
}
public Node BSTSearchParent(int val){
if(root == null){
return null;
}else{
return this.root.searchParent(val);
}
}
public void delNode(int val){
if(root == null){
return;
}else{
//1、找到要删除的结点 targetNode
Node targetNode = BSTSearch(val);
if(targetNode == null){
return;
}
//这颗二叉树只有一个节点 且根节点就是我们找到的目标节点
if(root.left == null && root.right == null){
root = null;
return;
}
//2、找到要删除的结点的父节点 parentNode
Node parentNode = BSTSearchParent(val);
//3、如果要删除的结点是叶子结点
if(targetNode.left == null && targetNode.right == null){
//targetNode是parent的左子节点
if(parentNode.left!= null && parentNode.left == targetNode){
parentNode.left = null;
}else if(parentNode.right != null && parentNode.right == targetNode){
parentNode.right = null;
}
}else if(targetNode.left != null && targetNode.right != null){ //4、删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode);
targetNode.value = minVal;
}else{ // 4、删除只有一颗子树的结点
//4.1、如果要删除的结点有左子结点
if(targetNode.left != null){
if(parentNode != null){
if(parentNode.left == targetNode){ //4.1.1 targetNode 是 parentNode的左子节点
parentNode.left = targetNode.left;
}else if(parentNode.right == targetNode){ //4.1.2 targetNode 是 parentNode的右子节点
parentNode.right = targetNode.left;
}
}else{
root = targetNode.left;
}
}else if(targetNode.right != null){ //4.2、如果要删除的结点有右子结点
if(parentNode != null){
//4.2.1 targetNode 是 parentNode的左子节点
if(parentNode.left == targetNode){
parentNode.left = targetNode.right;
}
//4.2.2 targetNode 是 parentNode的右子节点
if(parentNode.right == targetNode){
parentNode.right = targetNode.right;
}
}else{
root = targetNode.right;
}
}
}
}
}
/**
* 思路：右子树的最小值节点 在右子树的叶子节点 最左侧
* @param node 目标节点
* @return 删除目标节点右子树的最小值节点，并返回 该最小值节点
*/
public int delRightTreeMin(Node node){
Node target = node;
//循环的查找左子节点，就会找到最小值
while (target.left != null){
target = target.left;
}
//这时 target就指向了最小结点
//删除最小结点
delNode(target.value);
return target.value;
}
//添加结点的方法
public void BSTAdd(Node node){
if(this.root == null){
this.root = node;
}else{
this.root.add(node);
}
}
//中序遍历
public void BSTInfixOrder(){
if(this.root == null){
System.out.println("空树无法遍历...");
}else{
this.root.infixOrder();
}
}
}
@Data
@NoArgsConstructor
class Node{
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
//添加节点
public void add(Node node){
if(node == null){
return;
}
//判断传入的结点的值，和当前子树的根结点的值关系
if(node.value < this.value){
if(this.left == null){
this.left = node;
}else{
//递归的向左子树添加
this.left.add(node);
}
}else{ //node值 不小于当前节点值
if(this.right == null){
this.right = node;
}else{
//递归的向右子树添加
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();
}
}
/**
* 根据节点value值 查找结点
* @param val 节点value值
* @return 找到就返回该节点，否则返回null
*/
public Node search(int val){
if(val == this.value){
return this;
}else if(val < this.value){
if (this.left == null) {
return null;
}else{
return this.left.search(val);
}
}else{ //val 不小于当前节点的value值
if (this.right == null) {
return null;
}else{
return this.right.search(val);
}
}
}
/**
* 查找要删除结点的父结点
* @param val 要找到的结点的值
* @return 返回的是要删除的结点的父结点，如果没有就返回null
*/
public Node searchParent(int val){
//1、当前节点的左节点value==val 或者 右节点value==val
if((this.left != null && this.left.value == val) ||
(this.right != null && this.right.value == val)){
return this;
}else{
//如果val 小于当前节点值 并且当前节点的左子树不为null
if(val < this.value && this.left != null){
return this.left.searchParent(val);
}else if(val > this.value && this.right != null){
return this.right.searchParent(val);
}else{ //没有找到
return null;
}
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}作业
前面我们使用的是从右子树找到最小节点替换掉当前targetNode，尝试从左子树找到最大的结点，完成删除节点功能
5. 平衡二叉树(AVL 树)
参考：https://blog.csdn.net/qq_44111805/article/details/113739395
（有动画演示）https://blog.csdn.net/jarvan5/article/details/112428036
基本介绍
看一个案例(说明二叉排序树可能的问题)
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST)
存在的问题分析:
- 左子树全部为空，从形式上看，更像一个单链表
- 插入速度没有影响
- 查询速度明显降低(因为需要依次比较), 不能发挥 BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
解决方案-平衡二叉树(AVL)
平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树， 可以保证查询效率较高。
AVL树具有以下特点：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
注意：平衡二叉树一定是二叉排序树。含有n个结点的平衡二叉树的最大深度为O(log2(n))，即平衡二叉树的平均查找长度为O(log2(n))。
如下图所示为一棵平衡二叉树和一棵非平衡二叉树：
举例说明, 看看下面哪些 AVL 树, 为什么?
总结：判断「平衡二叉树」的 2 个条件：
平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列四种情况：
单旋转(左旋转)
有的地方又称为：RR平衡旋转（左单旋转）
前提条件：右子树的高度减去左子树的高度大于1，即：rightHeight() - leftHeight() > 1。
要求: 给你一个数列，创建出对应的平衡二叉树，数列 {4,3,6,5,7,8}
左旋转思路分析：
（1）创建一个新的结点newNode，值等于当前根结点的值；
（2）将新结点的左子树设置为当前结点的左子树：
newNode.left=left
（3）将新结点的右子树设置为当前结点的右子树的左子树：
newNode.right = right.left
（4）将当前结点的值换为右子结点的值：
value=right.value
（5）将当前结点的右子树设置成右子树的右子树：
right=right.right
（6）将当前结点的左子树设置成新结点：
left = newNode示意图
代码实现：
//左旋转方法
private void leftRotate() {
//创建新的结点，以当前根结点的值
Node newNode = new Node(value);
//把新的结点的左子树设置成当前结点的左子树
newNode.left = left;
//把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right = right.left;
//把当前结点的值替换成右子结点的值
value = right.value;
//把当前结点的右子树设置成当前结点右子树的右子树
right = right.right;
//把当前结点的左子树(左子结点)设置成新的结点
left = newNode;
}单旋转(右旋转)
有的地方又称为：LL平衡旋转（右单旋转）
前提条件：左子树的高度减去右子树的高度大于1，即：leftHeight() - rightHeight() > 1。
案例分析：
1）给你一个数列 {10,12, 8, 9, 7, 6}，创建出对应的平衡二叉树
- 思路分析
问题：当插入6 时
leftHeight() - rightHeight() > 1 成立，此时，不再是一颗avl树了.
怎么处理--进行右旋转.[就是降低左子树的高度], 这里是将9 这个节点，通过右旋转，到右子树
1、创建一个新的节点 newNode (以10这个值创建)创建一个新的节点，值等于当前根节点的值
2、把新节点的右子树设置了当前节点的右子树
newNode.right = right
3、把新节点的左子树设置为当前节点的左子树的右子树
newNode.left =left.right;
4、把当前节点的值换为左子节点的值
value=left.value;
5、把当前节点的左子树设置成左子树的左子树
left=left.left;
6、把当前节点的右子树设置为新节点
right=newLeft;示意图：
代码实现：
//右旋转
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}双旋转
有的地方又称为：LR平衡旋转（先左后右双旋转）
前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树
int[] arr = { 10, 11, 7, 6, 8, 9 }; //运行原来的代码可以看到，并没有转成 AVL 树.
解决思路分析
- 当符合右旋转的条件时（
rightHeight() - leftHeight() > 1） - 如果当前结点 它的左子树的右子树高度大于它的左子树的高度（
left.rightHeight()>left.leftHeight()） - 先对当前结点的左节点进行左旋转
- 再对当前结点进行右旋转的操作即可
- 当符合左旋转的条件时（
leftHeight() - rightHeight() > 1）- 如果当前结点 它的右子树的左子树高度大于它的右子树的高度（
right.leftHeight() > right.rightHeight()） - 先对当前结点的右子树进行右旋转
- 再对当前结点进行左旋转的操作即可
- 如果当前结点 它的右子树的左子树高度大于它的右子树的高度（
代码实现（AVL 树的汇总代码(完整代码)）：
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//int[] arr = { 10, 12, 8, 9, 7, 6 };
int[] arr = { 10, 11, 7, 6, 8, 9 };
//创建一个 AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for(int i=0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("在平衡处理~~");
System.out.println("树的高度=" + avlTree.getRoot().height()); //3
System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("当前的根结点=" + avlTree.getRoot());//8
}
}
// 创建AVLTree
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
// 查找要删除的结点
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
// 查找父结点
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
// 编写方法:
// 1. 返回的 以node 为根结点的二叉排序树的最小结点的值
// 2. 删除node 为根结点的二叉排序树的最小结点
/**
*
* @param node
* 传入的结点(当做二叉排序树的根结点)
* @return 返回的 以node 为根结点的二叉排序树的最小结点的值
*/
public int delRightTreeMin(Node node) {
Node target = node;
// 循环的查找左子节点，就会找到最小值
while (target.left != null) {
target = target.left;
}
// 这时 target就指向了最小结点
// 删除最小结点
delNode(target.value);
return target.value;
}
// 删除结点
public void delNode(int value) {
if (root == null) {
return;
} else {
// 1.需求先去找到要删除的结点 targetNode
Node targetNode = search(value);
// 如果没有找到要删除的结点
if (targetNode == null) {
return;
}
// 如果我们发现当前这颗二叉排序树只有一个结点
if (root.left == null && root.right == null) {
root = null;
return;
}
// 去找到targetNode的父结点
Node parent = searchParent(value);
// 如果要删除的结点是叶子结点
if (targetNode.left == null && targetNode.right == null) {
// 判断targetNode 是父结点的左子结点，还是右子结点
if (parent.left != null && parent.left.value == value) { // 是左子结点
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {// 是由子结点
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) { // 删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // 删除只有一颗子树的结点
// 如果要删除的结点有左子结点
if (targetNode.left != null) {
if (parent != null) {
// 如果 targetNode 是 parent 的左子结点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode 是 parent 的右子结点
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else { // 如果要删除的结点有右子结点
if (parent != null) {
// 如果 targetNode 是 parent 的左子结点
if (parent.left.value == value) {
parent.left = targetNode.right;
} else { // 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
// 添加结点的方法
public void add(Node node) {
if (root == null) {
root = node;// 如果root为空则直接让root指向node
} else {
root.add(node);
}
}
// 中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序树为空，不能遍历");
}
}
}
// 创建Node结点
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
// 返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
// 返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
// 返回 以该结点为根结点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//左旋转方法
private void leftRotate() {
//创建新的结点，以当前根结点的值
Node newNode = new Node(value);
//把新的结点的左子树设置成当前结点的左子树
newNode.left = left;
//把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right = right.left;
//把当前结点的值替换成右子结点的值
value = right.value;
//把当前结点的右子树设置成当前结点右子树的右子树
right = right.right;
//把当前结点的左子树(左子结点)设置成新的结点
left = newNode;
}
//右旋转
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
// 查找要删除的结点
/**
*
* @param value
* 希望删除的结点的值
* @return 如果找到返回该结点，否则返回null
*/
public Node search(int value) {
if (value == this.value) { // 找到就是该结点
return this;
} else if (value < this.value) {// 如果查找的值小于当前结点，向左子树递归查找
// 如果左子结点为空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else { // 如果查找的值不小于当前结点，向右子树递归查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
// 查找要删除结点的父结点
/**
*
* @param value
* 要找到的结点的值
* @return 返回的是要删除的结点的父结点，如果没有就返回null
*/
public Node searchParent(int value) {
// 如果当前结点就是要删除的结点的父结点，就返回
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
if (value < this.value && this.left != null) {
return this.left.searchParent(value); // 向左子树递归查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); // 向右子树递归查找
} else {
return null; // 没有找到父结点
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
// 添加结点的方法
// 递归的形式添加结点，注意需要满足二叉排序树的要求
public void add(Node node) {
if (node == null) {
return;
}
// 判断传入的结点的值，和当前子树的根结点的值关系
if (node.value < this.value) {
// 如果当前结点左子结点为null
if (this.left == null) {
this.left = node;
} else {
// 递归的向左子树添加
this.left.add(node);
}
} else { // 添加的结点的值大于 当前结点的值
if (this.right == null) {
this.right = node;
} else {
// 递归的向右子树添加
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();
}
}
}
// 中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
