数据结构和算法入门
1.了解数据结构和算法1.1 二分查找
二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两半，然后比较目标值与中间元素的巨细关系，从而确定应该在左半部分照旧右半部分继续查找。这个过程不绝重复，直到找到目标值或确定它不存在于数组中。
1.1.1 二分查找的实现
（1）循环条件使用 "i <= j" 而不是 "i < j" 是由于，在二分查找的过程中，我们必要同时更新 i 和 j 的值。当 i 和 j 相等时，说明当前搜索范围只剩下一个元素，我们必要查抄这个元素是否是我们要找的目标值。假如这个元素不是我们要找的目标值，那么我们可以确定目标值不存在于数组中。
假如我们将循环条件设置为 "i < j"，那么当 i 和 j 相等时，我们就无法进入循环来查抄这个唯一的元素，这会导致我们无法正确地判定目标值是否存在。
因此，在二分查找的循环条件中，我们应该使用 "i <= j"，以确保我们在搜索范围内包含所有可能的元素。
（2）假如你使用 "i + j / 2" 来计算二分查找的中间值，可能会遇到整数溢出的题目。这是由于在 Java 中，整数除法（/）对整数操作时会向下取整，结果仍然是一个整数。例如，假如 i 和 j 都是很大的数，且它们相加结果大于 Integer.MAX_VALUE（即 2^31 - 1），那么直接将它们相加再除以 2 就会导致溢出，由于中间结果已经超出了 int 范例的最大值（会酿成负数）。
public static void main(String[] args) {
int[]arr={1,22,33,55,88,99,117,366,445,999};
System.out.println(binarySearch( arr,1));//结果：0
System.out.println(binarySearch( arr,22));//结果：1
System.out.println(binarySearch( arr,33));//结果：2
System.out.println(binarySearch( arr,55));//结果：3
System.out.println(binarySearch( arr,88));//结果：4
System.out.println(binarySearch( arr,99));//结果：5
System.out.println(binarySearch( arr,117));//结果：6
System.out.println(binarySearch( arr,366));//结果：7
System.out.println(binarySearch( arr,445));//结果：8
System.out.println(binarySearch( arr,999));//结果：9
System.out.println(binarySearch( arr,1111));//结果：-1
System.out.println(binarySearch( arr,-1));//结果：-1
}
/**
* @Description
* @Author LY
* @Param 待查找升序数组，查找的值
* @return int 找到返回索引，找不到返回-1
* @Date 2023/12/8 16:38
**/
public static int binarySearch(int[] arr, int target){
//设置 i跟j 初始值
int i=0;
int j= arr.length-1;
//如果i>j，则表示并未找到该值
while (i<=j){
int m=(i+j)>>>1;
// int m=(i+j)/2;
if (target<arr){
//目标在左侧
j=m-1;
}else if(target>arr){
//目标在右侧
i=m+1;
}else{
//相等
return m;
}
}
return -1;
} 1.1.2 二分查找改动版
方法 binarySearchAdvanced 是一个优化版本的二分查找算法。它将数组范围从 0 到 arr.length 举行划分（改动1），而且在循环条件中使用 i < j 而不是 i <= j （改动2）。这种修改使恰当目标值不存在于数组中时，可以更快地竣事搜索。别的，在向左移动右边界时，只需将其设置为中间索引 m 而不是 m - 1 （改动3）。
这些改动使 binarySearchAdvanced 在某些环境下可能比标准二分查找更快。然而，在实际应用中，这些差异通常很小，由于二分查找本身的复杂度已经很低（O(log n)）。
/**
* @return int 找到返回索引，找不到返回-1
* @Description 二分查找改动版
* @Author LY
* @Param 待查找升序数组，查找的值
* @Date 2023/12/8 16:38
**/
public static int binarySearchAdvanced(int[] arr, int target) {
int i = 0;
// int j= arr.length-1;
int j = arr.length;//改动1
// while (i<=j){
while (i < j) {//改动2
int m = (i + j) >>> 1;
if (target < arr) {
// j = m - 1;
j = m; //改动3
} else if (arr < target) {
i = m + 1;
} else {
return m;
}
}
return -1;
}
1.1.3 递归实现
请检察：3.底子数据结构-链表-CSDN博客 3.5 补充：递归
1.2 线性查找
线性查找（Linear Search）是一种简单的搜索算法，用于在无序数组或列表中查找特定元素。它的基本思想是从数组的第一个元素开始，逐一比较每个元素与目标值的巨细关系，直到找到目标值或遍历完整个数组。
（1）初始化一个变量 index 为 -1，表示尚未找到目标值。
（2）从数组的第一个元素开始，使用循环依次访问每个元素：
（3）假如当前元素等于目标值，则将 index 设置为当前索引，并竣事循环。
（4）返回 index。（假如找到了目标值返回其索引；否则返回 -1 表示未找到目标值）
/**
* @return int 找到返回索引，找不到返回-1
* @Description 线性查找
* @Author LY
* @Param 待查找数组（可以不是升序），查找的值
* @Date 2023/12/8 16:38
**/
public static int LinearSearch(int[] arr, int target) {
int index=-1;
for (int i = 0; i < arr.length; i++) {
if(arr==target){
index=i;
break;
}
}
return index;
}
1.3 衡量算法第一因素
时间复杂度：算法在最坏环境下所需的基本操作次数与题目规模之间的关系。
1.3.1 对比
假设每行代码实行时间都为t，数据为n个，且是最差的实行环境（实行最多次）：
二分查找：
二分查找实行时间为：5L+4：
既5*floor(log_2(x)+1)+4实行语句实行次数int i=0;1int j=arr.length-1;1return -1;1循环次数为：floor(log_2(n))+1，之后使用L代替i<=j;L+1int m= (i+j)>>>1;Lartget<arrLarr<artgetLi=m+1;L线性查找：
线性查找实行时间为：3x+3实行语句实行次数int i=0;1i<a.length;x+1i++;xarr==targetxreturn -1;1对比工具：Desmos | 图形计算器
对比结果：
https://i-blog.csdnimg.cn/blog_migrate/6f66a0ffc32ce806a3d9d880d4e7031b.png
随着数据规模增长，线性查找实行时间会渐渐超过二分查找。
1.3.2 时间复杂度
计算机科学中，时间复杂度是用来衡量一个算法的实行，随着数据规模增大，而增长的时间资本（不依赖与环境因素）。
时间复杂度的标识：
假设要出炉的数据规模是n，代码总实行行数用f(n)来表示：
线性查找算法的函数：f(n)=3*n+3。
二分查找算法函数：：f(n)=5*floor(log_2(x)+1)+4。
为了简化f(n)，应当捉住主要矛盾，找到一个变革趋势与之相近的表示法。
https://i-blog.csdnimg.cn/blog_migrate/b3285c7434cd86c22073bfaceb49f655.png
https://i-blog.csdnimg.cn/blog_migrate/a9a10eb8cb84db0d00d1464642a2f662.png
1.3.3 渐进上界
渐进上界代表算法实行的最差环境：
以线性查找法为例：
f(n)=3*n+3
g(n)=n
取c=4，在n0=3后，g(n)可以作为f(n)的渐进上界，因此大O表示法写作O(n)
以二分查找为例：
5*floor(log_2(n)+1)+4===》5*floor(log_2(n))+9
g(n)=log_2(n)
O(log_2(n))
https://i-blog.csdnimg.cn/blog_migrate/20df5de6fd57a014e9a96246dcc53f9d.jpeg
1.3.4 常见大O表示法
https://i-blog.csdnimg.cn/blog_migrate/6ab2cbfc2ee0731f15fbc013d167036c.png
按时间复杂度，从低到高：
（1）玄色横线O(1)：常量时间复杂度，意味着算法时间并不随数据规模而变革。
（2）绿色O(log(n))：对数时间复杂度。
（3）蓝色O(n)：线性时间复杂度，算法时间与规模与数据规模成正比。
（4）橙色O(n*log(n))：拟线性时间复杂度。
（5）赤色O(n^2)：平方时间复杂度。
（6）玄色向上O(2^n)：指数时间复杂度。
（7）O(n!)：这种时间复杂度非常大，通常意味着随着输入规模 n 的增长，算法所需的时间会呈指数级增长。因此，具有 O(n!) 时间复杂度的算法在实际应用中每每是不可行的，由于它们必要耗费大量的计算资源和时间。
1.4 衡量算法第二因素
空间复杂度：与时间复杂度雷同，一般也用O衡量，一个算法随着数据规模增大，而增长的额外空间资本。
1.3.1 对比
以二分查找为例：
二分查找占用空间为：4字节实行语句实行次数int i=0;4字节int j=arr.length-1;4字节int m= (i+j)>>>1;4字节二分查找占用空间复杂度为：O(1)性能分析：
时间复杂度：
最坏环境：O(log(n))。
最好环境：待查找元素在数组中央，O(1)。
空间复杂度：必要常熟个数指针：i，j，m，额外占用空间是O(1)。
1.5 二分查找改进
在之前的二分查找算法中，假如数据在数组的最左侧，只必要实行L次 if 就可以了，但是假如数组在最右侧，那么必要实行L次 if 以及L次 else if，所以二分查找向左寻找元素，比向右寻找元素效率要高。
（1）左闭右开的区间，i指向的可能是目标，而j指向的不是目标。
（2）不在循环内找出，等范围内只剩下i时，退出循环，再循环外比较arr与target。
（3）优点：循环内的均匀比较次数减少了。
（4）缺点：时间复杂度：θ(log(n))。
1.6 二分查找相同元素
1.6.1 返回最左侧
当有两个数据相同时，上方的二分查找只会返回中间的元素，而我们想得到最左侧元素就必要对算法举行改进。（Leftmost）
public static void main(String[] args) {
int[] arr = {1, 22, 33, 55, 99, 99, 99, 366, 445, 999};
System.out.println(binarySearchLeftMost1(arr, 99));//结果：4
System.out.println(binarySearchLeftMost1(arr, 999));//结果：9
System.out.println(binarySearchLeftMost1(arr, 998));//结果：-1
}
/**
* @return int 找到相同元素返回返回最左侧查找元素索引，找不到返回-1
* @Description 二分查找LeftMost
* @Author LY
* @Param 待查找升序数组，查找的值
* @Date 2023/12/8 16:38
**/
public static int binarySearchLeftMost1(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < arr) {
j = m - 1;
} else if (arr < target) {
i = m + 1;
} else {
// return m;查找到之后记录下来
candidate=m;
j=m-1;
}
}
return candidate;
} 1.6.2 返回最右侧
当有两个数据相同时，上方的二分查找只会返回中间的元素，而我们想得到最右侧元素就必要对算法举行改进。（Rightmost）
public static void main(String[] args) {
int[] arr = {1, 22, 33, 55, 99, 99, 99, 366, 445, 999};
System.out.println(binarySearchRightMost1(arr, 99));//结果：6
System.out.println(binarySearchRightMost1(arr, 999));//结果：9
System.out.println(binarySearchRightMost1(arr, 998));//结果：-1
}
/**
* @return int 找到相同元素返回返回最右侧侧查找元素索引，找不到返回-1
* @Description 二分查找RightMost
* @Author LY
* @Param 待查找升序数组，查找的值
* @Date 2023/12/8 16:38
**/
public static int binarySearchRightMost1(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < arr) {
j = m - 1;
} else if (arr < target) {
i = m + 1;
} else {
// return m;查找到之后记录下来
candidate=m;
i = m + 1;
}
}
return candidate;
}
1.6.3 优化
将leftMost优化后，可以在未找到目标值的环境下，返回大于等于目标值最靠左的一个索引。
/**
* @return int 找到相同元素返回返回最左侧查找元素索引，找不到返回i
* @Description 二分查找LeftMost
* @Author LY
* @Param 待查找升序数组，查找的值
* @Date 2023/12/8 16:38
**/
public static int binarySearchLeftMost2(int[] arr, int target) {
int i = 0;
int j = arr.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target <= arr) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
} 将rightMost优化后，可以在未找到目标值的环境下，返回小于等于目标值最靠右的一个索引。
1.6.4 应用场景
1.6.4.1 查排名
（1）查找排名：
在实行二分查找时，除了返回目标值是否存在于数组中，还可以记录查找过程中遇到的目标值的位置。假如找到了目标值，则直接返回该位置作为排名；假如没有找到目标值，但知道它应该插入到哪个位置才气保持数组有序，则可以返回这个位置作为排名。
leftMost(target)+1
（2）查找前任（前驱）：
假如目标值在数组中存在，而且不是数组的第一个元素，那么其前任就是目标值左边的一个元素。我们可以在找到目标值之后，再调用一次二分查找函数，这次查找的目标值设置为比当前目标值小一点的数。如许就可以找到目标值左侧最接近它的元素，即前任。
leftMost(target)-1
（3）查找后任（后继）：
假如目标值在数组中存在，而且不是数组的末了一个元素，那么厥后任就是目标值右边的一个元素。雷同地，我们可以在找到目标值之后，再调用一次二分查找函数，这次查找的目标值设置为比当前目标值大一点的数。如许就可以找到目标值右侧最接近它的元素，即后任。
rightMost(target)+1
（3）迩来邻人：
前任和后任中，最接近目标值的一个元素。
1.6.4.2 条件查找元素
（1）小于某个值：0 ~ leftMost(target)-1
（2）小于等于某个值：0 ~ rightMost(target)
（3）大于某个值：rightMost(target)+1 ~ 无穷大
（4）大于等于某个值：leftMost(4) ~ 无穷大
（5）他们可以组合使用。
2. 底子数据结构-数组
2.1 概念
数组是一种数据结构，它是一个由相同范例元素组成的有序集合。在编程中，数组的定义是创建一个具有特定巨细和范例的存储区域来存放多个值。数组可以是一维、二维或多维的。每个元素至少有一个索引或键来标识。
2.2 数组特点
（1）固定巨细：数组的巨细在创建时就被确定下来，而且不能在后续操作中更改。这意味着一旦创建了数组，就不能添加或删除元素（除非使用新的数组来替换旧的数组）。
（2）相同数据范例：数组中的所有元素必须是同一数据范例的。例如，一个整数数组只能存储整数，而不能稠浊着字符串或其他范例的数据。
（3）连续内存空间：数组中的元素在内存中是连续存放的。
（4）索引访问：数组元素是通过索引来访问的，索引通常从0开始。因此，第一个元素的索引是0，第二个元素的索引是1，以此类推。
（5）高效的随机访问：由于数组元素在内存中是连续存放的，所以可以快速地通过索引访问到任何一个元素，时间复杂度为O(1)。
（6）有序性：虽然数组本身并没有规定其元素必须按照特定顺序排列，但通常在编程中会把数组看作是有序的数据结构，由于它的元素是按索引顺序存储的。
（7）可变性：数组中元素值是可改变的，只要该元素的数据范例与数组元素范例兼容即可。
（8）一维、二维或多维：数组可以是一维的（即线性的），也可以是二维或多维的。多维数组通常用于表示表格数据或其他复杂的网格结构。
这些特性使得数组在许多场景下非常有效，尤其是在必要对大量同范例数据举行高效访问和处理的时间。
2.3 数组特点（扩展）
2.3.1 数组的存储
由于数组中的元素在内存中是连续存放的。这意味着可以通过计算每个元素相对于数组开始位置的偏移量来访问它们，从而进步访问速率。 数组起始地点为BaseAddress，可以使用公式BaseAddress+ i *size，计算出索引 i 元素的地点，i 便是索引，java和C等语言中，都是从0开始。size是每个元素占用的字节，例如int占用4字节，double占用8字节。
因此，数组的随机访问和数据规模无关，时间复杂度为O(1)。
2.3.2 空间占用
JAVA的数组结构包含：markword（8字节），class指针（4字节），数组巨细（4字节）。
（1）数组本身是一个对象。每个Java对象都有一个对象头（Object Header），其中包含了类指针和Mark Word等信息。。Mark Word是HotSpot虚拟机计划的一种数据结构，用于存储对象的运行时元数据。
（2）Mark Word的作用主要包罗：
（2.1）对象的锁状态：Mark Word中的部分内容会根据对象是否被锁定而改变。例如，假如数组正在被synchronized同步块或方法保护，那么这部分内容将包含有关锁的信息，如线程ID、锁状态等。
（2.2）垃圾收集信息：Mark Word还存储了与垃圾收集相关的信息，如对象的分代年龄和范例指针等。这对于垃圾收集器跟踪和回收对象非常关键。
其他标记位：除此之外，Mark Word可能还包罗一些其他的标记位，如偏向锁标记、轻量级锁标记等。
（2.3）必要注意的是，由于Mark Word是为整个对象服务的，所以它并不直接针对数组元素。数组元素的数据是存储在对象头之后的实例数据区域中。Mark Word主要是为了支持JVM举行各种操作，好比内存管理和并发控制等。
（3）类指针：类指针指向的是该对象所属的类元数据（Class Metadata）。这个指针对于运行时的动态绑定、方法调用以及反射操作非常紧张。它存储了关于对象范例的所有信息，包罗类名、父类、接口、字段、方法、常量池等。在64位JVM上，类指针通常占用8字节。而在32位JVM上，类指针占用4字节。
（4）数组巨细：数组巨细为4字节，因此决定了数组最大容量为2^32，数组元素+字节对齐（JAVA中所有对象的巨细都是8字节的整数倍，不足的要用对齐字节补足）
例如：
int [] arr={1,2,3,4,5} 该数组包含内容包罗：
单位（字节）
markword（8）class指针（4）数组巨细（4）1（4）2（4）3（4）4（4）5（4）字节对齐（4）巨细为：8+4+4+4*4+4+4=40字节
2.3.3 动态数组
由于数组的巨细是固定的，所以数组中的元素并不能随意地添加和删除。这种数组称之为静态数组。
JAVA中的ArrayList是已经创建好的动态数组。
插入大概删除性能时间复杂度：
头部位置：O(n)
中间位置：O(n)
尾部位置：O(1) 均派来说
package org.alogorithm;
import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;
public class Main02 {
public static void main(String[] args) {
MyArray myArray = new MyArray();
myArray.addLast(1);
myArray.addLast(2);
myArray.addLast(3);
myArray.addLast(4);
myArray.addLast(5);
myArray.addLast(7);
myArray.addLast(8);
myArray.addLast(9);
myArray.addLast(10);
myArray.addLast(11);
/*for (int i = 0; i < myArray.size; i++) {
System.out.println(myArray.array);
}*/
myArray.foreach((e) -> {
//具体操作由调用方界定
System.out.println(e + "Consumer");
});
myArray.add(2, 6);
for (Integer integer : myArray) {
System.out.println(integer + "Iterable");
}
System.out.println(myArray.remove(4)+"元素被删除");
myArray.stream().forEach(e -> {
System.out.println(e + "stream");
});
}
static class MyArray implements Iterable<Integer> {
private int size = 0;//逻辑大小
private int capacity = 8;//容量
private int[] array = {};
public void addLast(int value) {
/*array = value;
size++;*/
add(size, value);
}
public void add(int index, int value) {
//容量不够扩容
checkAndGrow();
/*
* param1 ：要copy的数组
* param1 ：copy的起始位置
* param1 ：要存放数组
* param1 ：要copy的个数
* 这个方法表示要将array从index开始copy到index+1的位置，
* copy的个数是数组的大小-index（index向后的元素）
* */
if (index >= 0 && index <= size) {
System.arraycopy(array, index, array, index + 1, size - index);
}
//合并add方法
array = value;
size++;
}
private void checkAndGrow() {
if (size==0){
array=new int;
}else if (size == capacity) {
capacity+=capacity>>1;
int[] newArray = new int;
//赋值数组
System.arraycopy(array,0,newArray,0,size);
array=newArray;
}
}
//查询元素
public int get(int index) {
return array;
}
//遍历数组 1
//查询元素
public void foreach(Consumer<Integer> consumer) {
for (int i = 0; i < size; i++) {
//System.out.println(array);
//提供array，不需要返回值
consumer.accept(array);
}
}
//遍历数组2 迭代器模式
@Override
public Iterator<Integer> iterator() {
//匿名内部类
return new Iterator<Integer>() {
int i = 0;
@Override
public boolean hasNext() {
//有没有下一个元素
return i < size;
}
@Override
public Integer next() {
//返回当前元素，并将指针移向下一个元素
return array;
}
};
}
//遍历数组3 数据流
public IntStream stream() {
return IntStream.of(Arrays.copyOfRange(array, 0, size));
}
public int remove(int index) {
int removeed = array;
System.arraycopy(array, index + 1, array, index, size - index - 1);
size--;
return removeed;
}
}
} 2.4 二维数组
https://i-blog.csdnimg.cn/blog_migrate/ec8e6349debb528077494e5e93a06ca1.png
（1）二维数组占32个字节，其中array，array，array元素分别生存了指向三个一维数组的引用。
（2）三个一维数组各占40个字节。
（3）他们在内存布局上是连续的。
package org.alogorithm.array;
public class Main03 {
public static void main(String[] args) {
int rows = 1_000_000;
int columns = 14;
int[][] arr = new int;
long ijStar = System.currentTimeMillis();
ij(arr, rows, columns);
long ijEnd = System.currentTimeMillis();
System.out.println("ij执行时间为："+(ijEnd-ijStar));//ij执行时间为：10
long jiStar = System.currentTimeMillis();
ji(arr, rows, columns);
long jiEnd = System.currentTimeMillis();
System.out.println("ji执行时间为："+(jiEnd-jiStar));//ji执行时间为：47
}
public static void ji(int[][] arr, int rows, int columns) {
int sum = 0;
for (int j = 0; j < columns; j++) {
for (int i = 0; i < rows; i++) {
sum += arr;
}
}
System.out.println(sum+"ji");
}
public static void ij(int[][] arr, int rows, int columns) {
int sum = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
sum += arr;
}
}
System.out.println(sum+"ij");
}
}
在计算机中，内存是分块存储的。每个内存块称为一个页（page）。当程序访问数组时，CPU会从内存中加载包含该元素所在的整个页面到高速缓存（cache）中。
在这个例子中，ij和ji两个方法的主要区别在于它们遍历数组的方式：
ij按行遍历数组：它首先遍历所有的行，然后在同一行内遍历列。
ji按列遍历数组：它先遍历所有的列，然后在同一列内遍历行。
由于现代计算机体系结构的计划特点，ij比ji更快的缘故原由有以下几点：
（1）缓存局部性（Cache Locality）：按行遍历数组时，相邻的元素在物理内存中相互靠近，这使得CPU可以高效地使用缓存来加快数据访问。这是由于通常环境下，一次内存读取操作将加载一整块数据（通常是64字节），假如这一块数据中的多个元素被连续使用，那么这些元素很可能都在同一块缓存中，从而减少了对主内存的访问次数。
（2）预取（Prefetching）：一些现代处理器具有预取机制，可以猜测接下来可能必要的数据并提前将其加载到缓存中。按照行顺序遍历数组时，这种机制更有可能发挥作用，由于相邻的元素更可能在将来被访问。
综上所述，ij的遍历方式更得当计算机硬件的工作原理，因此实行速率更快。
3 底子数据结构-链表
3.1 定义
链表（Linked List）是一种线性数据结构，由一系列节点（Node）组成。每个节点包含两部分：元素值（Element Value）和指向下一个节点的指针（Pointer）。链表可以分为多种范例，如单向链表、双向链表、循环链表等。元素在存储上并不连续。
3.1.1 分类
（1）单向链表：每个元素只知道下一个元素。
（2）双向链表：每个元素知道下一个元素和上一个元素。
（3）循环链表：通常的链表为节点tail指向null，但是循环链表的tail指向head。
3.1.2 哨兵节点
https://i-blog.csdnimg.cn/blog_migrate/31b87105e200ba4de23a9bba23539b17.png
链表内另有一种特别的节点，成为哨兵（Sentinel）节点，也叫做哑元（Dummy）节点，他并不存储数据，用来减缓别介判定。
3.2 性能
随机访问：
根据index查找，时间复杂度O(n)。
插入大概删除：
起始位置：O(1)。
竣事位置：假如已知tail为节点是O(1)，否则为O(n)。
中间位置：根据index查找时间+O(1)。
3.3 单向链表
单向链表的主要操作包罗：
插入节点：在链表的特定位置插入一个新的节点。
删除节点：从链表中删除一个特定的节点。
查找节点：在链表中查找一个特定的节点。
遍历链表：从头到尾访问链表中的每个节点。
单向链表的优点包罗：
动态性：可以随时添加或删除节点，不必要预先知道数据的数目和巨细。
效率：插入和删除操作通常只必要常数时间。
缺点包罗：
访问速率：访问链表中的特定元素必要从头开始遍历，时间复杂度为O(n)。
空间效率：每个节点都必要额外的空间来存储指针。
3.3.1 普通单向链表实现
package org.alogorithm.linkedList;
import java.util.Iterator;
import java.util.function.Consumer;
public class SingLinkListMain {
public static void main(String[] args) {
SingLinkList singLinkList = new SingLinkList();
singLinkList.addFirst(1);
singLinkList.addFirst(2);
singLinkList.addFirst(3);
singLinkList.addFirst(4);
singLinkList.addFirst(5);
//使用Consumer+while实现
singLinkList.consumerLoop1(value -> System.out.println(value + "while,"));
System.out.println("----------------------------------------");
singLinkList.addLast(99);//尾部添加一个元素
singLinkList.addLast(100);//尾部添加一个元素
//使用Consumer+for实现
singLinkList.consumerLoop2(value -> System.out.println(value + "for"));
System.out.println("----------------------------------------");
int res = singLinkList.get(3);
System.out.println("查询结果为" + res);
singLinkList.insert(0, 111);
singLinkList.insert(3, 111);
//使用迭代器实现
for (Integer integer : singLinkList) {
System.out.println(integer + "iterable");
}
System.out.println("----------------------------------------");
/*int reserr = singLinkList.get(100);
System.out.println("查询结果为"+reserr);*/
// singLinkList.removeFirst();//删除第一个节点
singLinkList.reomve(0);
singLinkList.reomve(3);
singLinkList.reomve(99);
//使用递归
singLinkList.recursionLoop(e -> {
System.out.println(e + "recursion");
}, singLinkList.head);
// System.out.println(singLinkList.findLast());
}
}
//单向链表
class SingLinkList implements Iterable<Integer> {
// head指针
Node head;
//删除指定索引节点
public void reomve(int index) {
if (index < 0) {
IndexOutOfBoundsException(head, "索引不能为负");
} else if (index == 0) {
removeFirst();
}
Node node = findNode(index);//当前个节点
IndexOutOfBoundsException(node, "当前节点为空");
Node beforNode = findNode(index - 1);//上一个节点
beforNode.next = node.next;
}
//删除第一个节点
public void removeFirst() {
IndexOutOfBoundsException(head, "链表为空无");
head = head.next;//将head设置为之前的head.next第二个节点
}
//向索引位置添加一个元素
public void insert(int index, int value) {
Node afterNode = findNode(index);//后一个节点
//构建新的节点
Node newNode = new Node(value, afterNode);
if (index == 0) {
//索引为0向头部添加
addFirst(value);
} else {
Node beforNode = findNode(index - 1);
//否则将befor的next属性设置为当前节点
IndexOutOfBoundsException(beforNode, "索引位置异常");
beforNode.next = newNode;
}
}
//抛出异常
private static void IndexOutOfBoundsException(Node beforNode, String msg) {
if (beforNode == null) {
throw new IndexOutOfBoundsException(msg);
}
}
//获取节点的值
public int get(int index) {
Node node = findNode(index);
IndexOutOfBoundsException(node, "索引位置异常");
return node.value;
}
//获取索引的元素
private Node findNode(int index) {
Node point = head;
int i = 0;
while (point != null) {
if (i == index) {
return point;
} else {
point = point.next;
i++;
}
}
return null;
}
//向最后添加一个元素
public void addLast(int value) {
Node last = findLast();//找到最后一个节点
if (last == null) {
//没有最后一个就添加第一个
addFirst(value);
} else {
//否则设置最有一个节点的next属性为新的Node
last.next = new Node(value, null);
}
}
//查找最后一个元素
public Node findLast() {
Node point = head;
if (head == null) {
return null;
}
while (true) {
if (point.next != null) {
point = point.next;
} else {
return point;
}
}
}
//头部添加一个元素
public void addFirst(int value) {
//链表为空
// head =new Node(value,null);
//链表非空
head = new Node(value, head);//链表为空时head就是null
}
public void recursionLoop(Consumer<Integer> consumer, Node point) {
if (point != null) {
consumer.accept(point.value); // 先输出当前节点的值
recursionLoop(consumer, point.next); // 再递归处理下一个节点
}
}
//迭代器遍历
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node point = head;
@Override
public boolean hasNext() {
return point != null;
}
@Override
public Integer next() {
int value = point.value;
point = point.next;
return value;
}
};
}
//循环遍历 for
public void consumerLoop2(Consumer<Integer> consumer) {
for (Node point = head; point != null; point = point.next) {
consumer.accept(point.value);
}
}
//循环遍历 while
public void consumerLoop1(Consumer<Integer> consumer) {
Node point = head;
while (point != null) {
consumer.accept(point.value);
point = point.next;
}
}
//节点
private static class Node {
int value;//值
Node next;//下一个节点
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
}
这是一个普通单向链表的全部功能实现，但是实现起来比较麻烦。
补充：关于类需不必要带static：
（1）Node内部类可以添加static关键字，这是由于Java答应在类中定义静态成员。将内部类声明为静态的，意味着它不再依赖于外部类的实例。
（2）静态内部类不能访问外部类的非静态成员（包罗字段和方法）。
（3）由于不依赖外部类实例，创建静态内部类的对象不必要外部类对象。
3.3.2 单向链表-带哨兵
加入哨兵之后，就不存在head为空的环境，也不存在链表为空，某个节点上一个元素为空，插入头部时链表为空的环境，但是对应的循环遍历要从head.next开始，可以简化许多代码。
public class SingLinkSentryListMain {
public static void main(String[] args) {
SingLinkSentryList singLinkSentryList = new SingLinkSentryList();
singLinkSentryList.addLast(69);
singLinkSentryList.addLast(70);
//使用Consumer+while实现
singLinkSentryList.consumerLoop1(value -> System.out.println(value + "while,"));
System.out.println(singLinkSentryList.get(0));
//System.out.println(singLinkSentryList.get(99));
singLinkSentryList.insert(0,99);
// singLinkSentryList.insert(99,99);
System.out.println("----------------------------------------");
//使用Consumer+for实现
singLinkSentryList.consumerLoop2(value -> System.out.println(value + "for"));
System.out.println("----------------------------------------");
singLinkSentryList.reomve(1);
singLinkSentryList.reomve(0);
// singLinkSentryList.reomve(99);
//使用迭代器实现
for (Integer integer : singLinkSentryList) {
System.out.println(integer + "iterable");
}
System.out.println("----------------------------------------");
//使用递归
/* singLinkSentryList.recursionLoop(e -> {
System.out.println(e + "recursion");
}, singLinkSentryList.head);*/
}
}
//单向链表
class SingLinkSentryList implements Iterable<Integer> {
// head指针
Node head=new Node(1,null);//头指针指向哨兵
//删除指定索引节点
public void reomve(int index) {
if (index < 0) {
IndexOutOfBoundsException(head, "索引不能为负");
}
Node node = findNode(index);//当前个节点
IndexOutOfBoundsException(node, "当前节点为空");
Node beforNode = findNode(index - 1);//上一个节点
beforNode.next = node.next;
}
//删除第一个节点
public void removeFirst() {
IndexOutOfBoundsException(head, "链表为空无");
reomve(0);
}
//向索引位置添加一个元素
public void insert(int index, int value) {
Node afterNode = findNode(index);//后一个节点
//构建新的节点
Node newNode = new Node(value, afterNode);
Node beforNode = findNode(index - 1);
//否则将befor的next属性设置为当前节点
IndexOutOfBoundsException(beforNode, "索引位置异常");
beforNode.next = newNode;
}
//抛出异常
private static void IndexOutOfBoundsException(Node beforNode, String msg) {
if (beforNode == null) {
throw new IndexOutOfBoundsException(msg);
}
}
//获取节点的值
public int get(int index) {
Node node = findNode(index);
IndexOutOfBoundsException(node, "索引位置异常");
return node.value;
}
//获取索引的元素
private Node findNode(int index) {
Node point = head;
int i = -1;
while (point != null) {
if (i == index) {
return point;
} else {
point = point.next;
i++;
}
}
return null;
}
//向最后添加一个元素
public void addLast(int value) {
Node last = findLast();//因为有哨兵，head不可能为空
last.next = new Node(value, null);
}
//查找最后一个元素
public Node findLast() {
Node point = head;
while (true) {
if (point.next != null) {
point = point.next;
} else {
return point;
}
}
}
//头部添加一个元素
public void addFirst(int value) {
insert(0,value);
}
public void recursionLoop(Consumer<Integer> consumer, Node point) {
if (point != null) {
consumer.accept(point.value); // 先输出当前节点的值
recursionLoop(consumer, point.next); // 再递归处理下一个节点
}
}
//迭代器遍历
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node point = head.next;
@Override
public boolean hasNext() {
return point != null;
}
@Override
public Integer next() {
int value = point.value;
point = point.next;
return value;
}
};
}
//循环遍历 for
public void consumerLoop2(Consumer<Integer> consumer) {
for (Node point = head.next; point != null; point = point.next) {
consumer.accept(point.value);
}
}
//循环遍历 while
public void consumerLoop1(Consumer<Integer> consumer) {
Node point = head.next;
while (point != null) {
consumer.accept(point.value);
point = point.next;
}
}
//节点
private static class Node {
int value;//值
Node next;//下一个节点
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
} 3.4 双向链表
双向链表相比单向链表有以下上风：
双向访问：在双向链表中，每个节点都有两个指针，一个指向前一个节点（前驱），一个指向后一个节点（后继）。这使得在遍历或操作链表时可以向前或向后移动，提供了更大的灵活性。在某些环境下，这种双向访问能力可以简化算法并进步效率。
更方便的插入和删除操作：虽然在双向链表中插入和删除节点必要更新两个相邻节点的指针，但有时这反而能更快地完成操作。例如，假如已知要删除的节点，那么可以直接通过其前驱节点举行删除，无需从头开始查找。
更高效的搜索和定位：在某些搜索和定位操作中，双向链表的上风更加明显。例如，假如要查找某个特定节点的前驱节点，单向链表必要从头开始遍历，而双向链表可以直接通过当前节点访问其前驱节点。
尾节点操作：对尾结点操作更加方便而不消遍历查找到末了一个节点。
双向链表缺点：
空间开销：每个节点在单向链表的底子上都必要额外的空间来存储指向前一个节点的指针。
操作复杂性：在插入和删除节点时，必要更新两个相邻节点的指针，这在肯定程度上增长了操作的复杂性。
3.4.1 双向链表-带哨兵
package org.alogorithm.linkedList;
import java.util.Iterator;
/**
* 双向链表（带哨兵）
**/
public class DoubleLinkedListMain {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.addFirst( 1);
doubleLinkedList.add(1, 2);
doubleLinkedList.add(2, 3);
doubleLinkedList.add(3, 4);
System.out.println("-------------add-----------------");
for (Integer integer : doubleLinkedList){
System.out.println(integer);
}
doubleLinkedList.remove(2);
System.out.println("-------------remove-----------------");
for (Integer integer : doubleLinkedList){
System.out.println(integer);
}
doubleLinkedList.addLast(20);
System.out.println("-----------addLast------------------");
for (Integer integer : doubleLinkedList){
System.out.println(integer);
}
doubleLinkedList.remove(1);
System.out.println("-------remove---------------------");
for (Integer integer : doubleLinkedList){
System.out.println(integer);
}
doubleLinkedList.removeLast();
System.out.println("----------removeLast-------------------");
for (Integer integer : doubleLinkedList){
System.out.println(integer);
}
}
}
class DoubleLinkedList implements Iterable<Integer>{
private Node head;//头部哨兵
private Node tail;//尾部哨兵
public DoubleLinkedList() {
head = new Node(null, 0, null);//头哨兵赋值
tail = new Node(head, 0, null);//尾哨兵赋值
head.next = tail;
}
//操作尾节点
public void removeLast(){
Node node = tail.prev;//要删除的节点
if(node==head){
IndexOutOfBoundsException(head.prev,"当前链表为空");
}
Node prevNode = node.prev;//上一个节点
prevNode.next=tail;//上一个节点的next指向为哨兵
tail.prev=prevNode;//尾哨兵的prev的像一个节点为prevNode
}
public void addLast(int value){
Node lastNode = tail.prev;//原本最后一个节点
Node node = new Node(lastNode, value, tail);
lastNode.next=node;//原本节点下一个节点指向当前节点
tail.prev=node;//尾哨兵上一个节点设置为当前节点
}
public void removeFirst() {
remove(0);
}
public void remove(int index) {
Node prevNode = findNode(index - 1);//上一个节点
IndexOutOfBoundsException(prevNode, "非法指针，指针异常");
Node node = prevNode.next;//待删除节点
IndexOutOfBoundsException(node, "非法指针，待删除节点为空");
Node nextNode = node.next;//下一个节点
prevNode.next = nextNode;//上一个节点的next指针指向nextNode
nextNode.prev = prevNode;//下一个节点的prev指针指向prevNode
}
public void addFirst(int value) {
add(0, value);
}
//根据索引插入值
public void add(int index, int value) {
Node prevNode = findNode(index - 1);//查找原本节点
IndexOutOfBoundsException(prevNode, "非法指针，指针异常");
Node next = prevNode.next;
Node newNode = new Node(prevNode, value, next);//设置prev节点为oldNode的prev节点，next节点为oldNode节点
prevNode.next = newNode;//设置前节点的后一个节点为当前节点
next.prev = newNode;//设置oldNode的上一个节点为当前节点
}
//查找索引对应的节点
public Node findNode(int index) {
int i = -1;
//当p不是尾哨兵时循环继续
for (Node p = head; p != tail; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
//抛出异常
private static void IndexOutOfBoundsException(Node node, String msg) {
if (node == null) {
throw new IndexOutOfBoundsException(msg);
}
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
//设置起始指针
Node p = head.next;
@Override
public boolean hasNext() {
return p!= tail;
}
@Override
public Integer next() {
int value=p.value;
p=p.next;
return value;
}
};
}
static class Node {
Node prev;//上一个节点指针
int value;//值
Node next;//下一个节点指针
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
}
3.6环形链表
环形链表，也称为循环链表，是一种特别的链表数据结构。在环形链表中，末了一个节点的指针不再指向空（NULL），而是指向链表中的某个节点，通常是头节点，形成一个环状结构。
以下是对环形链表的主要特性和操作的描述：
特性： 结构：环形链表可以是单向的或双向的。在单向环形链表中，每个节点包含一个指针指向下一个节点；在双向环形链表中，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点（head节点既作为头也作为尾）。
环：链表的末了一个节点的指针不指向空，而是指向链表中的另一个节点，形成了一个环。这意味着从任何节点开始遍历，假如不做特别处理，将会无限循环下去。
遍历：由于环的存在，普通遍历方法（如递归或迭代）假如不做特别处理，将无法自然地终止。
3.5.1 双向环形链表
3.7 差异链表的特性
单向链表：
结构：每个节点包含一个指针，指向下一个节点。
访问：只能从头节点开始向尾节点举行单向遍历。
插入和删除操作：必要从头节点或已知的节点开始查找目标位置，操作相对复杂。
空间复杂性：每个节点只必要存储一个指向下一个节点的指针，空间开销较小。
应用场景：适用于不必要频繁修改且对空间效率要求较高的场景。
双向链表：
结构：每个节点包含两个指针，一个指向前一个节点（前驱），一个指向后一个节点（后继）。
访问：可以双向访问，即可以从头节点遍历到尾节点，也可以从尾节点反向遍历到头节点。
插入和删除操作：在已知要插入或删除节点的前后节点时，操作更快，由于可以直接通过前驱或后继节点举行修改。
空间复杂性：每个节点必要额外的空间来存储前驱和后继指针，所以空间开销比单向链表大。
应用场景：适用于必要频繁双向访问、搜索和定位操作的场景。
双向循环链表：
结构：雷同于双向链表，但尾节点的后继指针指向头节点，而头节点的前驱指针指向尾节点，形成一个环状结构。
访问：可以双向无限循环访问，从任意节点开始都可以遍历整个链表。
插入和删除操作：与双向链表雷同，但在处理首尾节点的操作时必要特别处理，确保环的完整性。
空间复杂性：与双向链表相同，每个节点必要额外的空间来存储前驱和后继指针。
应用场景：适用于必要循环遍历、模仿环形数据结构大概必要在到达链表尾部后自动返回头部的场景。
4.底子数据结构-队列
4.1 概述
队列是一种底子且广泛应用的线性数据结构，它模仿了现实生存中的列队现象，遵循“先进先出”（First-In-First-Out, FIFO）原则。在队列中，元素的添加和移除遵循特定的顺序：
入队操作（Enqueue）：新元素被添加到队列的尾部（称为队尾或rear），意味着迩来到达的元素将排在队列的末尾等待处理。
出队操作（Dequeue）：从队列的头部（称为队头或front）移除元素，确保开始到达的元素开始离开队列并被处理。
队列的主要特性包罗：
线性结构：队列中的元素按肯定的顺序排列。
动态变革：队列的巨细可以随着元素的入队和出队而动态改变。
有限或无限容量：取决于实现方式，队列可能有预先设定的最大容量（如固定巨细的数组实现），也可以理论上支持无限数目的元素（如链表实现）。
队列在计算机科学中有多种应用，例如使命调理、消息通报、打印机使命管理、缓冲区管理等场合，都使用了其有序和公平的特性来组织和处理数据流。队列可以用数组或链表等多种数据结构来实现，而且根据应用场景的差异，还发展出了优先队列、循环队列、双端队列等多种变体。
队列接口
package org.alogorithm.queue;
public interface Queue<E> extends Iterable<E> {
/**
* @Description 向队尾插入值
* @Author LY
* @Param 待插入的值
* @return boolean 是否成功
* @Date 2024/1/18 9:53
**/
boolean offer(E value);
/**
* @Description 从队头获取值，并移除
* @Author LY
* @return E 如果队列非空，返回队头值，否则返回null
* @Date 2024/1/18 9:53
**/
E pool();
/**
* @Description 从队头获取值，不移除
* @Author LY
* @return E 如果队列非空，返回队头值，否则返回null
* @Date 2024/1/18 9:55
**/
E peek();
/**
* @Description检查队列是否为空
* @Author LY
* @return boolean 空返回true，否则返回false
* @Date 2024/1/18 9:55
**/
boolean isEmpty();
/**
* @Description 队列是否满已满
* @Author LY
* @return boolean 满 true 否则 false
* @Date 2024/1/18 11:34
**/
boolean isFull();
}
4.2 链表实现
public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {
public static void main(String[] args) {
LinkedListQueue<Integer>queue=new LinkedListQueue<Integer>(1);
Integer peek1 = queue.peek();
boolean empty1 = queue.isEmpty();
//向尾部添加开始
boolean offer1 = queue.offer(1);
boolean offer2 = queue.offer(2);
//向尾部添加结束
boolean empty2 = queue.isEmpty();
Integer peek2 = queue.peek();
Integer pool1 = queue.pool();
Integer pool2 = queue.pool();
}
@Override
public boolean offer(E value) {
//满了
if(isFull()){
return false;
}
//新节点.next指向头
Node newNode = new Node(value, head);
//原尾节点.next指向新节点
tail.next = newNode;
//tail指向新节点
tail = newNode;
size++;
return true;
}
@Override
public E pool() {
if(this.isEmpty()){
return null;
}
Node<E> first=head.next;
head.next=first.next;
//如果是最后一个节点
if(first==tail){
tail=head;
}
size--;
return first.value;
}
@Override
public E peek() {
if(this.isEmpty()){
return null;
}
return head.next.value;
}
@Override
public boolean isEmpty() {
return tail==head;
}
@Override
public boolean isFull() {
return size==capacity;
}
//节点类
private static class Node<E> {
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.next = next;
this.value = value;
}
}
@Override
public Iterator iterator() {
return new Iterator<E>() {
Node<E>p=head.next;
@Override
public boolean hasNext() {
return p.next!=head;
}
@Override
public E next() {
E value=p.value;
return value;
}
};
}
Node<E> head = new Node<E>(null, null);
Node<E> tail = head;
//当前大小
private Integer size=0;
//容量
private Integer capacity =Integer.MAX_VALUE;
{
tail.next = head;
}
public LinkedListQueue(Integer capacity) {
this.capacity = capacity;
}
public LinkedListQueue() {
}
} 4.3 环形数组实现
使用环形数组而不是线性数组的缘故原由：
空间使用率：
在普通线性数组中实现队列时，假如队列的头部和尾部相隔较远（例如，头指针在前而尾指针在后接近数组末尾），中间会有许多未使用的空间。当尾指针到达数组末尾时，若没有足够的空间添加新元素，即使数组前面有空闲位置也无法继续入队，这就出现了所谓的“假溢出”题目。
环形数组通过计算下标时取模（即循环访问数组）的方式，使得队列的尾部可以“绕回”到数组的头部，如许就可以充分使用整个数组空间，制止了假溢出。
高效性：
环形队列的所有操作（入队、出队）理论上都可以在常数时间内完成（O(1)复杂度）。这是由于可以通过预先设定好的固定巨细的数组，而且维护好头指针和尾指针，直接在对应的位置举行插入和删除操作，无需像线性数组那样可能必要移动大量元素以腾出或弥补空间。
适用于及时体系和硬件实现：
环形队列因其简单高效的特性，在及时操作体系、网络通讯、多线程间同步通讯等场合被广泛应用。例如在网络装备中，数据包的接收和发送经常使用环形缓冲区（即环形队列的一种形式）来缓存和处理数据流，如许可以确保在高频率的数据交换过程中，不会由于频繁地申请释放内存而导致性能降落或不可猜测的举动。
4.3.1 环形数组实现1
必要思量当前数组满了的环境下头尾指针指向的位置。
package org.alogorithm.queue;
import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;
public class ArrayQueue1<E> implements Queue<E>{
public static void main(String[] args) {
ArrayQueue1<Integer>queue=new ArrayQueue1<Integer>(1);
Integer peek1 = queue.peek();
boolean empty1 = queue.isEmpty();
//向尾部添加开始
boolean offer1 = queue.offer(1);
boolean offer2 = queue.offer(2);
//向尾部添加结束
boolean empty2 = queue.isEmpty();
Integer peek2 = queue.peek();
Integer pool1 = queue.pool();
Integer pool2 = queue.pool();
}
private E[] arr;
private int head=0;
private int tail=0;
//抑制警告产生
@SuppressWarnings("all")
public ArrayQueue1(int capacity) {
this.arr = (E[]) new Object;
}
@Override
public boolean offer(E value) {
if(isFull()){
return false;
}
arr=value;
//防止当前元素时最后一个
tail=(tail+1)% arr.length;
return true;
}
@Override
public E pool() {
if(isEmpty()){
return null;
}
E e = arr;
head=(head+1)%arr.length;
return e;
}
@Override
public E peek() {
if(isEmpty()){return null;
}
return arr;
}
@Override
public boolean isEmpty() {
return tail==head;
}
@Override
public boolean isFull() {
return (tail+1)%arr.length==head;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p=head;
@Override
public boolean hasNext() {
return p!=tail;
}
@Override
public E next() {
E e = arr;
p=(p+1)% arr.length;
return e;
}
};
}
}
4.3.2 环形数组实现2
增长一个size属性，生存全部元素个数，新建数组时巨细，判定满和空，添加元素，移除元素做出相应修改。迭代时也应该增长一个count属性。
public class ArrayQueue2<E> implements Queue<E>{
public static void main(String[] args) {
ArrayQueue2<Integer> queue=new ArrayQueue2<Integer>(1);
Integer peek1 = queue.peek();
boolean empty1 = queue.isEmpty();
//向尾部添加开始
boolean offer1 = queue.offer(1);
boolean offer2 = queue.offer(2);
//向尾部添加结束
boolean empty2 = queue.isEmpty();
Integer peek2 = queue.peek();
Integer pool1 = queue.pool();
Integer pool2 = queue.pool();
}
private E[] arr;
private int head=0;
private int tail=0;
//元素个数
private int size=0;
//抑制警告产生
@SuppressWarnings("all")
public ArrayQueue2(int capacity) {
this.arr = (E[]) new Object;
}
@Override
public boolean offer(E value) {
if(isFull()){
return false;
}
arr=value;
//防止当前元素时最后一个
tail=(tail+1)% arr.length;
size++;
return true;
}
@Override
public E pool() {
if(isEmpty()){
return null;
}
E e = arr;
head=(head+1)%arr.length;
size--;
return e;
}
@Override
public E peek() {
if(isEmpty()){return null;
}
return arr;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public boolean isFull() {
return size==arr.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p=head;
int count=0;
@Override
public boolean hasNext() {
return count<size;
}
@Override
public E next() {
E e = arr;
p=(p+1)% arr.length;
count++;
return e;
}
};
}
} 4.3.3 环形数组实现3
基于方式1，做出优化，head和tail一直递增，使用时在举行计算。
当索引超出int最大值会出现索引为负数的题目。
必要单独处理(int) Integer.toUnsignedLong()。
方法1
public class ArrayQueue3<E> implements Queue<E>{
public static void main(String[] args) {
ArrayQueue3<Integer> queue=new ArrayQueue3<Integer>(1);
Integer peek1 = queue.peek();
boolean empty1 = queue.isEmpty();
//向尾部添加开始
boolean offer1 = queue.offer(1);
boolean offer2 = queue.offer(2);
//向尾部添加结束
boolean empty2 = queue.isEmpty();
Integer peek2 = queue.peek();
Integer pool1 = queue.pool();
Integer pool2 = queue.pool();
}
private E[] arr;
private int head=0;
private int tail=0;
//抑制警告产生
@SuppressWarnings("all")
public ArrayQueue3(int capacity) {
this.arr = (E[]) new Object;
}
@Override
public boolean offer(E value) {
if(isFull()){
return false;
}
arr[(int) Integer.toUnsignedLong(tail% arr.length)]=value;
//防止当前元素时最后一个
tail++;
return true;
}
@Override
public E pool() {
if(isEmpty()){
return null;
}
E e = arr[(int) Integer.toUnsignedLong(head% arr.length)];
head++;
return e;
}
@Override
public E peek() {
if(isEmpty()){return null;
}
return arr[(int) Integer.toUnsignedLong(head%arr.length)];
}
@Override
public boolean isEmpty() {
return tail==head;
}
@Override
public boolean isFull() {
return tail-head== arr.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p=head;
@Override
public boolean hasNext() {
return p!=tail;
}
@Override
public E next() {
E e = arr[(int) Integer.toUnsignedLong(p% arr.length)];
p++;
return e;
}
};
}
}
方法2
对于求模运算来讲（二进制）：
假如除数是2的n次方，那么被除数的后n为即为余数（模）。
求除数后的n位方法：与2^n-1 按位与
题目：传入数组长度不肯定是2^n，可以抛出非常大概转为比入参大最接近的一个2^n次方值，判定一个数是否是2^n可以与该值-1举行按位与，假如结果为0则是2^n，否则则不是。
public class ArrayQueue3_2<E> implements Queue<E>{
public static void main(String[] args) {
ArrayQueue3_2<Integer> queue=new ArrayQueue3_2<Integer>(1);
Integer peek1 = queue.peek();
boolean empty1 = queue.isEmpty();
//向尾部添加开始
boolean offer1 = queue.offer(1);
boolean offer2 = queue.offer(2);
//向尾部添加结束
boolean empty2 = queue.isEmpty();
Integer peek2 = queue.peek();
Integer pool1 = queue.pool();
Integer pool2 = queue.pool();
}
private E[] arr;
private int head=0;
private int tail=0;
//抑制警告产生
@SuppressWarnings("all")
public ArrayQueue3_2(int capacity) {
//方式1
/*if((capacity&capacity-1)!=0){
throw new IllegalArgumentException("长度必须为2的n次方");
}*/
//方法2
/*
* 求以2为底capacity的对数+1
*
* */
/*int res = (int) (Math.log10(capacity-1) / Math.log10(2))+1;
int i = 1 << res;*/
capacity-=1;
capacity|=capacity>>1;
capacity|=capacity>>2;
capacity|=capacity>>4;
capacity|=capacity>>8;
capacity|=capacity>>16;
capacity+=1;
this.arr = (E[]) new Object;
}
@Override
public boolean offer(E value) {
if(isFull()){
return false;
}
arr=value;
//防止当前元素时最后一个
tail++;
return true;
}
@Override
public E pool() {
if(isEmpty()){
return null;
}
E e = arr;
head++;
return e;
}
@Override
public E peek() {
if(isEmpty()){return null;
}
return arr;
}
@Override
public boolean isEmpty() {
return tail==head;
}
@Override
public boolean isFull() {
return tail-head== arr.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p=head;
@Override
public boolean hasNext() {
return p!=tail;
}
@Override
public E next() {
E e = arr;
p++;
return e;
}
};
}
} 5.底子数据结构-栈
5.1 相关概念
数据结构栈（Stack）是一种特别的线性表：
栈顶（Top）： 栈顶是指栈中最靠近“出口”或“操作端”的那个位置。新元素总是被压入（push）到栈顶，当举行弹出（pop）操作时，也是从栈顶移除元素。因此，栈顶始终指向当前栈内的末了一个加入的元素。
栈底（Bottom）： 栈底则是指栈中固定不变的那个位置，通常是在创建栈时初始化的第一个位置，也可以明白为栈中最早加入的那些元素所在的位置。在实际操作中，栈底不发生变革，除非整个栈为空大概重新初始化。
后进先出（Last In First Out, LIFO）：
末了被压入（push）到栈中的元素将是第一个被弹出（pop）的元素。这意味着在没有其他操作的环境下，栈顶元素总是末了被添加的那一个。
受限的插入和删除操作：
栈只答应在栈顶举行插入（称为“压入”或"push"操作）和删除（称为“弹出”或"pop"操作）。不能直接访问或修改栈内的中间元素。
5.2 接口
public interface Stock<E> extends Iterable<E> {
/**
* @Description 向栈压入元素
* @Author LY
* @Param 待压入的值
* @return boolean 是否成功
* @Date 2024/1/18 9:53
**/
boolean push(E value);
/**
* @Description 从栈顶弹出元素
* @Author LY
* @return E 如果栈非空，返回栈顶元素，否则返回null
* @Date 2024/1/18 9:53
**/
E pop();
/**
* @Description 返回栈顶元素，不弹出
* @Author LY
* @return E 如果栈非空，返回栈顶元素，否则返回null
* @Date 2024/1/18 9:55
**/
E peek();
/**
* @Description检查栈是否为空
* @Author LY
* @return boolean 空返回true，否则返回false
* @Date 2024/1/18 9:55
**/
boolean isEmpty();
/**
* @Description 栈是否满已满
* @Author LY
* @return boolean 满 true 否则 false
* @Date 2024/1/18 11:34
**/
boolean isFull();
}
5.3 链表实现
public class LinkedListStock<E> implements Stock<E>{
public static void main(String[] args) {
LinkedListStock<Integer>stock=new LinkedListStock<>(2);
boolean empty1 = stock.isEmpty();
boolean full1 = stock.isFull();
boolean push1 = stock.push(1);
boolean push2 = stock.push(2);
boolean push3 = stock.push(3);
boolean empty2 = stock.isEmpty();
boolean full2 = stock.isFull();
Integer peek1 = stock.peek();
Integer pop1 = stock.pop();
Integer pop2 = stock.pop();
Integer pop3 = stock.pop();
Integer peek2 = stock.peek();
}
//容量
private int capatity=Integer.MAX_VALUE;
//元素个数
private int size=0;
private Node head=new Node(null,null);
public LinkedListStock() {
}
public LinkedListStock(int capatity) {
this.capatity = capatity;
}
staticclass Node<E>{
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.value = value;
this.next = next;
}
}
@Override
public boolean push(E value) {
if(isFull()){
return false;
}
Node node = new Node(value, head.next);
head.next=node;
size++;
return true;
}
@Override
public E pop() {
if(isEmpty()){
return null;
}
Node<E> first = head.next;
head.next=first.next;
size--;
return first.value;
}
@Override
public E peek() {
if(isEmpty()){
return null;
}
Node<E> first = head.next;
return first.value;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public boolean isFull() {
return size==capatity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p=head;
@Override
public boolean hasNext() {
return p!=null;
}
@Override
public E next() {
E value = p.value;
p=p.next;
return value;
}
};
}
} 5.4 数组实现
public class ArrayStock<E> implements Stock<E>{
public static void main(String[] args) {
ArrayStock<Integer> stock=new ArrayStock<>(2);
boolean empty1 = stock.isEmpty();
boolean full1 = stock.isFull();
boolean push1 = stock.push(1);
boolean push2 = stock.push(2);
boolean push3 = stock.push(3);
boolean empty2 = stock.isEmpty();
boolean full2 = stock.isFull();
Integer peek1 = stock.peek();
Integer pop1 = stock.pop();
Integer pop2 = stock.pop();
Integer pop3 = stock.pop();
Integer peek2 = stock.peek();
}
private E[]arr;
private int top;
//容量
private int capatity=Integer.MAX_VALUE;
public ArrayStock() {
}
@SuppressWarnings("all")
public ArrayStock(int capatity) {
this.arr = (E[]) new Object;
this.capatity=capatity;
}
@Override
public boolean push(E value) {
if(isFull()){
return false;
}
/* arr=value;
top++;*/
arr=value;
return true;
}
@Override
public E pop() {
if(isEmpty()){
return null;
}
E e = arr[--top];
return e;
}
@Override
public E peek() {
if(isEmpty()){
return null;
}
return arr;
}
@Override
public boolean isEmpty() {
return top==0;
}
@Override
public boolean isFull() {
return top==capatity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p=top;
@Override
public boolean hasNext() {
return p>0;
}
@Override
public E next() {
return arr[--p];
}
};
}
}
6.其他队列
6.1 对比
双端队列（Double-Ended Queue, deque）、栈（Stack）和队列（Queue）是三种基本且紧张的数据结构，它们各自具有差异的操作特性和使用场景：
栈 (Stack)：
结构特点：栈是一种后进先出（Last-In-First-Out, LIFO）的数据结构，它只答应在一端举行插入和删除操作。这一端通常称为栈顶。
操作特性：主要支持push（入栈，将元素添加到栈顶）、pop（出栈，移除并返回栈顶元素）以及peek（检察栈顶元素但不移除）等操作。
应用场景：栈常用于实现函数调用堆栈、括号匹配查抄、深度优先搜索算法（DFS）等。
队列 (Queue)：
结构特点：队列遵循先进先出（First-In-First-Out, FIFO）的原则，答应在队尾插入元素（enqueue或add），而在队头删除元素（dequeue或remove）。
操作特性：主要支持enqueue（入队）、dequeue（出队）、peek（检察队头元素但不移除）以及判定是否为空等操作。
应用场景：队列常见于多线程同步、使命调理、广度优先搜索算法（BFS）、消息通报体系等必要有序处理多个使命的场合。
6.2 双端队列
6.2.1 概念
双端队列 (Double-Ended Queue, deque)：
结构特点：可以在两头举行插入和删除的序列容器，同时具备队列和栈的部分特性。
操作特性：包罗push_front/pop_front（在/从队头操作）、push_back/pop_back（在/从队尾操作）等功能。
应用场景：滑动窗口算法、回文串检测、及时事件处理等。
6.2.2 链表实现
public class LinkedListDeque<E> implements Deque<E> {
public static void main(String[] args) {
LinkedListDeque<Integer>linkedListDeque=new LinkedListDeque<>(5);
boolean offerLast1 = linkedListDeque.offerLast(1);
boolean offerLast2 = linkedListDeque.offerLast(2);
boolean offerLast3 = linkedListDeque.offerLast(3);
boolean offerLast4 = linkedListDeque.offerLast(4);
boolean offerLast5 = linkedListDeque.offerLast(5);
boolean offerLast6 = linkedListDeque.offerLast(6);
Integer first1 = linkedListDeque.poolFirst();
Integer first2 = linkedListDeque.poolFirst();
Integer last1 = linkedListDeque.poolLast();
Integer last2 = linkedListDeque.poolLast();
Integer last3 = linkedListDeque.poolLast();
Integer last4 = linkedListDeque.poolLast();
}
private int capacity;
private int size;
Node<E> sentinel=new Node<E>(null,null,null);
public LinkedListDeque(int capacity) {
this.capacity = capacity;
sentinel.next=sentinel;
sentinel.prev=sentinel;
}
static class Node<E>{
Node prev;
E value;
Node next;
public Node(Node<E> prev, E value, Node<E> next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
@Override
public boolean offerFirst(E e) {
if(isFull()){
return false;
}
//上一个节点是哨兵，下一个节点是哨兵.next
Node oldFirst = sentinel.next;
//新的节点
Node<E> addNode=new Node<E>(sentinel,e,oldFirst);
//旧节点修改prev指针
oldFirst.prev=addNode;
//修改哨兵next指针
sentinel.next=addNode;
//增加容量
size++;
return true;
}
@Override
public boolean offerLast(E e) {
if(isFull()){
return false;
}
//旧的最后一个节点
Node oldLast = sentinel.prev;
//新的节点
Node addNode=new Node(oldLast,e,sentinel);
//旧节点修改next指针
oldLast.next=addNode;
//修改哨兵prev指针
sentinel.prev=addNode;
size++;
return true;
}
@Override
public E poolFirst() {
if(isEmpty()){
return null;
}
//需要出队列的节点
Node<E> poolNode=sentinel.next;
//移除节点的下一个节点
Node<E>nextNode=poolNode.next;
//修改下一个节点.prev指针
nextNode.prev=sentinel;
//修改哨兵.next指针
sentinel.next=nextNode;
size--;
return poolNode.value;
}
@Override
public E poolLast() {
if(isEmpty()){
return null;
}
//需要出队列的节点
Node<E> poolNode=sentinel.prev;
//移除节点的上一个节点
Node<E>prevNode=poolNode.prev;
//修改上一个节点.next指针
prevNode.next=sentinel;
//修改哨兵.prev指针
sentinel.prev=prevNode;
size--;
return poolNode.value;
}
@Override
public E peekFirst() {
if(isEmpty()){
return null;
}
return (E) sentinel.next.value;
}
@Override
public E peekLast() {
if(isEmpty()){
return null;
}
return (E) sentinel.prev.value;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public boolean isFull() {
return size==capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> piont=sentinel.next;
@Override
public boolean hasNext() {
return piont!=sentinel;
}
@Override
public E next() {
E val= piont.value;
piont=piont.next;
return val;
}
};
}
}
6.2.3 数组实现
public class ArrayDeque1<E> implements Deque<E>{
public static void main(String[] args) {
ArrayDeque1<Integer> arrayDeque1=new ArrayDeque1(3);
boolean full1 = arrayDeque1.isFull();
boolean empty1 = arrayDeque1.isEmpty();
boolean offerFirst1 = arrayDeque1.offerFirst(1);
boolean offerFirst2 = arrayDeque1.offerFirst(2);
boolean offerFirst3 = arrayDeque1.offerLast(3);
boolean offerFirst4 = arrayDeque1.offerLast(4);
boolean full2 = arrayDeque1.isFull();
boolean empty2 = arrayDeque1.isEmpty();
int poolFirst1= arrayDeque1.poolFirst();
int poolLast1= arrayDeque1.poolLast();
}
E[]array;
private int head;
private int tail;
/*
* tail不存值，实际长度应该用参数+1
* */
public ArrayDeque1(int capacity) {
array= (E[]) new Object ;
}
@Override
/*
* 先head-1再添加元素
* */
public boolean offerFirst(E e) {
if(isFull()){
return false;
}
head= dec(head, array.length);
array=e;
return true;
}
@Override
/*
* 添加元素后，tail+1
* */
public boolean offerLast(E e) {
if(isFull()){
return false;
}
array=e;
tail= inc(tail, array.length);
return true;
}
@Override
/*
* 先获取值，再head++（转换为合法索引）
* */
public E poolFirst() {
if(isEmpty()){
return null;
}
E e = array;
//取消引用，自动释放内存
array=null;
head=inc(head,array.length);
return e;
}
@Override
/*
* 先tail-- ，再获取元素（转换为合法索引）
* */
public E poolLast() {
if(isEmpty()){
return null;
}
tail=dec(tail,array.length);
E e = array;
//取消引用，自动释放内存
array=null;
return e;
}
@Override
public E peekFirst() {
if(isEmpty()){
return null;
}
return array;
}
/*
* 获取 tail-1位置的元素
* */
@Override
public E peekLast() {
return array;
}
@Override
/*
* 头尾指向同一个位置即为空
* */
public boolean isEmpty() {
return head==tail;
}
@Override
/*
* head ~ tail =数组.length-1
* tail>head tail-head ==数组.length-1
* tail<head head-tail==1
* */
public boolean isFull() {
if(head <tail){
return tail-head==array.length-1;
}else if(head >tail){
return head-tail==1;
}
return false;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int poin=head;
@Override
public boolean hasNext() {
return poin!=tail;
}
@Override
public E next() {
E e = array;
poin = inc(poin + 1, array.length);
return e;
}
};
}
/*
* 索引++之后越界恢复成0
* */
static int inc(int i, int length){
if(++i>=length){
return 0;
}
return i;
}
/*
* 索引--之后越界恢复成数组长度
* */
static int dec(int i, int length){
if(--i <0)return length-1;
return i;
}
} 注意：基本范例占用字节相同，不必要思量内存释放，但是引用数据范例要思量内存释放题目（当不删除元素时，该索引位置应该置位null，否则垃圾回收器不会自动回收）。
6.3 优先级队列
6.3.1 概念
优先级队列 (Priority Queue)：
结构特点：每个元素都有一个优先级，每次取出的是当前优先级最高的元素。可以基于堆实现。
操作特性：主要包罗insert（插入元素）、delete_min/max（移除并返回优先级最高/最低的元素）等。
应用场景：Dijkstra算法中的最短路径搜索、操作体系中的进程调理、事件驱动编程中的事件处理等。
6.3.2 无序数组实现
基于无序数组的优先级队列（例如使用索引堆）：
插入元素：
无序数组实现如索引堆等结构可以相对快速地插入元素，并通过索引维护堆属性，插入操作的时间复杂度一般为O(log n)。
删除最高优先级元素：
删除最小元素通常涉及到重新调整堆结构以满意堆属性，即包管父节点的优先级高于或等于子节点，时间复杂度同样是O(log n)。
上风：
插入和删除操作的时间复杂度都相对较低，都是O(log n)，适用于动态变革的数据集合。
相对于有序数组，插入和删除操作更加高效，特别是在大量元素插入、删除的环境下。
劣势：
查找最高优先级元素并不像有序数组那样简单，每次取出最小元素都必要调整堆结构。
//基于无序数组的实现
public class PriorityQueue<E extends Priority> implements Queue<E> {
public static void main(String[] args) {
Test test1 = new Test(1, "任务9");
Test test2 = new Test(2, "任务8");
Test test3 = new Test(3, "任务7");
Test test4 = new Test(4, "任务6");
PriorityQueue priorityQueue=new PriorityQueue(3);
boolean full1 = priorityQueue.isFull();
boolean empty1 = priorityQueue.isEmpty();
Priority peek1 = priorityQueue.peek();
boolean offer1 = priorityQueue.offer(test1);
boolean offer2 = priorityQueue.offer(test2);
boolean offer3 = priorityQueue.offer(test3);
boolean offer4 = priorityQueue.offer(test4);
boolean full2 = priorityQueue.isFull();
boolean empty2 = priorityQueue.isEmpty();
Priority peek2 = priorityQueue.peek();
Priority pool1 = priorityQueue.pool();
Priority pool2 = priorityQueue.pool();
Priority pool3 = priorityQueue.pool();
Priority pool4 = priorityQueue.pool();
}
static class Test extends Priority {
String task;
public Test(int priority, String task) {
super(priority);
this.task = task;
}
}
@Getter
static Priority[] array;
private static int size=0;
public PriorityQueue(int capacity) {
array = new Priority;
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
array = value;
size++;
return true;
}
@Override
public E pool() {
if(isEmpty()){
return null;
}
int maxIndex = getMaxIndex();
Priority priority = array;
remove(maxIndex);
return (E) priority;
}
//移除元素
private void remove(int maxIndex) {
if(maxIndex<size-1){
//不是最后一个元素
System.arraycopy(array,maxIndex+1,array,maxIndex,size-1-maxIndex);
}
size--;
}
private static int getMaxIndex(){
int max = 0;
for (int i = 0; i < array.length; i++) {
if (array.priority < array.priority) {
max = i;
}
}
return max;
}
@Override
public E peek() {
if(isEmpty()){
return null;
}
int max = 0;
for (int i = 0; i < size; i++) {
if (array.priority < array.priority) {
max = i;
}
}
Priority priority = array;
return (E) priority;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int p;
@Override
public boolean hasNext() {
return p < array.length;
}
@Override
public E next() {
Priority priority = array;
p++;
return (E) priority;
}
};
}
}
6.3.3 有序数组实现
基于有序数组的优先级队列：
插入元素：
插入新元素必要保持数组的有序性，因此在插入过程中可能必要移动部分或全部已存在的元素以腾出位置给新元素，时间复杂度通常是O(n)。
由于数组本身是有序的，可以通过二分查找快速定位到插入点，但是插入后的调整仍然涉及元素移动。
删除最高优先级元素：
可以直接访问并删除数组的第一个元素（假设是最小元素），时间复杂度为O(1)。
删除后假如必要维持有序，可能必要将末了一个元素移动到被删除元素的位置，大概使用某种方法来“弥补”空缺，总体上删除操作的时间复杂度也是O(n)。
上风：
查找最高优先级元素的时间复杂度低，为O(1)。
假如插入不黑白常频繁且数组巨细相对稳定，那么其效率可能会较高，由于查询和删除最小元素高效。
劣势：
插入和删除元素的资本高，尤其是当数组较大时，频繁的移动操作会显著降低性能。
//基于有序数组的实现
public class PriorityQueue3<E extends Priority> implements Queue<E> {
public static void main(String[] args) {
Test test1 = new Test(1, "任务9");
Test test2 = new Test(2, "任务8");
Test test3 = new Test(3, "任务7");
Test test4 = new Test(4, "任务6");
PriorityQueue3 priorityQueue=new PriorityQueue3(3);
boolean full1 = priorityQueue.isFull();
boolean empty1 = priorityQueue.isEmpty();
Priority peek1 = priorityQueue.peek();
boolean offer2 = priorityQueue.offer(test2);
boolean offer1 = priorityQueue.offer(test1);
boolean offer3 = priorityQueue.offer(test3);
boolean offer4 = priorityQueue.offer(test4);
boolean full2 = priorityQueue.isFull();
boolean empty2 = priorityQueue.isEmpty();
Priority peek2 = priorityQueue.peek();
Priority pool1 = priorityQueue.pool();
Priority pool2 = priorityQueue.pool();
Priority pool3 = priorityQueue.pool();
Priority pool4 = priorityQueue.pool();
}
static class Test extends Priority {
String task;
public Test(int priority, String task) {
super(priority);
this.task = task;
}
}
@Getter
static Priority[] array;
private static int size;
public PriorityQueue3(int capacity) {
array = new Priority;
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
insert( value);
size++;
return true;
}
private void insert(E value) {
int i=size-1;
while (i>=0 && array.priority> value.priority){
//优先级大于入参向上移动
array=array;
i--;
}
//在比他小的索引后面插入元素
array=value;
}
@Override
public E pool() {
if(isEmpty()){
return null;
}
E priority = (E) array;
array[--size]=null;
return (priority) ;
}
@Override
public E peek() {
if(isEmpty()){
return null;
}
return (E) array;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int p;
@Override
public boolean hasNext() {
return p < array.length;
}
@Override
public E next() {
Priority priority = array;
p++;
return (E) priority;
}
};
}
}
6.3.4 基于堆实现
6.3.4.1 堆的概念
计算机科学中，堆是一种基于树的数据结构，通常用完全二叉树来实现。堆的特性如下：
完全二叉树属性：
堆是一个完全二叉树，这意味着除了末了一层之外，其他每一层都被完全填满，而且所有节点都尽可能地集中在左侧。
堆序性质：
在大顶堆（也称为最大堆）中，对于任意节点 C 与其父节点 P，满意不等式 P.value >= C.value，即每个父节点的值都大于或等于其子节点的值。
在小顶堆（也称为最小堆）中，对于任意节点 C 与其父节点 P，满意不等式 P.value <= C.value，即每个父节点的值都小于或等于其子节点的值。
操作特性：
插入操作：在保持堆序性质的条件下插入新元素，可能必要调整堆中的元素位置。
删除操作：删除堆顶元素（即最大或最小元素），也必要重新调整堆结构以包管剩余元素仍然满意堆序性质。
查找最大/最小元素：堆顶元素就是整个堆中的最大（在大顶堆中）或最小（在小顶堆中）元素，无需遍历整个堆即可直接获取。
存储方式：
堆可以用数组来高效存储，由于是完全二叉树，可以使用数组下标与节点层级、左右子节点之间的关系精密关联的特点，节流存储空间并加快访问速率。
应用：
堆常用于实现优先队列，能够快速找到并移除具有最高或最低优先级的元素。
在许多算法和数据处理中，如求解最值题目、堆排序算法以及图的最小天生树算法（例如Prim算法或Kruskal算法联合使用优先队列）中都有紧张应用。
6.3.4.2 堆的分类
堆在计算机科学中主要根据其内部元素的排序特性举行分类，可以分为以下两种范例：
大顶堆（Max Heap）： 在大顶堆中，父节点的值总是大于或等于其所有子节点的值。堆的根节点是整个堆中的最大元素，因此，大顶堆常被用于实现优先队列，其中队列头部始终是当前最大的元素。
小顶堆（Min Heap）： 在小顶堆中，父节点的值总是小于或等于其所有子节点的值。与大顶堆相反，小顶堆的根节点是整个堆中的最小元素，同样适用于实现优先队列，只不过在这种环境下，队列头部提供的是当前最小的元素。
这两种范例的堆都是完全二叉树结构，而且通常通过数组来实现存储，使用数组索引与树节点之间的逻辑关系快速访问和操作堆中的元素。除了大顶堆和小顶堆之外，另有其他形式的堆，例如斐波那契堆（Fibonacci Heap），它是一种更为复杂的高效数据结构，提供了更优化的插入、删除和归并操作，但并不像普通二叉堆那样要求严格的父节点与子节点的巨细关系。
6.3.4.3 堆的计算
在树型数据结构中，从索引0开始存储节点数据是常见的做法，尤其是在数组或链表实现的树结构里。这里我们区分两种环境：
已知子节点求父节点：
假如树结构使用数组来表示，而且我们知道子节点对应的数组索引，那么根据某种固定规则（如：每个节点的左孩子通常位于2倍索引处，右孩子位于2倍索引 + 1处），可以计算出父节点的索引。
在完全二叉树中，给定一个节点i的索引，其父节点的索引可以通过 (i - 1) / 2 计算得出（向下取整）。
已知父节点求子节点：
同样地，假如知道父节点在数组中的索引，我们可以很容易地找到它的两个子节点。
左子节点的索引通常是 2 * 父节点索引 + 1。
右子节点的索引通常是 2 * 父节点索引 + 2。
假如从索引1开始存储节点：
已知子节点求父节点为： (i ) / 2。
已知父节点求子节点为：2i，2i+1。
请注意，这些规则适用于采用数组实现的完全二叉树和几乎完全二叉树等特定场景下的节点关系查找。对于其他范例的树大概非完全二叉树，可能必要额外的数据结构或差异的逻辑来维护父子节点之间的关系。例如，在链表形式的树结构中，父节点会直接持有指向其子节点的指针，因此不必要通过计算索引来定位子节点。
6.3.4.4 基于大顶堆实现
//基于有序数组的实现
public class PriorityQueue4<E extends Priority> implements Queue<E> {
public static void main(String[] args) {
Test test1 = new Test(1, "任务9");
Test test2 = new Test(2, "任务8");
Test test3 = new Test(3, "任务7");
Test test4 = new Test(4, "任务6");
PriorityQueue4 priorityQueue = new PriorityQueue4(3);
boolean full1 = priorityQueue.isFull();
boolean empty1 = priorityQueue.isEmpty();
Priority peek1 = priorityQueue.peek();
boolean offer2 = priorityQueue.offer(test2);
boolean offer1 = priorityQueue.offer(test1);
boolean offer3 = priorityQueue.offer(test3);
boolean offer4 = priorityQueue.offer(test4);
boolean full2 = priorityQueue.isFull();
boolean empty2 = priorityQueue.isEmpty();
Priority peek2 = priorityQueue.peek();
Priority pool1 = priorityQueue.pool();
Priority pool2 = priorityQueue.pool();
Priority pool3 = priorityQueue.pool();
Priority pool4 = priorityQueue.pool();
}
static class Test extends Priority {
String task;
public Test(int priority, String task) {
super(priority);
this.task = task;
}
}
@Getter
static Priority[] array;
private static int size;
public PriorityQueue4(int capacity) {
array = new Priority;
}
/*
* 1.入队新元素，加入到数组末尾（索引child）
* 2.不断比较新元素与父节点的优先级。
* 如果优先级低于新节点，则向下移动，并寻找下一个paraent
* 直至父元素优先级跟高或者child==0为止
* */
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
if(isEmpty()){
array=value;
}
int child = size++;
int parent = (child - 1) / 2;
//新元素和父元素优先级对比
while (value.priority > array.priority && child != 0) {
array = array;
//子节点指向父节点，父节点指向，原本的父节点的父节点
child = parent;
parent = (child - 1) / 2;
}
array = value;
return true;
}
/*
* 1.由于移除最后一个元素效率比较高，
* 故应将第一个优先级最高的元素与最后一个元素互换。
* 2.将堆顶元素与两个子元素比较，与较大的那个更换，
* 直至该节点为最后一个节点或者子节点都小于该节点
*
* */
@Override
public E pool() {
if (isEmpty()) return null;
swap(0, size - 1);
size--;
//保存优先级最大的元素
Priority p = array;
//置空垃圾回收
array = null;
//堆顶下潜
down(0);
return (E) p;
}
private void swap(int i, int j) {
Priority t = array;
array = array;
array = t;
}
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int bigChild = parent;
//比较左侧元素与父元素
if (left < size && array.priority > array.priority) bigChild = left;
//比较右侧元素与父元素
if (right < size && array.priority > array.priority) bigChild = right;
//交换较大的元素
if (bigChild != parent) {
swap(bigChild, parent);
//以最大的子元素节点索引为参数继续执行下潜操作
down(bigChild);
}
}
@Override
public E peek() {
if(isEmpty())return null;
return (E) array;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int p;
@Override
public boolean hasNext() {
return p < array.length;
}
@Override
public E next() {
Priority priority = array;
p++;
return (E) priority;
}
};
}
}
6.4 壅闭队列
/*
* 为了避免多线程导致的数据混乱，例如：线程T1 修改之后未执行tail++,T2执行赋值，
* 会把T1赋值给覆盖掉，然后执行两次tail++，最后导致数据混乱。
* 1.synchronized 关键字,简单功能少
* 2.ReentrantLock 可重入锁，功能多
* */
public class TestThreadUnsafe {
public static void main(String[] args) {
TestThreadUnsafe queue = new TestThreadUnsafe();
/*queue.offer("E1");
queue.offer("E2");*/
new Thread(() -> {
try {
queue.offer("E1");
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}, "t1").start();
new Thread(() -> {
try {
queue.offer("E2");
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}, "t2").start();
}
private final String[] array = new String;
private int tail = 0;
private int size = 0;
ReentrantLock reentrantLock = new ReentrantLock();
Condition tailWaits=reentrantLock.newCondition();//条件对象集合
public void offer(String s) throws InterruptedException {
//加锁 等待直到解锁
// reentrantLock.lock();
// 加锁，阻塞过程中随时打断抛出异常
reentrantLock.lockInterruptibly();
try {
/*
* 如果使用if 多线程情况下，会导致新加入的线程未走判断，等待的线程被唤醒，两个线程同时向下执行
* 这种唤醒叫做虚假唤醒，每次都应该循环判断是否满了，而不应该用if
* */
while (isFull()){
//等待 让线程进入阻塞状态
tailWaits.await();
// 阻塞后唤醒线程使用，且必须配合锁使用
/*reentrantLock.lockInterruptibly();
tailWaits.signal();
reentrantLock.unlock();*/
}
array = s;
if(++tail== array.length){
tail=0;
}
size++;
} finally {
//解锁必须执行
reentrantLock.unlock();
}
}
public boolean isFull(){
return size==array.length;
}
public String toString() {
return Arrays.toString(array);
}
}
6.4.1 单锁实现
/*
* 用锁保证线程安全。
* 条件变量让pool或者offer线程进入等待，而不是循环尝试，占用cpu
* */
publicclass BlockingQueue1<E> implements BlockingQueue<E> {
public static void main(String[] args) {
BlockingQueue1<String> blockingQueue1=new BlockingQueue1<>(3);
try {
blockingQueue1.offer("任务1");
blockingQueue1.offer("任务2");
blockingQueue1.offer("任务3");
boolean offer = blockingQueue1.offer("任务4", 2000);
System.out.println(offer);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
private final E[] array;
private int head;
private int tail;
private int size;
private ReentrantLock lock = new ReentrantLock();
private Condition headWaits = lock.newCondition();
private Condition tailWaits = lock.newCondition();
public BlockingQueue1(int capacity) {
this.array = (E[]) new Object;
}
@Override
public void offer(E e) throws InterruptedException {
lock.lockInterruptibly();
try {
//防止虚假唤醒
while (isFull()) {
tailWaits.await();
}
array = e;
if (++tail == array.length) {
tail = 0;
}
size++;
//唤醒等待非空的线程
headWaits.signal();
} finally {
lock.unlock();
}
}
/*
* 优化后的offer，设置等待时间，超出则抛出异常
* */
@Override
public boolean offer(E e, long timeout) throws InterruptedException {
lock.lockInterruptibly();
try {
//等待timeout纳秒抛出异常
long ns = TimeUnit.MICROSECONDS.toNanos(timeout);
while (isFull()) {
if (ns <= 0) {
return false;
}
ns = tailWaits.awaitNanos(ns);
}
array = e;
if (++tail == array.length) {
tail = 0;
}
size++;
//唤醒等待非空的线程
headWaits.signal();
return true;
} finally {
lock.unlock();
}
}
@Override
public E pool() throws InterruptedException {
lock.lockInterruptibly();
try {
while (isFull()) {
headWaits.await();
}
E e = array;
array = null;
if (++head == array.length) {
head = 0;
}
size--;
//唤醒等待不满的线程
tailWaits.signal();
return e;
} finally {
lock.unlock();
}
}
public boolean isFull() {
return size == array.length;
}
public boolean isEmpty() {
return size == 0;
}
}
6.4.2 双锁实现
6.4.2.1 双锁实现1
由于tailWaits.signal();必须配合taillock.unlock(); taillock.unlock();使用，headloca也一样，这种方式极易出现死锁题目。
使用jps下令可以获取进程id，jstack+进程id 可以检测死锁等题目。
可以将两个锁列为平级，而不是嵌套即可办理。
/*
* 单锁实现方式，offer和pool是互相影响的，
* 但是head指针和tail执行两者并不互相影响，
* 会降低运行效率，offer和pool不应该互相影响
* */
public class BlockingQueue2<E> implements BlockingQueue<E> {
public static void main(String[] args) {
BlockingQueue2<String> blockingQueue2 = new BlockingQueue2<>(3);
try {
blockingQueue2.offer("任务1");
blockingQueue2.offer("任务2");
blockingQueue2.offer("任务3");
boolean offer = blockingQueue2.offer("任务4", 2000);
System.out.println(offer);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
private final E[] array;
private int head;
private int tail;
/*
* 由于 pool和offer会同时操作size变量，
* 所以size应该被声明为原子变量
* */
private AtomicInteger size=new AtomicInteger();
private ReentrantLock taillock = new ReentrantLock();
private ReentrantLock headlock = new ReentrantLock();
/*
* headlock和headWaits必须配合使用否则会报错
* */
private Condition tailWaits = taillock.newCondition();
private Condition headWaits = headlock.newCondition();
public BlockingQueue2(int capacity) {
this.array = (E[]) new Object;
}
@Override
public void offer(E e) throws InterruptedException {
taillock.lockInterruptibly();
try {
//防止虚假唤醒
while (isFull()) {
tailWaits.await();
}
array = e;
if (++tail == array.length) {
tail = 0;
}
size.addAndGet(1);
//唤醒等待非空的线程
headWaits.signal();
} finally {
taillock.unlock();
}
}
/*
* 优化后的offer，设置等待时间，超出则抛出异常
* */
@Override
public boolean offer(E e, long timeout) throws InterruptedException {
taillock.lockInterruptibly();
try {
//等待timeout纳秒抛出异常
long ns = TimeUnit.MICROSECONDS.toNanos(timeout);
while (isFull()) {
if (ns <= 0) {
return false;
}
ns = tailWaits.awaitNanos(ns);
}
array = e;
if (++tail == array.length) {
tail = 0;
}
size.getAndIncrement();
//唤醒等待非空的线程,必须配合headlocal使用
headlock.lock();
headWaits.signal();
headlock.unlock();
return true;
} finally {
taillock.unlock();
}
}
@Override
public E pool() throws InterruptedException {
headlock.lockInterruptibly();
try {
while (isFull()) {
headWaits.await();
}
E e = array;
array = null;
if (++head == array.length) {
head = 0;
}
size.getAndDecrement();
//唤醒等待不满的线程，tailWaits闭合和tailLock配合使用
taillock.unlock();
tailWaits.signal();
taillock.unlock();
return e;
} finally {
headlock.unlock();
}
}
public boolean isFull() {
return size.get() == array.length;
}
public boolean isEmpty() {
return size.get() == 0;
}
}
6.4.2.2 双锁实现2
为了提升效率应该只管减少taillock和headlock之间的互相影响，对应的就可以提升效率，tail的叫醒操作只由第一个线程实行，而后续的叫醒可以交给第一个线程来实行，headlock也是一样的。这也叫做级联操作。
/*
* 单锁实现方式，offer和pool是互相影响的，
* 但是head指针和tail执行两者并不互相影响，
* 会降低运行效率，offer和pool不应该互相影响
* */
public class BlockingQueue2<E> implements BlockingQueue<E> {
public static void main(String[] args) {
BlockingQueue2<String> blockingQueue2 = new BlockingQueue2<>(3);
try {
blockingQueue2.offer("任务1");
blockingQueue2.offer("任务2");
blockingQueue2.offer("任务3");
boolean offer = blockingQueue2.offer("任务4", 2000);
System.out.println(offer);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
private final E[] array;
private int head;
private int tail;
/*
* 由于 pool和offer会同时操作size变量，
* 所以size应该被声明为原子变量
* */
private AtomicInteger size = new AtomicInteger();
private ReentrantLock taillock = new ReentrantLock();
private ReentrantLock headlock = new ReentrantLock();
/*
* headlock和headWaits必须配合使用否则会报错
* */
private Condition tailWaits = taillock.newCondition();
private Condition headWaits = headlock.newCondition();
public BlockingQueue2(int capacity) {
this.array = (E[]) new Object;
}
@Override
public void offer(E e) throws InterruptedException {
taillock.lockInterruptibly();
try {
//防止虚假唤醒
while (isFull()) {
tailWaits.await();
}
array = e;
if (++tail == array.length) {
tail = 0;
}
size.addAndGet(1);
//唤醒等待非空的线程，
headWaits.signal();
} finally {
taillock.unlock();
}
}
/*
* 优化后的offer，设置等待时间，超出则抛出异常
* */
@Override
public boolean offer(E e, long timeout) throws InterruptedException {
//新增元素钱的个数，为0既说明是第一个线程
int c;
taillock.lockInterruptibly();
try {
//等待timeout纳秒抛出异常
long ns = TimeUnit.MICROSECONDS.toNanos(timeout);
while (isFull()) {
if (ns <= 0) {
return false;
}
ns = tailWaits.awaitNanos(ns);
}
array = e;
if (++tail == array.length) {
tail = 0;
}
c = size.getAndIncrement();
// 如果c+1<arr.length说明还没有满，那么级联唤醒
if(c+1< array.length){
tailWaits.signal();
}
} finally {
taillock.unlock();
}
try {
//唤醒等待非空的线程,必须配合headlocal使用
headlock.lock();
if (c == 0) {
//第一个线程
headWaits.signal();
}
headlock.unlock();
} catch (Exception exception) {
throw exception;
}
return true;
}
@Override
public E pool() throws InterruptedException {
E e;
//取走钱的元素个数
int c;
headlock.lockInterruptibly();
try {
while (isFull()) {
headWaits.await();
}
e = array;
array = null;
if (++head == array.length) {
head = 0;
}
c = size.getAndDecrement();
if (c > 1) {
// 说明还有其他元素,唤醒下一个
headWaits.signal();
}
} finally {
headlock.unlock();
}
//唤醒等待不满的线程，tailWaits闭合和tailLock配合使用
try {
taillock.unlock();
//唤醒减少之前队列是满的那个线程
if (c == array.length) {
tailWaits.signal();
}
taillock.unlock();
} catch (Exception exception) {
throw exception;
}
return e;
}
public boolean isFull() {
return size.get() == array.length;
}
public boolean isEmpty() {
return size.get() == 0;
}
}
7.（数据结构）堆
7.1 相关概念
堆（Heap）在计算机科学中是一种特别的数据结构，它通常被实现为一个可以看作完全二叉树的数组对象。以下是一些关于堆的基本概念：
数据结构：
堆是一个优先队列的抽象数据范例实现，通过完全二叉树的逻辑结构来组织元素。
完全二叉树意味着除了末了一层外，每一层都被完全填满，而且末了一层的所有节点都尽可能地集中在左边。
物理存储：
堆用一维数组顺序存储，从索引0开始，每个节点的父节点和子节点之间的关系可以通过简单的算术运算确定。
堆的特性：
堆序性质：对于任意节点i，其值（或关键字）满意与它的子节点的关系——在最大堆（大根堆）中，节点i的值大于或等于其两个子节点的值；在最小堆（小根堆）中，节点i的值小于或等于其两个子节点的值。
结构性：堆始终保持完全二叉树的状态，这意味着即使有节点删除或插入，堆也要颠末调整以保持堆序性质。
操作：
插入：新元素添加到堆中时，必要自下而上调整堆，以确保新的元素不会破坏堆的性质。
删除：通常从堆顶（根节点）删除元素（即最大堆中的最大元素或最小堆中的最小元素），然后将堆尾元素移动到堆顶，再自上而下调整堆。
查找：堆常用于快速找到最大或最小元素，但查找特定值的时间复杂度通常不优于线性时间，由于堆本身不具备随机访问的能力。
应用：
堆常用于办理各种题目，如优先级队列、事件调理、图算法中的最短路径计算（Dijkstra算法）、求解Top K题目等。
分类：
最常见的堆是二叉堆，包罗大根堆和小根堆。
另有其他范例的堆，好比斐波那契堆，提供更高效的归并操作以及其他优化特性。
建堆算法：
1. Dijkstra算法：是一个使用优先队列（可以基于堆实现）的经典例子。在Dijkstra算法中，每次都会从未确定最短路径且当前间隔已知最小的顶点开始，更新与其相邻顶点的间隔。为了高效地找到下一个待处理的顶点（即当前已知最短路径的顶点），会用到一个能够根据顶点间隔值举行快速插入和删除的优先队列，堆就是实现这种功能的理想数据结构之一。
2. 堆下沉”（Heap Sink），“堆下滤”（Heap Percolate Down）：从根节点（非叶子节点中最高层的一个）开始。 查抄该节点与其两个子节点的关系：在最大堆中，假如当前节点的值小于其任意一个子节点的值；在最小堆中，假如当前节点的值大于其任意一个子节点的值。 假如违反了堆的性质，则交换当前节点与其较大（对于最大堆）或较小（对于最小堆）子节点的值，并将当前节点移动到新位置（即原来子节点的位置）。 重复上述步调，但这次以交换后的子节点作为新的当前节点，继续下潜至当前节点没有子节点（即成为叶子节点），大概当前节点及其子节点均满意堆的性质为止。
时间复杂度：
https://i-blog.csdnimg.cn/blog_migrate/059fe7165619b5286bcc5b0c5b2a2913.png
7.2 大顶堆
堆内比较紧张的方法就是，建堆，堆下潜操作，堆上浮操作
/*
* 大顶堆
* */
public class MaxHeap {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7};
MaxHeap maxHeap = new MaxHeap(array);
System.out.println(Arrays.toString(MaxHeap.array));
}
static int[] array;
static int size;
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
/*
* 建堆：
* 找到第一个非叶子结点
* 执行下潜，直到没有子节点
* */
private void heapify() {
//最后一个非叶子结点 size/2-1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
//执行下潜 parent 为需要下潜的索引，下潜到没有孩子，或者孩子都小于当前节点
private void down(int parent) {
//左child索引
int leftChild = parent * 2 + 1;
//右child索引
int rightChild = leftChild + 1;
int max = parent;
if (leftChild < size && array < array) max = leftChild;
if (rightChild < size && array < array) max = rightChild;
if (max != parent) {
//下潜并再次调用
swap(parent, max);
down(max);
}
}
/*
* 上浮操作
* */
public void up(int offered){
int child =size;
//子元素索引等于0则到达了堆顶
while (child>0){
int parent=(child-1)/2;
if (offered>array){
array=array;
}else {
break;
}
child=parent;
}
array = offered;
}
//交换两个元素
private void swap(int i, int j) {
isEmptyeException();
int temp = array;
array = array;
array = temp;
}
public int peek(){
isEmptyeException();
return array;
}
/*
* 从第一个位置移除元素，交换头尾，在移除最后一个
* */
public int poll(){
isEmptyeException();
int temp=array;
//交换首位
swap(0,size-1);
size--;
down(0);
return temp;
}
/*
* 从指定位置移除元素，交换指定位置和尾，在移除最后一个
* */
public int poll(int index){
isEmptyeException();
int temp=array;
//交换首位
swap(index,size-1);
size--;
down(index);
return temp;
}
/*
* 替换堆顶部元素
* 1.替换堆顶元素
* 2.执行下潜，直到符合堆的特性
* */
public void replace(int replaced){
isEmptyeException();
array=replaced;
down(0);
}
/*
* 堆尾部添加元素
* */
public boolean offered(int offered){
if(isFull()){
return false;
}
up(offered);
size++;
return true;
}
/*
* 堆满异常
* */
public void isFulleException(){
if (isFull()){
throw new RuntimeException("堆已满");
}
}
/*
* 堆空异常
* */
public void isEmptyeException(){
if (isEmpty()){
throw new RuntimeException("堆为空");
}
}
/*
* 判满
* */
public boolean isFull(){
return size== array.length;
}
/*
* 判空
* */
public boolean isEmpty(){
return size== 0;
}
}
7.3 堆排序
堆排序是一种基于比较的排序算法，它使用了完全二叉树（即堆）这种数据结构。堆通常可以分为两种：最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其所有子节点的值；在最小堆中，父节点的值总是小于或等于其所有子节点的值。
堆排序的基本步调如下：
构造初始堆：首先将待排序的序列构造成一个大顶堆（升序排序）或小顶堆（降序排序）。从末了一个非叶子节点开始，自底向上、自右向左举行调整。
堆调整：将堆顶元素（即当前未排序序列的最大元素大概最小元素）与末尾元素举行交换，然后移除末尾元素（由于它已经是最小或最大的），如许就完成了第一个元素的排序。此时，剩余未排序部分不再满意堆的性质，因此必要对剩余元素重新调整为堆。
重复步调2：对剩余的n-1个元素重新构造堆，再将堆顶元素与末尾元素交换并移除末尾元素，直到整个序列都有序。
通过不绝调整堆和交换堆顶元素，终极实现整个序列的排序。
堆排序的时间复杂度为O(nlogn)，其中n为待排序元素的数目，空间复杂度为O(1)（原地排序）。由于其在最坏环境下的时间复杂度依然为O(nlogn)，且不必要额外的存储空间，因此堆排序在处理大数据量时具有较好的性能体现。
public class HeapSort {
public static void main(String[] args) {
int[] array = {2, 3, 1, 7, 6, 4, 5};
HeapSort heapSort = new HeapSort(array);
System.out.println(Arrays.toString(heapSort.array));
while (heapSort.size > 1) {
heapSort.swap(0, heapSort.size-1);
heapSort.size--;
heapSort.down(0);
}
System.out.println(Arrays.toString(heapSort.array));
}
int[] array;
int size;
public HeapSort(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
/*
* 建堆：
* 找到第一个非叶子结点
* 执行下潜，直到没有子节点
* */
private void heapify() {
//最后一个非叶子结点 size/2-1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
//执行下潜 parent 为需要下潜的索引，下潜到没有孩子，或者孩子都小于当前节点
private void down(int parent) {
//左child索引
int leftChild = parent * 2 + 1;
//右child索引
int rightChild = leftChild + 1;
int max = parent;
if (leftChild < size && array < array) max = leftChild;
if (rightChild < size && array < array) max = rightChild;
if (max != parent) {
//下潜并再次调用
swap(parent, max);
down(max);
}
}
/*
* 上浮操作
* */
public void up(int offered) {
int child = size;
//子元素索引等于0则到达了堆顶
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array) {
array = array;
} else {
break;
}
child = parent;
}
array = offered;
}
//交换两个元素
private void swap(int i, int j) {
int temp = array;
array = array;
array = temp;
}
} 8.二叉树
8.1概述
二叉树是一种基本的非线性数据结构，它是由n（n>=0）个节点构成的有限集合。在二叉树中，每个节点最多有两个子节点，通常被称作左孩子（left child）和右孩子（right child）。别的，二叉树还具有以下特点： 每个节点包含一个值（也可以包含其他信息）。 有一个被称为根（root）的特别节点，它是二叉树的起点，没有父节点。 假如一个节点存在左子节点，则该节点称为左子节点的父节点；同样，假如存在右子节点，则称为右子节点的父节点。 每个节点的所有子孙（包罗子节点、孙子节点等）构成了该节点的子树（subtree）。 左子树和右子树本身也是二叉树，且可以为空。
8.2 二叉树遍历
遍历：
广度优先遍历（Breadth-First Search, BFS）和深度优先遍历（Depth-First Search, DFS）是两种在图或树这类非线性数据结构中搜索节点的常用策略。
广度优先遍历（BFS）： 从根节点开始，首先访问所有与根节点直接相连的节点（即第一层邻人节点），然后按顺序访问它们的子节点（第二层），接着是孙子节点（第三层），以此类推。 使用队列作为辅助数据结构，将起始节点入队，每次从队列头部取出一个节点举行访问，并将其未被访问过的相邻节点全部加入队列尾部，直到队列为空为止。 在二叉树场景下，BFS通常实现为层序遍历，它会按照从上到下、从左到右的顺序依次访问各个节点。
深度优先遍历（DFS）： 从根节点开始，尽可能深地探索图或树的分支，直到到达叶子节点大概无法继续深入时返回上一层节点，再实验探索其他分支。 深度优先遍历有多种方式：前序遍历（先访问根节点，再遍历左子树，末了遍历右子树）、中序遍历（先遍历左子树，再访问根节点，末了遍历右子树）、后序遍历（先遍历左子树，再遍历右子树，末了访问根节点）以及反向的前后序遍历等。 在二叉树的DFS中，通常使用递归的方式实现。别的，也可以借助栈这一数据结构，模仿递归过程举行非递归实现。 总结来说，BFS包管了同一层次的节点会被一起访问到，而DFS则是沿着一条路径尽可能深地探索，直至无法继续进步时回溯至另一条路径。这两种遍历方式在办理差异的题目时各有上风，如寻找最短路径、拓扑排序等场景经常会用到BFS，而办理迷宫求解、判定连通性等题目时DFS则更为常见。
8.3 深度优先遍历
深度优先遍历（DFS）分为：
前序遍历（Preorder Traversal）： 在前序遍历中，访问顺序为：根节点 -> 左子树 -> 右子树。 递归地对当前节点的左子树举行前序遍历。 递归地对当前节点的右子树举行前序遍历。
中序遍历（Inorder Traversal）： 在中序遍历中，访问顺序为：左子树 -> 根节点 -> 右子树。 递归地对当前节点的左子树举行中序遍历。 访问当前节点。 递归地对当前节点的右子树举行中序遍历。
后序遍历（Postorder Traversal）： 在后序遍历中，访问顺序为：左子树 -> 右子树 -> 根节点。 递归地对当前节点的左子树举行后序遍历。 递归地对当前节点的右子树举行后序遍历。 访问当前节点。
8.3.1 递归实现遍历
public class TreeTraversal {
public static void main(String[] args) {
TreeNode tree = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6)));
preOrder(tree);
System.out.println();
inOrder(tree);
System.out.println();
postOrder(tree);
System.out.println();
}
/*
* 前序遍历 根节点=》左子树=》右子树
* */
//递归实现
static void preOrder(TreeNode treeNode){
if(treeNode==null){
return;
}
System.out.print(treeNode.val+"\t");//根节点
preOrder(treeNode.left);//左子树
preOrder(treeNode.right);//右子树
}
/*
* 中序遍历 左子树=》=》根节点=》右子树
* */
static void inOrder(TreeNode treeNode){
if(treeNode==null){
return;
}
inOrder(treeNode.left);//左子树
System.out.print(treeNode.val+"\t");//根节点
inOrder(treeNode.right);//右子树
}
/*
* 后序遍历 左子树=》右子树 =》根节点
* */
static void postOrder(TreeNode treeNode){
if(treeNode==null){
return;
}
postOrder(treeNode.left);//左子树
postOrder(treeNode.right);//右子树
System.out.print(treeNode.val+"\t");//根节点
}
}
8.3.2 非递归实现遍历
//非递归实现
public class TreeTraversal2 {
public static void main(String[] args) {
TreeNode tree = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6)));
preOrder(tree);
System.out.println();
inOrder(tree);
System.out.println();
postOrder(tree);
System.out.println();
}
/*
* 前序遍历 根节点=》左子树=》右子树
* */
static void preOrder(TreeNode treeNode){
LinkedList<TreeNode> stack = new LinkedList<>();
//定义一个指针,当前节点
TreeNode curr = treeNode;
//去的路径为前序遍历，回的路径为中序遍历
while (curr != null||!stack.isEmpty()) {
if (curr != null) {
stack.push(curr);//压入栈，为了记住返回的路径
System.out.print("前序" + curr.val + "\t");
curr = curr.left;
}else {
TreeNode peek = stack.peek();
TreeNode pop=stack.pop();
curr= pop.right;
}
}
}
/*
* 中序遍历 左子树=》=》根节点=》右子树
* */
static void inOrder(TreeNode treeNode){
LinkedList<TreeNode> stack = new LinkedList<>();
//定义一个指针,当前节点
TreeNode curr = treeNode;
//去的路径为前序遍历，回的路径为中序遍历
while (curr != null||!stack.isEmpty()) {
if (curr != null) {
stack.push(curr);//压入栈，为了记住返回的路径
curr = curr.left;
}else {
TreeNode peek = stack.peek();
TreeNode pop=stack.pop();
System.out.print("中序" + pop.val + "\t");
curr= pop.right;
}
}
}
/*
* 后序遍历 左子树=》右子树 =》根节点
* */
static void postOrder(TreeNode treeNode){
LinkedList<TreeNode> stack = new LinkedList<>();
//定义一个指针,当前节点
TreeNode curr = treeNode;
//去的路径为前序遍历，回的路径为中序遍历
TreeNode pop = null;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);//压入栈，为了记住返回的路径
curr = curr.left;
} else {
TreeNode peek = stack.peek();
//右子树为null，或者最近一次弹栈的元素与当前元素的右子树相等 说明全部子树都处理完了
if (peek.right == null||peek.right==pop) {
//最近一次弹栈的元素
pop= stack.pop();
System.out.print("后序" + pop.val + "\t");
} else {
curr = peek.right;
}
}
}
}
}
8.3.2 非递归实现遍历2
//非递归实现
public class TreeTraversal3 {
public static void main(String[] args) {
TreeNode tree = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6)));
postOrder(tree);
System.out.println();
}
static void postOrder(TreeNode treeNode){
LinkedList<TreeNode> stack = new LinkedList<>();
//定义一个指针,当前节点
TreeNode curr = treeNode;
//去的路径为前序遍历，回的路径为中序遍历
TreeNode pop = null;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
//压入栈，为了记住返回的路径
stack.push(curr);
//待处理左子树
System.out.println("前序"+curr.val);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
//右子树为null，无需处理
if (peek.right == null) {
//最近一次弹栈的元素
System.out.println("中序"+peek.val);
pop= stack.pop();
System.out.println("后序"+pop.val);
}else if(peek.right==pop) {//最近一次弹栈的元素与当前元素的右子树相等 说明右子树都处理完了
pop= stack.pop();
System.out.println("后序"+pop.val);
}else {
//待处理右子树
System.out.println("中序"+peek.val);
curr = peek.right;
}
}
}
}
} 9.二叉搜索树
9.1 概述
二叉搜索树（Binary Search Tree，BST）是一种特别的二叉树数据结构，其计划目标是为了支持高效的查找、插入和删除操作。在二叉搜索树中，每个节点都具有以下性质：
节点值的排序性：
节点的左子树（假如存在）包含的所有节点的值都小于该节点的值。
节点的右子树（假如存在）包含的所有节点的值都大于该节点的值。
递归定义：
一个空树是二叉搜索树。
假如一个非空树的根节点满意上述排序性，而且它的左子树和右子树分别都是二叉搜索树，则这个树整体上也是一个二叉搜索树。
操作特性：
查找：通过比较待查找值与当前节点值来决定是向左子树照旧右子树举行查找，可以将查找时间减少到对数级别（O(log n)），在最优环境下。
插入：新插入的节点根据其值被放到合适的位置以保持树的排序性质。
删除：删除节点可能涉及替换、移动或重新连接节点以维持树的完整性和排序规则。
遍历顺序：
中序遍历（Inorder Traversal）：对于二叉搜索树来说，中序遍历的结果是一个递增排序的序列。
由于这些特点，二叉搜索树在计算机科学中广泛应用，特别是在必要频繁查询和更新动态集合的环境下，如数据库索引和文件体系等。
9.2 get方法实现
9.2.1 普通get方法
public class BSTree1 {
BSTNode root;//根节点
public BSTree1(BSTNode root) {
this.root = root;
}
public BSTree1() {
}
//根据key查找相应的值 非递归实现
public Object get(int key) {
BSTNode node=root;
while (node!=null){
if(node.key>key){
node=node.left;
} else if (node.key<key) {
node=node.right;
}else{
return node.value;
}
}
return null;
}
//根据key查找相应的值 递归实现
/*public Object get(int key) {
return get(root, key);
}
public Object get(BSTNode node, int key) {
if (node == null) {
return null;
}
if (node.key > key) {
return get(node.left, key);
} else if (node.key < key) {
return get(node.right, key);
} else {
return node.value;
}
}*/
static class BSTNode {
int key;
Object value;
BSTNode left;
BSTNode right;
public BSTNode(int key) {
this.key = key;
}
public BSTNode(int key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
9.2.2 泛型key，value
只要具备比较巨细功能的类都可以作为key，而具备比较巨细功能只必要继续Comparable接口即可,value也可以用泛型来指定。
public class BSTree2<T extends Comparable<T>,V> {
BSTNode<T,V> root;//根节点
public BSTree2(BSTNode root) {
this.root = root;
}
public BSTree2() {
}
//泛型key 优化，接口必须继承Comparable
public V get(T key){
BSTNode<T,V> node=root;
while (node!=null){
int res = node.key.compareTo(key);
if(res>0){
node=node.left;
} else if (res<0) {
node=node.right;
}else{
return node.value;
}
}
return null;
}
static class BSTNode<T,V> {
T key;
V value;
BSTNode<T,V>left;
BSTNode<T,V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T,V> left, BSTNode<T,V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
} 9.3 min,max方法实现
public class BSTree3<T extends Comparable<T>, V> {
BSTNode<T, V> root;//根节点
public BSTree3(BSTNode root) {
this.root = root;
}
public BSTree3() {
}
//非递归实现
public V min() {
BSTNode<T, V> curr = root;
if(curr ==null) return null;
while (curr.left != null) {
curr = curr.left;
}
return curr.value;
}
public V max() {
BSTNode<T, V> curr = root;
if(curr ==null) return null;
while (curr.right != null) {
curr = curr.right;
}
return curr.value;
}
//递归实现
/*public V min(){
return min(root);
}
public V min(BSTNode<T,V> node){
if(node ==null) return null;
if(node.left!=null){
return min(node.left);
}else{
return node.value;
}
}
public V max(){
return max(root);
}
public V max(BSTNode<T,V> node){
if(node ==null) return null;
if(node.right!=null){
return max(node.right);
}else{
return node.value;
}
}*/
static class BSTNode<T, V> {
T key;
V value;
BSTNode<T, V> left;
BSTNode<T, V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
} 9.4 put方法实现
//put
public class BSTree4<T extends Comparable<T>, V> {
BSTNode<T, V> root;//根节点
public BSTree4(BSTNode root) {
this.root = root;
}
public BSTree4() {
}
/*
* 有该节点，更新value，没有则新增
* */
public void put(T key,V value){
BSTNode<T,V>node=root;
BSTNode<T,V>parent=node;
while (node!=null){
parent=node;
int res = node.key.compareTo(key);
if(res>0){
node=node.left;
} else if (res<0) {
node=node.right;
}else{
node.value=value;
return;
}
}
//没找到新增节点
BSTNode<T,V>newNode=new BSTNode<>(key,value);
//树为空
if(parent==null){
root=newNode;
return;
}
int res = parent.key.compareTo(key);
if(res>0){
parent.left=newNode;
}else if(res<0){
parent.right=newNode;
}
}
static class BSTNode<T, V> {
T key;
V value;
BSTNode<T, V> left;
BSTNode<T, V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
9.5 前任 后继方法实现
对于一般的二叉搜索树来说，其特性是左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。 我们首先必要找到目标节点。
然后从目标节点开始回溯到其父节点，假如目标节点是其父节点的左孩子，则其“前任”就是其父节点；
假如不是（即目标节点是其父节点的右孩子），则继续向上回溯至其父节点的父节点，重复此过程。
假如在回溯过程中，我们到达了根节点且根节点是目标节点的父节点，而且目标节点是其右孩子，那么说明目标节点没有“前任”。
前任：
假如目标有左子树，此时前任就是左子树的最大值。
假如目标没有左子树，离他迩来的自左而来的祖先就是他的前任。
后继：
假如目标有右子树，此时前任就是右子树的最小值。
假如目标没有右子树，离他迩来的自右而来的祖先就是他的前任。
//前任后继
public class BSTree5<T extends Comparable<T>, V> {
BSTNode<T, V> root;//根节点
public BSTree5(BSTNode root) {
this.root = root;
}
public BSTree5() {
}
/*
* 如果目标有左子树，此时前任就是左子树的最大值。
* 如果目标没有左子树，离他最近的自左而来的祖先就是他的前任。
* */
public V successor(T key) {
BSTNode<T, V> curr = root;
BSTNode<T, V> leftAncestor = null;
while (curr != null) {
int res = key.compareTo(curr.key);
if (res < 0) {
curr = curr.left;
} else if (res > 0) {
leftAncestor=curr;
curr = curr.right;
} else {
//curr为查找到的节点
break;
}
}
//未找到
if(curr==null){
return null;
}
//有左子树
if(curr.left!=null){
curr=curr.left;
while (curr.right!=null){
curr=curr.right;
}
return curr.value;
}
//节点没有左子树
return leftAncestor==null?null:leftAncestor.value;
}
/*
* 如果目标有右子树，此时前任就是右子树的最大值。
* 如果目标没有右子树，离他最近的自右而来的祖先就是他的前任。
* */
public V predecessor(T key){
BSTNode<T, V> curr = root;
BSTNode<T, V> rightAncestor = null;
while (curr != null) {
int res = key.compareTo(curr.key);
if (res < 0) {
rightAncestor=curr;
curr = curr.left;
} else if (res > 0) {
curr = curr.right;
} else {
//curr为查找到的节点
break;
}
}
//未找到
if(curr==null){
return null;
}
//有左子树
if(curr.right!=null){
curr=curr.right;
while (curr.left!=null){
curr=curr.left;
}
return curr.value;
}
//节点没有左子树
return rightAncestor==null?null:rightAncestor.value;
}
static class BSTNode<T, V> {
T key;
V value;
BSTNode<T, V> left;
BSTNode<T, V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
} 9.6 删除方法实现
1.删除没有子节点的节点：假如要删除的节点没有子节点，那么可以直接删除该节点，并将其父节点指向该节点的引用设置为 None。
2.删除只有一个子节点的节点：假如要删除的节点只有一个子节点（左或右）。
2.1 删除元素为父元素左子结点：子节点作为父元素的左子结点。
2.2 删除元素为父元素右子结点：子节点作为父元素的右子结点。
3.删除有两个子节点的节点：让被删除节点的后继节点顶替当前节点，分为两种
3.1 后继节点为删除节点的直接子节点：直接顶替删除节点即可。
3.2 后继节点非删除节点的直接子节点：要将后任节点的子节点交给后继节点的父节点，然后用后继节点顶替被删除节点。
9.6.1 非递归实现
//删除节点
public class BSTree6<T extends Comparable<T>, V> {
BSTNode<T, V> root;//根节点
public BSTree6(BSTNode root) {
this.root = root;
}
public BSTree6() {
}
public V delete(T key) {
BSTNode<T, V> curr = root;
// 父节点
BSTNode<T, V> parent = null;
while (curr != null) {
int res = key.compareTo(curr.key);
if (res < 0) {
parent = curr;
curr = curr.left;
} else if (res > 0) {
parent = curr;
curr = curr.right;
} else {
//curr为查找到的节点
break;
}
}
//未找到
if (curr == null) {
return null;
}
//删除操作
if (curr.left == null) {
//有右子节点，没有左子节点 将元素托管给父元素
shift(parent, curr, curr.right);
} else if (curr.left != null) {
//有左子节点，没有右子节点 将元素托管给父元素
shift(parent, curr, curr.left);
} else {
//左右子节点都存在
// 1.查找被删除节点后继节点
BSTNode<T, V> proNode = curr.right;
BSTNode<T, V> sParent = curr;
while (proNode != null) {
//保存父节点信息
sParent = proNode;
//找到右子树最小值，没有left属性的元素
proNode = proNode.left;
}
// 2.处理被删除节点后继节点的情况后
// 2.1继节点为被删除元素的直接子节点（直接替换）
// 2.2继节点为被删除元素的非直接子节点 将后任节点的子节点交给后继节点的父节点
if (sParent != curr) {
//删除后继节点并将后继节点右侧节点托管给后继节点的父节点（因为查找后继节点的操作，不断像left查找，不可能存在左侧节点）
shift(sParent, proNode, proNode.right);
//还要将被删除节点的右侧节点托管给后继节点
proNode.right=curr.right;
}
// 3.用后继节点替换被删除节点(删除当前节点将后继节点托管给父节点)
shift(parent, curr, proNode);
//将被删除节点的左侧节点托管给后继节点
proNode.left = curr.left;
}
return curr.value;
}
private void shift(BSTNode<T, V> parent, BSTNode<T, V> curr, BSTNode<T, V> child) {
if (parent == null) {
//被删除节点没有父元素
root = curr;
} else if (curr == parent.left) {
//删除节点为父节点的左孩子
parent.left = child;
} else {
//删除节点为父节点的右孩子
parent.right = child;
}
}
static class BSTNode<T, V> {
T key;
V value;
BSTNode<T, V> left;
BSTNode<T, V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
9.6.2 递归实现
//删除节点 非递归
public class BSTree6<T extends Comparable<T>, V> {
BSTNode<T, V> root;//根节点
public BSTree6(BSTNode root) {
this.root = root;
}
public BSTree6() {
}
public V delete(T key) {
ArrayList<V> arrayList = new ArrayList<>();
root = delete(key, root, arrayList);
return arrayList.isEmpty() ? null : arrayList.get(0);
}
private BSTNode delete(T key, BSTNode<T, V> node, ArrayList<V> arrayList) {
if (node == null) {
return null;
}
int res = key.compareTo(node.key);
if (res < 0) {
//当前节点的左侧子元素更新为删除结束后剩下的元素
node.left = delete(key, node.left, arrayList);
return node;
}
if (res > 0) {
node.right = delete(key, node.right, arrayList);
return node;
}
arrayList.add(node.value);
//只有右子元素
if (node.left == null) {
return node.right;
}
//只有左子元素
if (node.right == null) {
return node.left;
}
//有两个子元素
//删除节点与后继节点相邻
BSTNode<T, V> s = node.left;
BSTNode<T, V> sParent = node;
while (s.left != node) {
s = s.left;
}
//删除节点与后继节点不相邻
s.right = delete(s.key, node.right, new ArrayList<>());
//更新后继节点的左子元素为删除节点的左子元素
s.left = node.left;
return s;
}
private void shift(BSTNode<T, V> parent, BSTNode<T, V> curr, BSTNode<T, V> child) {
if (parent == null) {
//被删除节点没有父元素
root = curr;
} else if (curr == parent.left) {
//删除节点为父节点的左孩子
parent.left = child;
} else {
//删除节点为父节点的右孩子
parent.right = child;
}
}
static class BSTNode<T, V> {
T key;
V value;
BSTNode<T, V> left;
BSTNode<T, V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
} 9.7 范围查询
使用中序遍历，从小到大遍历，将符合条件的值添加到List中：
//范围查询
public class BSTree8<T extends Comparable<T>, V> {
BSTNode<T, V> root;//根节点
public BSTree8(BSTNode root) {
this.root = root;
}
public BSTree8() {
}
/*
* 中序遍历可以得到由小到大的结果
* 判断与key的关系添加到list内
* 将list返回
* */
//查找小于key
public ArrayList<V> less(T key){
ArrayList<V>res=new ArrayList<>();
BSTNode<T,V>p=root;
LinkedList<BSTNode<T,V>> stack=new LinkedList();
while (p!=null || !stack.isEmpty()){
if(p!=null){
//未走到最左
stack.push(p);
p=p.left;
}else{
//到头之后弹栈
BSTNode<T, V> pop = stack.pop();
//处理值
int popRes = pop.key.compareTo(key);
if(popRes<0){
res.add(pop.value);
}else {
break;
}
//弹出之后走右侧节点
p=pop.right;
}
}
return res;
}
//查找大于key
public ArrayList<V> greater(T key){
ArrayList<V>res=new ArrayList<>();
BSTNode<T,V>p=root;
LinkedList<BSTNode<T,V>> stack=new LinkedList();
while (p!=null || !stack.isEmpty()){
if(p!=null){
//未走到最左
stack.push(p);
p=p.left;
}else{
//到头之后弹栈
BSTNode<T, V> pop = stack.pop();
//处理值
int popRes = pop.key.compareTo(key);
if(popRes>0){
res.add(pop.value);
}
//弹出之后走右侧节点
p=pop.right;
}
}
return res;
}
//查找大于等于key1,小于等于key2
public ArrayList<V> between(T key1,T key2){
ArrayList<V>res=new ArrayList<>();
BSTNode<T,V>p=root;
LinkedList<BSTNode<T,V>> stack=new LinkedList();
while (p!=null || !stack.isEmpty()){
if(p!=null){
//未走到最左
stack.push(p);
p=p.left;
}else{
//到头之后弹栈
BSTNode<T, V> pop = stack.pop();
//处理值
int popRes1 = pop.key.compareTo(key1);
int popRes2 = pop.key.compareTo(key2);
if(popRes1>0 && popRes2<0){
res.add(pop.value);
}
//弹出之后走右侧节点
p=pop.right;
}
}
return res;
}
static class BSTNode<T, V> {
T key;
V value;
BSTNode<T, V> left;
BSTNode<T, V> right;
public BSTNode(T key) {
this.key = key;
}
public BSTNode(T key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
10.AVL树
AVL 树（平衡二叉搜索树）
二叉搜索树在插入和删除时，节点可能失衡
假如在插入和删除时通过旋转,始终让二叉搜索树保持平衡,称为自平衡的二叉搜索树
AVL是自平衡二又搜索树的实现之一
假如一个节点的左右孩子，高度差超过1，则此节点失衡，才必要旋转。
10.1 获取高度
//处理节点高度
private int haight(AVLNode node) {
return node == null ? 0 : node.height;
} 10.2更新高度
//增、删、旋转更新节点高度
//最大高度+1
public void updateHeight(AVLNode treeNode) {
treeNode.height=Integer.max(haight(treeNode.left),haight(treeNode.right))+1;
}
10.1 旋转
10.1.1 平衡因子
平衡因子：一个节点左子树高度-右子树高度所得结果
小于1平衡:(0,1,-1)
大于1不平衡
>1:左边高
<-1：右边高
public int bf(AVLNode avlNode){
return haight(avlNode.left)-haight(avlNode.right);
} 10.1.2 四种失衡环境
LL
-失衡节点的 bf >1，即左边更高
-失衡节点的左孩子的bf>=0即左孩子这边也是左边更高或等
一次右旋可以恢复平衡
LR
-失衡节点的 bf >1，即左边更高
-失衡节点的左孩子的bf<0 即左孩子这边是右边更高
左子节点先左旋，将树修正为LL情况，
然后失衡节点再右旋，恢复平衡
RL
-失衡节点的 bf <-1，即右边更高
-失衡节点的右孩子的bf>0，即右孩子这边左边更高
右子节点先右旋，将树修正为RR情况，
然后失衡节点再左旋，恢复平衡
RR
-失衡节点的 bf<-1，即右边更高
-失衡节点的右孩子的bf<=0，即右孩子这边右边更高或等高
一次左旋可以恢复平衡
//右旋
/**
* @Description 返回旋转后的节点
* @Param 需要旋转的节点
**/
private AVLNode rightRotate(AVLNode redNode) {
AVLNode yellowNode = redNode.left;
/*
*黄色节点有右子节点，给右子节点重新找父级节点
*由于二叉搜索树特性，某个节点的左子节点必定小于 本身，右子节点必定大于本身
* 故：yelllow的右子节点必定大于yellow且小于rea，
* 所以，gree可以作为red的左子结点
* */
/*
AVLNode greeNode = yellowNode.right;
redNode.left = greeNode;
*/
redNode.left = yellowNode.right;
yellowNode.right = redNode;
//更新高度，红色和黄色都会改变
updateHeight(redNode);
updateHeight(yellowNode);
return yellowNode;
}
//左旋
private AVLNode leftRotate(AVLNode redNode) {
//左旋和右旋操作相反
AVLNode yellowNode = redNode.right;
//处理yellow的子节点
redNode.right = yellowNode.left;
//yellow变为跟，原red比yellow小，为yellow的left
yellowNode.left=redNode;
updateHeight(redNode);
updateHeight(yellowNode);
return yellowNode;
}
/*
* LR
-失衡节点的 bf >1，即左边更高
-失衡节点的左孩子的bf<0 即左孩子这边是右边更高
左子节点先左旋，将树修正为LL情况，
然后失衡节点再右旋，恢复平衡
* */
//先左旋再右旋
private AVLNode leftRightRotate(AVLNode node) {
//修正左子结点LL
node.left = leftRotate(node.left);
return rightRotate(node);
}
/*
* RL
-失衡节点的 bf <-1，即右边更高
-失衡节点的右孩子的bf>0，即右孩子这边左边更高
右子节点先右旋，将树修正为RR情况，
然后失衡节点再左旋，恢复平衡
* */
//先右旋再左旋
private AVLNode rightLeftRotate(AVLNode node) {
//修正右子节点为RR
node.right= rightRotate(node.left);
return leftRotate(node);
} 10.1.3 返回一个平衡后的树
//检查节点是否失衡，重新平衡
private AVLNode checkBalance(AVLNode node) {
if (node == null) {
return null;
}
//获取该节点的平衡因子
int bf = bf(node);
if (bf > 1) {
//左边更高的两种情况根据 左子树平衡因子判定
int leftBf = bf(node.left);
if (leftBf >= 0) {
//左子树左边高 LL 右旋考虑到删除时等于0也应该右旋
return rightRotate(node);
} else {
//左子树右边更高 LR
return leftRightRotate(node);
}
} else if (bf < -1) {
int rightBf = bf(node.right);
if (rightBf <= 0) {
//右子树左边更高 RR 虑到删除时等于0也要左旋
return leftRotate(node);
} else {
//右子树右边更高RL
return rightLeftRotate(node);
}
}
return node;
} 10.2 新增
public void put(int key, Object value){
doPut(root,key,value);
}
//找空位并添加新的节点
private AVLNode doPut(AVLNode node, int key, Object value) {
/*
* 1.找到空位，创建新节点
* 2.key 已存在 更新位置
* 3.继续寻找
**/
//未找到
if (node ==null){
return new AVLNode(key,value);
}
//找到了节点 重新赋值
if(key ==node.key){
node.value=value;
return node;
}
//继续查找
if(key < node.key){
//继续向左，并建立父子关系
node.left= doPut(node.left,key,value);
}else{
//向右找,并建立父子关系
node.right=doPut(node.right,key,value);
}
//更新节点高度
updateHeight(node);
//重新平衡树
return checkBalance(node);
} 10.3 删除
//删除
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
//1. node==null
if (node == null) {
return node;
}
//2.未找到key
if (key < node.key) {
//未找到key，且key小于当前节点key，继续向左
node.left = doRemove(node.left, key);
} else if (key > node.key) {
//向右找
node.right = doRemove(node.right, key);
} else {
//3.找到key
if (node.left == null && node.right == null) {
//3.1 没有子节点
return null;
} else if (node.left != null && node.right == null) {
//3.2 一个子节点（左节点）
node = node.left;
} else if (node.left == null && node.right != null) {
//3.2 一个子节点（右节点）
node = node.right;
} else {
//3.3 两个子节点
//找到他最小的后继节点，右子树向左找到底
AVLNode s=node;
while (s.left!=null){
s=s.left;
}
//s即为后继节点,将节点删除并重新修正右子树
s.right=doRemove(s.right,s.key);
//左子树为s.left,右子树为原删除节点的左子树
s.left=node.left;
node=s;
}
}
//4.更新高度
updateHeight(node);
//5.检查是否失衡
return checkBalance(node);
} 10.4 整体代码
package org.alogorithm.tree.AVLTree;public class AVLTree { static class AVLNode { int key; int height = 1;//高度初始值1 AVLNode left, right; private AVLNode root; Object value; public AVLNode(int key, Object value) { this.key = key; this.value = value; } public AVLNode(int key, AVLNode left, AVLNode right, AVLNode root) { this.key = key; this.left = left; this.right = right; this.root = root; } } //处理节点高度 private int haight(AVLNode node) { return node == null ? 0 : node.height; } //增、删、旋转更新节点高度 //最大高度+1 public void updateHeight(AVLNode treeNode) { treeNode.height = Integer.max(haight(treeNode.left), haight(treeNode.right)) + 1; } /* 平衡因子：一个节点左子树高度-右子树高度所得结果 小于1平衡:(0,1,-1) 大于1不平衡 >1:左边高 <-1：右边高 */ public int bf(AVLNode avlNode) { return haight(avlNode.left) - haight(avlNode.right); } //四种失衡环境 /* LL -失衡节点的 bf >1，即左边更高 -失衡节点的左孩子的bf>=0即左孩子这边也是左边更高或等 一次右旋可以规复平衡 LR -失衡节点的 bf >1，即左边更高 -失衡节点的左孩子的bf<0 即左孩子这边是右边更高 左子节点先左旋，将树修正为LL环境， 然后失衡节点再右旋，规复平衡 RL -失衡节点的 bf <-1，即右边更高 -失衡节点的右孩子的bf>0，即右孩子这边左边更高 右子节点先右旋，将树修正为RR环境， 然后失衡节点再左旋，规复平衡 RR -失衡节点的 bf<-1，即右边更高 -失衡节点的右孩子的bf<=0，即右孩子这边右边更高或等高 一次左旋可以规复平衡*/ //右旋 /** * @Description 返回旋转后的节点 * @Param 必要旋转的节点 **/ private AVLNode rightRotate(AVLNode redNode) { AVLNode yellowNode = redNode.left; /* *黄色节点有右子节点，给右子节点重新找父级节点 *由于二叉搜索树特性，某个节点的左子节点肯定小于 本身，右子节点肯定大于本身 * 故：yelllow的右子节点肯定大于yellow且小于rea， * 所以，gree可以作为red的左子结点 * */ /* AVLNode greeNode = yellowNode.right; redNode.left = greeNode; */ redNode.left = yellowNode.right; yellowNode.right = redNode; //更新高度，赤色和黄色都会改变 updateHeight(redNode); updateHeight(yellowNode); return yellowNode; } //左旋 private AVLNode leftRotate(AVLNode redNode) { //左旋和右旋操作相反 AVLNode yellowNode = redNode.right; //处理yellow的子节点 redNode.right = yellowNode.left; //yellow变为跟，原red比yellow小，为yellow的left yellowNode.left = redNode; updateHeight(redNode); updateHeight(yellowNode); return yellowNode; } /* * LR -失衡节点的 bf >1，即左边更高 -失衡节点的左孩子的bf<0 即左孩子这边是右边更高 左子节点先左旋，将树修正为LL环境， 然后失衡节点再右旋，规复平衡 * */ //先左旋再右旋 private AVLNode leftRightRotate(AVLNode node) { //修正左子结点LL node.left = leftRotate(node.left); return rightRotate(node); } /* * RL -失衡节点的 bf <-1，即右边更高 -失衡节点的右孩子的bf>0，即右孩子这边左边更高 右子节点先右旋，将树修正为RR环境， 然后失衡节点再左旋，规复平衡 * */ //先右旋再左旋 private AVLNode rightLeftRotate(AVLNode node) { //修正右子节点为RR node.right = rightRotate(node.left); return leftRotate(node); } //检查节点是否失衡，重新平衡
private AVLNode checkBalance(AVLNode node) {
if (node == null) {
return null;
}
//获取该节点的平衡因子
int bf = bf(node);
if (bf > 1) {
//左边更高的两种情况根据 左子树平衡因子判定
int leftBf = bf(node.left);
if (leftBf >= 0) {
//左子树左边高 LL 右旋考虑到删除时等于0也应该右旋
return rightRotate(node);
} else {
//左子树右边更高 LR
return leftRightRotate(node);
}
} else if (bf < -1) {
int rightBf = bf(node.right);
if (rightBf <= 0) {
//右子树左边更高 RR 虑到删除时等于0也要左旋
return leftRotate(node);
} else {
//右子树右边更高RL
return rightLeftRotate(node);
}
}
return node;
} AVLNode root; public void put(int key, Object value) { doPut(root, key, value); } //找空位并添加新的节点 private AVLNode doPut(AVLNode node, int key, Object value) { /* * 1.找到空位，创建新节点 * 2.key 已存在 更新位置 * 3.继续寻找 **/ //未找到 if (node == null) { return new AVLNode(key, value); } //找到了节点 重新赋值 if (key == node.key) { node.value = value; return node; } //继续查找 if (key < node.key) { //继续向左，并创建父子关系 node.left = doPut(node.left, key, value); } else { //向右找,并创建父子关系 node.right = doPut(node.right, key, value); } //更新节点高度 updateHeight(node); //重新平衡树 return checkBalance(node); } //删除
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
//1. node==null
if (node == null) {
return node;
}
//2.未找到key
if (key < node.key) {
//未找到key，且key小于当前节点key，继续向左
node.left = doRemove(node.left, key);
} else if (key > node.key) {
//向右找
node.right = doRemove(node.right, key);
} else {
//3.找到key
if (node.left == null && node.right == null) {
//3.1 没有子节点
return null;
} else if (node.left != null && node.right == null) {
//3.2 一个子节点（左节点）
node = node.left;
} else if (node.left == null && node.right != null) {
//3.2 一个子节点（右节点）
node = node.right;
} else {
//3.3 两个子节点
//找到他最小的后继节点，右子树向左找到底
AVLNode s=node;
while (s.left!=null){
s=s.left;
}
//s即为后继节点,将节点删除并重新修正右子树
s.right=doRemove(s.right,s.key);
//左子树为s.left,右子树为原删除节点的左子树
s.left=node.left;
node=s;
}
}
//4.更新高度
updateHeight(node);
//5.检查是否失衡
return checkBalance(node);
}} 11. 红黑树
红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少
红黑树特性
1.所有节点都有两种颜色:红与黑
2.所有 null 视为玄色
3.赤色节点不能相邻
4.根节点是玄色
5.从根到任意一个叶子节点，路径中的玄色节点数一样(玄色完美平衡)
补充：玄色叶子结点一般是成对出现，单独出现肯定不平衡
11.1 node内部类
private static class Node {
int key;
Object value;
Node left;
Node right;
Node parent;//父节点
Color color = RED;//颜色
//是否是左孩子，左未true，右为false
boolean isLeftChild() {
return parent != null && this == parent.left;
}
//获取叔叔节点
Node uncle() {
//有父节点，和父节点的父节点才能有叔叔节点
if (parent == null || parent.parent == null) {
return null;
}
if (parent.isLeftChild()) {
//如果父亲为左子节点则返回右子节点，
return parent.parent.right;
} else {
//如果父亲为右子节点则返回左子节点
return parent.parent.left;
}
}
//获取兄弟节点
Node sibling() {
if(parent==null){
return null;
}
if(this.isLeftChild()){
return parent.right;
}else {
return parent.left;
}
}
} 11.2 判定颜色
//判断颜色
boolean isRed(Node node){
return node!=null&&node.color==RED;
}
boolean isBlack(Node node){
return node==null||node.color==BLACK;
} 11.3 左旋和右旋
//和AVL树的不同
// 右旋1.父(Parent)的处理2.旋转后新根的父子关系方法内处理
void rotateRight(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.left;
Node gree = yellow.right;
//右旋之后换色节点的右子结点变为Pink
yellow.right = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.left = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.left == pink) {
//处理父子关系，yellow代替pink
parent.left = yellow;
} else {
parent.right = yellow;
}
}
void rotateLeft(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.right;
Node gree = yellow.left;
//右旋之后换色节点的右子结点变为Pink
yellow.left = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.right = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.right == pink) {
//处理父子关系，yellow代替pink
parent.right = yellow;
} else {
parent.left = yellow;
}
} 11.4 新增或更新
//新增或更新
void put(int key, Object value) {
Node p = root;
Node parent = null;
while (p != null) {
parent = p;
if (key < p.key) {
//向左找
p = p.left;
} else if (key > p.key) {
p = p.right;
} else {
//更新
p.value = value;
return;
}
}
//插入
Node interestNode = new Node(key, value);
//如果parent为空
if (parent == null) {
root = interestNode;
} else if (key < parent.key) {
parent.left = interestNode;
interestNode.parent = parent;
} else {
parent.right = interestNode;
interestNode.parent = parent;
}
fixRedRed(interestNode);
}
/*
* 1.所有节点都有两种颜色:红与黑
* 2.所有 null 视为黑色
* 3.红色节点不能相邻
* 4.根节点是黑色
* 5.从根到任意一个叶子节点，路径中的黑色节点数一样(黑色完美平衡)
* */
//修复红红不平衡
void fixRedRed(Node x) {
/*
* 插入节点均视为红色
* 插入节点的父亲为红色
* 触发红红相邻
* case 3:叔叔为红色
* case 4:叔叔为黑色
* */
//case 1:插入节点为根节点，将根节点变黑
if (x == root) {
x.color = BLACK;
return;
}
//case 2:插入节点的父亲若为黑色树的红黑性质不变，无需调整
if (isBlack(x.parent)) {
return;
}
Node parent = x.parent;
Node uncle = x.uncle();
Node grandParent = parent.parent;
//插入节点的父亲为红色
if (isRed(uncle)) {
//红红相邻叔叔为红色时（仅通过变色即可）
/*
* 为了保证黑色平衡，连带的叔叔也变为黑色·
* 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色祖父如果变成红色，
* 可能会接着触发红红相邻，因此对将祖父进行递归调整，祖父的父亲变为黑色
* */
parent.color = BLACK;
uncle.color = BLACK;
grandParent.color = RED;
fixRedRed(grandParent);
return;
} else {
//触发红红相邻叔叔为黑色
/*
* 1.父亲为左孩子，插入节点也是左孩子，此时即 LL不平衡（右旋一次）
* 2.父亲为左孩子，插入节点是右孩子，此时即 LR不平衡（父亲左旋，祖父右旋）
* 3.父亲为右孩子，插入节点也是右孩子，此时即 RR不平衡（左旋一次）
* 4.父亲为右孩子，插入节点是左孩子，此时即 RL不平衡（父亲右旋，祖父左旋）
*
*/
if (parent.isLeftChild() && x.isLeftChild()) {
//如果父亲为左子节点，查询节点也为左子结点即为LL（祖父右旋处理）
//父节点变黑（和叔叔节点同为黑色）
parent.color = BLACK;
//祖父节点变红
grandParent.color = RED;
rotateRight(grandParent);
} else if (parent.isLeftChild() && !x.isLeftChild()) {
//parent为左子节点，插入节点为右子节点，LR（父亲左旋，祖父右旋）
rotateLeft(parent);
//插入节点变为黑色
x.color=BLACK;
//祖父变为红色
grandParent.color=RED;
rotateRight(grandParent);
} else if (!parent.isLeftChild()&&!x.isLeftChild()) {
//父节点变黑（和叔叔节点同为黑色）
parent.color = BLACK;
//祖父节点变红
grandParent.color = RED;
rotateLeft(grandParent);
}else if(!parent.isLeftChild()&&x.isLeftChild()){
rotateRight(parent);
//插入节点变为黑色
x.color=BLACK;
//祖父变为红色
grandParent.color=RED;
rotateLeft(grandParent);
}
}
} 11.5 删除
//删除
/*
* 删除
* 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
* */
public void remove(int key) {
Node deleted = find(key);
if (deleted == null) {
return;
}
doRemove(deleted);
}
//检测双黑节点删除
/*
*
* 删除节点和剩下节点都是黑触发双黑，双黑意思是，少了一个黑
* case 3:删除节点或剩余节点的兄弟为红此时两个侄子定为黑
* case 4:删除节点或剩余节点的兄弟、和兄弟孩子都为黑
* case 5:删除节点的兄弟为黑,至少一个红侄子
*
* */
private void fixDoubleBlack(Node x) {
//把case3处理为case4和case5
if (x == root) {
return;
}
Node parent = x.parent;
Node sibling = x.sibling();
if (sibling.color == RED) {
//进入case3
if (x.isLeftChild()) {
//如果是做孩子就进行左旋
rotateLeft(parent);
} else {
//如果是右孩子就进行右旋
rotateRight(parent);
}
//父亲颜色变为红色（父亲变色前肯定为黑色）
parent.color = RED;
//兄弟变为黑色
sibling.color = BLACK;
//此时case3 已经被转换为 case4或者case5
fixDoubleBlack(x);
return;
}
//兄弟为黑
//两个侄子都为黑
if (sibling != null) {
if (isBlack(sibling.left) && isBlack(sibling.right)) {
/*
* case 4:被调整节点的兄弟为黑,两个侄于都为黑
* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
* 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
* 如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
* */
//将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
sibling.color = RED;
if (isRed(parent)) {
// 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
parent.color = BLACK;
} else {
//如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
fixDoubleBlack(parent);
}
} else {
//CASE5 至少有一个侄子不是黑色
/*
*
* case 5:被调整节点的兄弟为黑
* 如果兄弟是左孩子，左侄子是红LL 不平衡
* 如果兄弟是左孩子，右侄子是红LR 不平衡
* 如果兄弟是右孩子，右侄于是红RR 不平衡
* 如果兄弟是右孩子，左侄于是红RL 不平衡
* */
if(sibling.isLeftChild()&&isRed(sibling.left)){
// 如果兄弟是左孩子，左侄子是红LL 不平衡
rotateRight(parent);
//兄弟的做孩子变黑
sibling.left.color=BLACK;
//兄弟变成父亲的颜色
sibling.color= parent.color;
//父亲变黑
parent.color=BLACK;
}else if(sibling.isLeftChild()&&isRed(sibling.right)){
//如果兄弟是左孩子，右侄子是红LR 不平衡
//变色必须在上 否则旋转后会空指针
//兄弟的右孩子变为父节点颜色
sibling.right.color= parent.color;
//父节点变黑
parent.color=BLACK;
rotateLeft(sibling);
rotateRight(parent);
}
}
} else {
fixDoubleBlack(parent);
}
}
private void doRemove(Node deleted) {
Node replaced = findReplaced(deleted);
Node parent = deleted.parent;
if (replaced == null) {
//没有子节点
/* case1:删的是根节点,没有子节点
* 删完了，直接将 root=null
* */
if (deleted == root) {
root = null;
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
if (isBlack(deleted)) {
//复杂处理,先调整平衡再删除
fixDoubleBlack(deleted);
} else {
//红色不处理
}
//删除的不是根节点且没有孩子
if (deleted.isLeftChild()) {
parent.left = null;
} else {
parent.right = null;
}
deleted.parent = null;
}
return;
} else if (replaced.left == null || replaced.right == null) {
//有一个子节点
/* case1:删的是根节点,有一个子节点
* 用剩余节点替换了根节点的 key，Value，根节点孩子=null，颜色保持黑色 不变
* */
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
} else {
//删除的不是根节点但是有一个孩子
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.right = deleted.left = deleted.parent = null;
if (isBlack(deleted) && isBlack(replaced)) {
//如果删除的是黑色剩下的也是黑色，需要复杂处理，先删除再平衡
fixDoubleBlack(replaced);
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
replaced.color = BLACK;
}
}
return;
} else {
//两个子节点
//交换删除节点和删除节点的后几点的key，value，这
// 样被删除节点就只有一个子节点或没有子节点了
int t = deleted.key;
deleted.key = replaced.key;
replaced.key = t;
Object v = deleted.value;
deleted.value = replaced.value;
replaced.value = v;
doRemove(replaced);
return;
}
}
private Node find(int key) {
Node p = root;
while (p != null) {
if (key > p.key) {
//key更大向右找
p = p.right;
} else if (key < p.key) {
//向左找
p = p.left;
} else {
return p;
}
}
return null;
}
//查找删除后的剩余节点
private Node findReplaced(Node deleted) {
if (deleted.left == null & deleted.right == null) {
//没有子节点
return null;
} else if (deleted.left == null) {
return deleted.right;
} else if (deleted.right == null) {
return deleted.left;
} else {
Node s = deleted.right;
while (s != null) {
//右子树的最小值
s = s.left;
}
return s;
}
}
}
11.6 完整代码
package org.alogorithm.tree;import static org.alogorithm.tree.RedBlackTree.Color.BLACK;import static org.alogorithm.tree.RedBlackTree.Color.RED;public class RedBlackTree { enum Color {RED, BLACK} private Node root; private static class Node { int key; Object value; Node left; Node right; Node parent;//父节点 Color color = RED;//颜色 public Node() { } public Node(int key, Object value) { this.key = key; this.value = value; } //是否是左孩子，左未true，右为false boolean isLeftChild() { return parent != null && this == parent.left; } //获取叔叔节点 Node uncle() { //有父节点，和父节点的父节点才气有叔叔节点 if (parent == null || parent.parent == null) { return null; } if (parent.isLeftChild()) { //假如父亲为左子节点则返回右子节点， return parent.parent.right; } else { //假如父亲为右子节点则返回左子节点 return parent.parent.left; } } //获取兄弟节点 Node sibling() { if (parent == null) { return null; } if (this.isLeftChild()) { return parent.right; } else { return parent.left; } } } //判定颜色 boolean isRed(Node node) { return node != null && node.color == RED; } boolean isBlack(Node node) { return node == null || node.color == BLACK; } //和AVL树的不同
// 右旋1.父(Parent)的处理2.旋转后新根的父子关系方法内处理
void rotateRight(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.left;
Node gree = yellow.right;
//右旋之后换色节点的右子结点变为Pink
yellow.right = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.left = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.left == pink) {
//处理父子关系，yellow代替pink
parent.left = yellow;
} else {
parent.right = yellow;
}
}
void rotateLeft(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.right;
Node gree = yellow.left;
//右旋之后换色节点的右子结点变为Pink
yellow.left = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.right = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.right == pink) {
//处理父子关系，yellow代替pink
parent.right = yellow;
} else {
parent.left = yellow;
}
} //新增或更新 void put(int key, Object value) { Node p = root; Node parent = null; while (p != null) { parent = p; if (key < p.key) { //向左找 p = p.left; } else if (key > p.key) { p = p.right; } else { //更新 p.value = value; return; } } //插入 Node interestNode = new Node(key, value); //假如parent为空 if (parent == null) { root = interestNode; } else if (key < parent.key) { parent.left = interestNode; interestNode.parent = parent; } else { parent.right = interestNode; interestNode.parent = parent; } fixRedRed(interestNode); } /* * 1.所有节点都有两种颜色:红与黑 * 2.所有 null 视为玄色 * 3.赤色节点不能相邻 * 4.根节点是玄色 * 5.从根到任意一个叶子节点，路径中的玄色节点数一样(玄色完美平衡) * */ //修复红红不平衡 void fixRedRed(Node x) { /* * 插入节点均视为赤色 * 插入节点的父亲为赤色 * 触发红红相邻 * case 3:叔叔为赤色 * case 4:叔叔为玄色 * */ //case 1:插入节点为根节点，将根节点变黑 if (x == root) { x.color = BLACK; return; } //case 2:插入节点的父亲若为玄色树的红黑性质不变，无需调整 if (isBlack(x.parent)) { return; } Node parent = x.parent; Node uncle = x.uncle(); Node grandParent = parent.parent; //插入节点的父亲为赤色 if (isRed(uncle)) { //红红相邻叔叔为赤色时（仅通过变色即可） /* * 为了包管玄色平衡，连带的叔叔也变为玄色· * 祖父假如是玄色不变，会造成这颗子树玄色过多，因此祖父节点变为赤色祖父假如酿成赤色， * 可能会接着触发红红相邻，因此对将祖父举行递归调整，祖父的父亲变为玄色 * */ parent.color = BLACK; uncle.color = BLACK; grandParent.color = RED; fixRedRed(grandParent); return; } else { //触发红红相邻叔叔为玄色 /* * 1.父亲为左孩子，插入节点也是左孩子，此时即 LL不平衡（右旋一次） * 2.父亲为左孩子，插入节点是右孩子，此时即 LR不平衡（父亲左旋，祖父右旋） * 3.父亲为右孩子，插入节点也是右孩子，此时即 RR不平衡（左旋一次） * 4.父亲为右孩子，插入节点是左孩子，此时即 RL不平衡（父亲右旋，祖父左旋） * */ if (parent.isLeftChild() && x.isLeftChild()) { //假如父亲为左子节点，查询节点也为左子结点即为LL（祖父右旋处理） //父节点变黑（和叔叔节点同为玄色） parent.color = BLACK; //祖父节点变红 grandParent.color = RED; rotateRight(grandParent); } else if (parent.isLeftChild() && !x.isLeftChild()) { //parent为左子节点，插入节点为右子节点，LR（父亲左旋，祖父右旋） rotateLeft(parent); //插入节点变为玄色 x.color = BLACK; //祖父变为赤色 grandParent.color = RED; rotateRight(grandParent); } else if (!parent.isLeftChild() && !x.isLeftChild()) { //父节点变黑（和叔叔节点同为玄色） parent.color = BLACK; //祖父节点变红 grandParent.color = RED; rotateLeft(grandParent); } else if (!parent.isLeftChild() && x.isLeftChild()) { rotateRight(parent); //插入节点变为玄色 x.color = BLACK; //祖父变为赤色 grandParent.color = RED; rotateLeft(grandParent); } } } //删除
/*
* 删除
* 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
* */
public void remove(int key) {
Node deleted = find(key);
if (deleted == null) {
return;
}
doRemove(deleted);
}
//检测双黑节点删除
/*
*
* 删除节点和剩下节点都是黑触发双黑，双黑意思是，少了一个黑
* case 3:删除节点或剩余节点的兄弟为红此时两个侄子定为黑
* case 4:删除节点或剩余节点的兄弟、和兄弟孩子都为黑
* case 5:删除节点的兄弟为黑,至少一个红侄子
*
* */
private void fixDoubleBlack(Node x) {
//把case3处理为case4和case5
if (x == root) {
return;
}
Node parent = x.parent;
Node sibling = x.sibling();
if (sibling.color == RED) {
//进入case3
if (x.isLeftChild()) {
//如果是做孩子就进行左旋
rotateLeft(parent);
} else {
//如果是右孩子就进行右旋
rotateRight(parent);
}
//父亲颜色变为红色（父亲变色前肯定为黑色）
parent.color = RED;
//兄弟变为黑色
sibling.color = BLACK;
//此时case3 已经被转换为 case4或者case5
fixDoubleBlack(x);
return;
}
//兄弟为黑
//两个侄子都为黑
if (sibling != null) {
if (isBlack(sibling.left) && isBlack(sibling.right)) {
/*
* case 4:被调整节点的兄弟为黑,两个侄于都为黑
* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
* 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
* 如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
* */
//将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
sibling.color = RED;
if (isRed(parent)) {
// 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
parent.color = BLACK;
} else {
//如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
fixDoubleBlack(parent);
}
} else {
//CASE5 至少有一个侄子不是黑色
/*
*
* case 5:被调整节点的兄弟为黑
* 如果兄弟是左孩子，左侄子是红LL 不平衡
* 如果兄弟是左孩子，右侄子是红LR 不平衡
* 如果兄弟是右孩子，右侄于是红RR 不平衡
* 如果兄弟是右孩子，左侄于是红RL 不平衡
* */
if(sibling.isLeftChild()&&isRed(sibling.left)){
// 如果兄弟是左孩子，左侄子是红LL 不平衡
rotateRight(parent);
//兄弟的做孩子变黑
sibling.left.color=BLACK;
//兄弟变成父亲的颜色
sibling.color= parent.color;
//父亲变黑
parent.color=BLACK;
}else if(sibling.isLeftChild()&&isRed(sibling.right)){
//如果兄弟是左孩子，右侄子是红LR 不平衡
//变色必须在上 否则旋转后会空指针
//兄弟的右孩子变为父节点颜色
sibling.right.color= parent.color;
//父节点变黑
parent.color=BLACK;
rotateLeft(sibling);
rotateRight(parent);
}
}
} else {
fixDoubleBlack(parent);
}
}
private void doRemove(Node deleted) {
Node replaced = findReplaced(deleted);
Node parent = deleted.parent;
if (replaced == null) {
//没有子节点
/* case1:删的是根节点,没有子节点
* 删完了，直接将 root=null
* */
if (deleted == root) {
root = null;
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
if (isBlack(deleted)) {
//复杂处理,先调整平衡再删除
fixDoubleBlack(deleted);
} else {
//红色不处理
}
//删除的不是根节点且没有孩子
if (deleted.isLeftChild()) {
parent.left = null;
} else {
parent.right = null;
}
deleted.parent = null;
}
return;
} else if (replaced.left == null || replaced.right == null) {
//有一个子节点
/* case1:删的是根节点,有一个子节点
* 用剩余节点替换了根节点的 key，Value，根节点孩子=null，颜色保持黑色 不变
* */
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
} else {
//删除的不是根节点但是有一个孩子
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.right = deleted.left = deleted.parent = null;
if (isBlack(deleted) && isBlack(replaced)) {
//如果删除的是黑色剩下的也是黑色，需要复杂处理，先删除再平衡
fixDoubleBlack(replaced);
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
replaced.color = BLACK;
}
}
return;
} else {
//两个子节点
//交换删除节点和删除节点的后几点的key，value，这
// 样被删除节点就只有一个子节点或没有子节点了
int t = deleted.key;
deleted.key = replaced.key;
replaced.key = t;
Object v = deleted.value;
deleted.value = replaced.value;
replaced.value = v;
doRemove(replaced);
return;
}
}
private Node find(int key) {
Node p = root;
while (p != null) {
if (key > p.key) {
//key更大向右找
p = p.right;
} else if (key < p.key) {
//向左找
p = p.left;
} else {
return p;
}
}
return null;
}
//查找删除后的剩余节点
private Node findReplaced(Node deleted) {
if (deleted.left == null & deleted.right == null) {
//没有子节点
return null;
} else if (deleted.left == null) {
return deleted.right;
} else if (deleted.right == null) {
return deleted.left;
} else {
Node s = deleted.right;
while (s != null) {
//右子树的最小值
s = s.left;
}
return s;
}
}
}
10.AVL树
AVL 树（平衡二叉搜索树）
二叉搜索树在插入和删除时，节点可能失衡
假如在插入和删除时通过旋转,始终让二叉搜索树保持平衡,称为自平衡的二叉搜索树
AVL是自平衡二又搜索树的实现之一
假如一个节点的左右孩子，高度差超过1，则此节点失衡，才必要旋转。
10.1 获取高度
//处理节点高度
private int haight(AVLNode node) {
return node == null ? 0 : node.height;
} 10.2更新高度
//增、删、旋转更新节点高度
//最大高度+1
public void updateHeight(AVLNode treeNode) {
treeNode.height=Integer.max(haight(treeNode.left),haight(treeNode.right))+1;
} 10.1 旋转
10.1.1 平衡因子
平衡因子：一个节点左子树高度-右子树高度所得结果
小于1平衡:(0,1,-1)
大于1不平衡
>1:左边高
<-1：右边高
public int bf(AVLNode avlNode){
return haight(avlNode.left)-haight(avlNode.right);
} 10.1.2 四种失衡环境
LL
-失衡节点的 bf >1，即左边更高
-失衡节点的左孩子的bf>=0即左孩子这边也是左边更高或等
一次右旋可以恢复平衡
LR
-失衡节点的 bf >1，即左边更高
-失衡节点的左孩子的bf<0 即左孩子这边是右边更高
左子节点先左旋，将树修正为LL情况，
然后失衡节点再右旋，恢复平衡
RL
-失衡节点的 bf <-1，即右边更高
-失衡节点的右孩子的bf>0，即右孩子这边左边更高
右子节点先右旋，将树修正为RR情况，
然后失衡节点再左旋，恢复平衡
RR
-失衡节点的 bf<-1，即右边更高
-失衡节点的右孩子的bf<=0，即右孩子这边右边更高或等高
一次左旋可以恢复平衡
//右旋
/**
* @Description 返回旋转后的节点
* @Param 需要旋转的节点
**/
private AVLNode rightRotate(AVLNode redNode) {
AVLNode yellowNode = redNode.left;
/*
*黄色节点有右子节点，给右子节点重新找父级节点
*由于二叉搜索树特性，某个节点的左子节点必定小于 本身，右子节点必定大于本身
* 故：yelllow的右子节点必定大于yellow且小于rea，
* 所以，gree可以作为red的左子结点
* */
/*
AVLNode greeNode = yellowNode.right;
redNode.left = greeNode;
*/
redNode.left = yellowNode.right;
yellowNode.right = redNode;
//更新高度，红色和黄色都会改变
updateHeight(redNode);
updateHeight(yellowNode);
return yellowNode;
}
//左旋
private AVLNode leftRotate(AVLNode redNode) {
//左旋和右旋操作相反
AVLNode yellowNode = redNode.right;
//处理yellow的子节点
redNode.right = yellowNode.left;
//yellow变为跟，原red比yellow小，为yellow的left
yellowNode.left=redNode;
updateHeight(redNode);
updateHeight(yellowNode);
return yellowNode;
}
/*
* LR
-失衡节点的 bf >1，即左边更高
-失衡节点的左孩子的bf<0 即左孩子这边是右边更高
左子节点先左旋，将树修正为LL情况，
然后失衡节点再右旋，恢复平衡
* */
//先左旋再右旋
private AVLNode leftRightRotate(AVLNode node) {
//修正左子结点LL
node.left = leftRotate(node.left);
return rightRotate(node);
}
/*
* RL
-失衡节点的 bf <-1，即右边更高
-失衡节点的右孩子的bf>0，即右孩子这边左边更高
右子节点先右旋，将树修正为RR情况，
然后失衡节点再左旋，恢复平衡
* */
//先右旋再左旋
private AVLNode rightLeftRotate(AVLNode node) {
//修正右子节点为RR
node.right= rightRotate(node.left);
return leftRotate(node);
} 10.1.3 返回一个平衡后的树
//检查节点是否失衡，重新平衡
private AVLNode checkBalance(AVLNode node) {
if (node == null) {
return null;
}
//获取该节点的平衡因子
int bf = bf(node);
if (bf > 1) {
//左边更高的两种情况根据 左子树平衡因子判定
int leftBf = bf(node.left);
if (leftBf >= 0) {
//左子树左边高 LL 右旋考虑到删除时等于0也应该右旋
return rightRotate(node);
} else {
//左子树右边更高 LR
return leftRightRotate(node);
}
} else if (bf < -1) {
int rightBf = bf(node.right);
if (rightBf <= 0) {
//右子树左边更高 RR 虑到删除时等于0也要左旋
return leftRotate(node);
} else {
//右子树右边更高RL
return rightLeftRotate(node);
}
}
return node;
} 10.2 新增
public void put(int key, Object value){
doPut(root,key,value);
}
//找空位并添加新的节点
private AVLNode doPut(AVLNode node, int key, Object value) {
/*
* 1.找到空位，创建新节点
* 2.key 已存在 更新位置
* 3.继续寻找
**/
//未找到
if (node ==null){
return new AVLNode(key,value);
}
//找到了节点 重新赋值
if(key ==node.key){
node.value=value;
return node;
}
//继续查找
if(key < node.key){
//继续向左，并建立父子关系
node.left= doPut(node.left,key,value);
}else{
//向右找,并建立父子关系
node.right=doPut(node.right,key,value);
}
//更新节点高度
updateHeight(node);
//重新平衡树
return checkBalance(node);
} 10.3 删除
//删除
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
//1. node==null
if (node == null) {
return node;
}
//2.未找到key
if (key < node.key) {
//未找到key，且key小于当前节点key，继续向左
node.left = doRemove(node.left, key);
} else if (key > node.key) {
//向右找
node.right = doRemove(node.right, key);
} else {
//3.找到key
if (node.left == null && node.right == null) {
//3.1 没有子节点
return null;
} else if (node.left != null && node.right == null) {
//3.2 一个子节点（左节点）
node = node.left;
} else if (node.left == null && node.right != null) {
//3.2 一个子节点（右节点）
node = node.right;
} else {
//3.3 两个子节点
//找到他最小的后继节点，右子树向左找到底
AVLNode s=node;
while (s.left!=null){
s=s.left;
}
//s即为后继节点,将节点删除并重新修正右子树
s.right=doRemove(s.right,s.key);
//左子树为s.left,右子树为原删除节点的左子树
s.left=node.left;
node=s;
}
}
//4.更新高度
updateHeight(node);
//5.检查是否失衡
return checkBalance(node);
} 10.4 整体代码
package org.alogorithm.tree.AVLTree;public class AVLTree { static class AVLNode { int key; int height = 1;//高度初始值1 AVLNode left, right; private AVLNode root; Object value; public AVLNode(int key, Object value) { this.key = key; this.value = value; } public AVLNode(int key, AVLNode left, AVLNode right, AVLNode root) { this.key = key; this.left = left; this.right = right; this.root = root; } } //处理节点高度 private int haight(AVLNode node) { return node == null ? 0 : node.height; } //增、删、旋转更新节点高度 //最大高度+1 public void updateHeight(AVLNode treeNode) { treeNode.height = Integer.max(haight(treeNode.left), haight(treeNode.right)) + 1; } /* 平衡因子：一个节点左子树高度-右子树高度所得结果 小于1平衡:(0,1,-1) 大于1不平衡 >1:左边高 <-1：右边高 */ public int bf(AVLNode avlNode) { return haight(avlNode.left) - haight(avlNode.right); } //四种失衡环境 /* LL -失衡节点的 bf >1，即左边更高 -失衡节点的左孩子的bf>=0即左孩子这边也是左边更高或等 一次右旋可以规复平衡 LR -失衡节点的 bf >1，即左边更高 -失衡节点的左孩子的bf<0 即左孩子这边是右边更高 左子节点先左旋，将树修正为LL环境， 然后失衡节点再右旋，规复平衡 RL -失衡节点的 bf <-1，即右边更高 -失衡节点的右孩子的bf>0，即右孩子这边左边更高 右子节点先右旋，将树修正为RR环境， 然后失衡节点再左旋，规复平衡 RR -失衡节点的 bf<-1，即右边更高 -失衡节点的右孩子的bf<=0，即右孩子这边右边更高或等高 一次左旋可以规复平衡*/ //右旋 /** * @Description 返回旋转后的节点 * @Param 必要旋转的节点 **/ private AVLNode rightRotate(AVLNode redNode) { AVLNode yellowNode = redNode.left; /* *黄色节点有右子节点，给右子节点重新找父级节点 *由于二叉搜索树特性，某个节点的左子节点肯定小于 本身，右子节点肯定大于本身 * 故：yelllow的右子节点肯定大于yellow且小于rea， * 所以，gree可以作为red的左子结点 * */ /* AVLNode greeNode = yellowNode.right; redNode.left = greeNode; */ redNode.left = yellowNode.right; yellowNode.right = redNode; //更新高度，赤色和黄色都会改变 updateHeight(redNode); updateHeight(yellowNode); return yellowNode; } //左旋 private AVLNode leftRotate(AVLNode redNode) { //左旋和右旋操作相反 AVLNode yellowNode = redNode.right; //处理yellow的子节点 redNode.right = yellowNode.left; //yellow变为跟，原red比yellow小，为yellow的left yellowNode.left = redNode; updateHeight(redNode); updateHeight(yellowNode); return yellowNode; } /* * LR -失衡节点的 bf >1，即左边更高 -失衡节点的左孩子的bf<0 即左孩子这边是右边更高 左子节点先左旋，将树修正为LL环境， 然后失衡节点再右旋，规复平衡 * */ //先左旋再右旋 private AVLNode leftRightRotate(AVLNode node) { //修正左子结点LL node.left = leftRotate(node.left); return rightRotate(node); } /* * RL -失衡节点的 bf <-1，即右边更高 -失衡节点的右孩子的bf>0，即右孩子这边左边更高 右子节点先右旋，将树修正为RR环境， 然后失衡节点再左旋，规复平衡 * */ //先右旋再左旋 private AVLNode rightLeftRotate(AVLNode node) { //修正右子节点为RR node.right = rightRotate(node.left); return leftRotate(node); } //检查节点是否失衡，重新平衡
private AVLNode checkBalance(AVLNode node) {
if (node == null) {
return null;
}
//获取该节点的平衡因子
int bf = bf(node);
if (bf > 1) {
//左边更高的两种情况根据 左子树平衡因子判定
int leftBf = bf(node.left);
if (leftBf >= 0) {
//左子树左边高 LL 右旋考虑到删除时等于0也应该右旋
return rightRotate(node);
} else {
//左子树右边更高 LR
return leftRightRotate(node);
}
} else if (bf < -1) {
int rightBf = bf(node.right);
if (rightBf <= 0) {
//右子树左边更高 RR 虑到删除时等于0也要左旋
return leftRotate(node);
} else {
//右子树右边更高RL
return rightLeftRotate(node);
}
}
return node;
} AVLNode root; public void put(int key, Object value) { doPut(root, key, value); } //找空位并添加新的节点 private AVLNode doPut(AVLNode node, int key, Object value) { /* * 1.找到空位，创建新节点 * 2.key 已存在 更新位置 * 3.继续寻找 **/ //未找到 if (node == null) { return new AVLNode(key, value); } //找到了节点 重新赋值 if (key == node.key) { node.value = value; return node; } //继续查找 if (key < node.key) { //继续向左，并创建父子关系 node.left = doPut(node.left, key, value); } else { //向右找,并创建父子关系 node.right = doPut(node.right, key, value); } //更新节点高度 updateHeight(node); //重新平衡树 return checkBalance(node); } //删除
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
//1. node==null
if (node == null) {
return node;
}
//2.未找到key
if (key < node.key) {
//未找到key，且key小于当前节点key，继续向左
node.left = doRemove(node.left, key);
} else if (key > node.key) {
//向右找
node.right = doRemove(node.right, key);
} else {
//3.找到key
if (node.left == null && node.right == null) {
//3.1 没有子节点
return null;
} else if (node.left != null && node.right == null) {
//3.2 一个子节点（左节点）
node = node.left;
} else if (node.left == null && node.right != null) {
//3.2 一个子节点（右节点）
node = node.right;
} else {
//3.3 两个子节点
//找到他最小的后继节点，右子树向左找到底
AVLNode s=node;
while (s.left!=null){
s=s.left;
}
//s即为后继节点,将节点删除并重新修正右子树
s.right=doRemove(s.right,s.key);
//左子树为s.left,右子树为原删除节点的左子树
s.left=node.left;
node=s;
}
}
//4.更新高度
updateHeight(node);
//5.检查是否失衡
return checkBalance(node);
}} 11. 红黑树
红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少
红黑树特性
1.所有节点都有两种颜色:红与黑
2.所有 null 视为玄色
3.赤色节点不能相邻
4.根节点是玄色
5.从根到任意一个叶子节点，路径中的玄色节点数一样(玄色完美平衡)
补充：玄色叶子结点一般是成对出现，单独出现肯定不平衡
11.1 node内部类
private static class Node {
int key;
Object value;
Node left;
Node right;
Node parent;//父节点
Color color = RED;//颜色
//是否是左孩子，左未true，右为false
boolean isLeftChild() {
return parent != null && this == parent.left;
}
//获取叔叔节点
Node uncle() {
//有父节点，和父节点的父节点才能有叔叔节点
if (parent == null || parent.parent == null) {
return null;
}
if (parent.isLeftChild()) {
//如果父亲为左子节点则返回右子节点，
return parent.parent.right;
} else {
//如果父亲为右子节点则返回左子节点
return parent.parent.left;
}
}
//获取兄弟节点
Node sibling() {
if(parent==null){
return null;
}
if(this.isLeftChild()){
return parent.right;
}else {
return parent.left;
}
}
} 11.2 判定颜色
//判断颜色
boolean isRed(Node node){
return node!=null&&node.color==RED;
}
boolean isBlack(Node node){
return node==null||node.color==BLACK;
} 11.3 左旋和右旋
//和AVL树的不同
// 右旋1.父(Parent)的处理2.旋转后新根的父子关系方法内处理
void rotateRight(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.left;
Node gree = yellow.right;
//右旋之后换色节点的右子结点变为Pink
yellow.right = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.left = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.left == pink) {
//处理父子关系，yellow代替pink
parent.left = yellow;
} else {
parent.right = yellow;
}
}
void rotateLeft(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.right;
Node gree = yellow.left;
//右旋之后换色节点的右子结点变为Pink
yellow.left = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.right = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.right == pink) {
//处理父子关系，yellow代替pink
parent.right = yellow;
} else {
parent.left = yellow;
}
} 11.4 新增或更新
//新增或更新
void put(int key, Object value) {
Node p = root;
Node parent = null;
while (p != null) {
parent = p;
if (key < p.key) {
//向左找
p = p.left;
} else if (key > p.key) {
p = p.right;
} else {
//更新
p.value = value;
return;
}
}
//插入
Node interestNode = new Node(key, value);
//如果parent为空
if (parent == null) {
root = interestNode;
} else if (key < parent.key) {
parent.left = interestNode;
interestNode.parent = parent;
} else {
parent.right = interestNode;
interestNode.parent = parent;
}
fixRedRed(interestNode);
}
/*
* 1.所有节点都有两种颜色:红与黑
* 2.所有 null 视为黑色
* 3.红色节点不能相邻
* 4.根节点是黑色
* 5.从根到任意一个叶子节点，路径中的黑色节点数一样(黑色完美平衡)
* */
//修复红红不平衡
void fixRedRed(Node x) {
/*
* 插入节点均视为红色
* 插入节点的父亲为红色
* 触发红红相邻
* case 3:叔叔为红色
* case 4:叔叔为黑色
* */
//case 1:插入节点为根节点，将根节点变黑
if (x == root) {
x.color = BLACK;
return;
}
//case 2:插入节点的父亲若为黑色树的红黑性质不变，无需调整
if (isBlack(x.parent)) {
return;
}
Node parent = x.parent;
Node uncle = x.uncle();
Node grandParent = parent.parent;
//插入节点的父亲为红色
if (isRed(uncle)) {
//红红相邻叔叔为红色时（仅通过变色即可）
/*
* 为了保证黑色平衡，连带的叔叔也变为黑色·
* 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色祖父如果变成红色，
* 可能会接着触发红红相邻，因此对将祖父进行递归调整，祖父的父亲变为黑色
* */
parent.color = BLACK;
uncle.color = BLACK;
grandParent.color = RED;
fixRedRed(grandParent);
return;
} else {
//触发红红相邻叔叔为黑色
/*
* 1.父亲为左孩子，插入节点也是左孩子，此时即 LL不平衡（右旋一次）
* 2.父亲为左孩子，插入节点是右孩子，此时即 LR不平衡（父亲左旋，祖父右旋）
* 3.父亲为右孩子，插入节点也是右孩子，此时即 RR不平衡（左旋一次）
* 4.父亲为右孩子，插入节点是左孩子，此时即 RL不平衡（父亲右旋，祖父左旋）
*
*/
if (parent.isLeftChild() && x.isLeftChild()) {
//如果父亲为左子节点，查询节点也为左子结点即为LL（祖父右旋处理）
//父节点变黑（和叔叔节点同为黑色）
parent.color = BLACK;
//祖父节点变红
grandParent.color = RED;
rotateRight(grandParent);
} else if (parent.isLeftChild() && !x.isLeftChild()) {
//parent为左子节点，插入节点为右子节点，LR（父亲左旋，祖父右旋）
rotateLeft(parent);
//插入节点变为黑色
x.color=BLACK;
//祖父变为红色
grandParent.color=RED;
rotateRight(grandParent);
} else if (!parent.isLeftChild()&&!x.isLeftChild()) {
//父节点变黑（和叔叔节点同为黑色）
parent.color = BLACK;
//祖父节点变红
grandParent.color = RED;
rotateLeft(grandParent);
}else if(!parent.isLeftChild()&&x.isLeftChild()){
rotateRight(parent);
//插入节点变为黑色
x.color=BLACK;
//祖父变为红色
grandParent.color=RED;
rotateLeft(grandParent);
}
}
} 11.5 删除
//删除
/*
* 删除
* 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
* */
public void remove(int key) {
Node deleted = find(key);
if (deleted == null) {
return;
}
doRemove(deleted);
}
//检测双黑节点删除
/*
*
* 删除节点和剩下节点都是黑触发双黑，双黑意思是，少了一个黑
* case 3:删除节点或剩余节点的兄弟为红此时两个侄子定为黑
* case 4:删除节点或剩余节点的兄弟、和兄弟孩子都为黑
* case 5:删除节点的兄弟为黑,至少一个红侄子
*
* */
private void fixDoubleBlack(Node x) {
//把case3处理为case4和case5
if (x == root) {
return;
}
Node parent = x.parent;
Node sibling = x.sibling();
if (sibling.color == RED) {
//进入case3
if (x.isLeftChild()) {
//如果是做孩子就进行左旋
rotateLeft(parent);
} else {
//如果是右孩子就进行右旋
rotateRight(parent);
}
//父亲颜色变为红色（父亲变色前肯定为黑色）
parent.color = RED;
//兄弟变为黑色
sibling.color = BLACK;
//此时case3 已经被转换为 case4或者case5
fixDoubleBlack(x);
return;
}
//兄弟为黑
//两个侄子都为黑
if (sibling != null) {
if (isBlack(sibling.left) && isBlack(sibling.right)) {
/*
* case 4:被调整节点的兄弟为黑,两个侄于都为黑
* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
* 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
* 如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
* */
//将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
sibling.color = RED;
if (isRed(parent)) {
// 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
parent.color = BLACK;
} else {
//如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
fixDoubleBlack(parent);
}
} else {
//CASE5 至少有一个侄子不是黑色
/*
*
* case 5:被调整节点的兄弟为黑
* 如果兄弟是左孩子，左侄子是红LL 不平衡
* 如果兄弟是左孩子，右侄子是红LR 不平衡
* 如果兄弟是右孩子，右侄于是红RR 不平衡
* 如果兄弟是右孩子，左侄于是红RL 不平衡
* */
if(sibling.isLeftChild()&&isRed(sibling.left)){
// 如果兄弟是左孩子，左侄子是红LL 不平衡
rotateRight(parent);
//兄弟的做孩子变黑
sibling.left.color=BLACK;
//兄弟变成父亲的颜色
sibling.color= parent.color;
//父亲变黑
parent.color=BLACK;
}else if(sibling.isLeftChild()&&isRed(sibling.right)){
//如果兄弟是左孩子，右侄子是红LR 不平衡
//变色必须在上 否则旋转后会空指针
//兄弟的右孩子变为父节点颜色
sibling.right.color= parent.color;
//父节点变黑
parent.color=BLACK;
rotateLeft(sibling);
rotateRight(parent);
}
}
} else {
fixDoubleBlack(parent);
}
}
private void doRemove(Node deleted) {
Node replaced = findReplaced(deleted);
Node parent = deleted.parent;
if (replaced == null) {
//没有子节点
/* case1:删的是根节点,没有子节点
* 删完了，直接将 root=null
* */
if (deleted == root) {
root = null;
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
if (isBlack(deleted)) {
//复杂处理,先调整平衡再删除
fixDoubleBlack(deleted);
} else {
//红色不处理
}
//删除的不是根节点且没有孩子
if (deleted.isLeftChild()) {
parent.left = null;
} else {
parent.right = null;
}
deleted.parent = null;
}
return;
} else if (replaced.left == null || replaced.right == null) {
//有一个子节点
/* case1:删的是根节点,有一个子节点
* 用剩余节点替换了根节点的 key，Value，根节点孩子=null，颜色保持黑色 不变
* */
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
} else {
//删除的不是根节点但是有一个孩子
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.right = deleted.left = deleted.parent = null;
if (isBlack(deleted) && isBlack(replaced)) {
//如果删除的是黑色剩下的也是黑色，需要复杂处理，先删除再平衡
fixDoubleBlack(replaced);
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
replaced.color = BLACK;
}
}
return;
} else {
//两个子节点
//交换删除节点和删除节点的后几点的key，value，这
// 样被删除节点就只有一个子节点或没有子节点了
int t = deleted.key;
deleted.key = replaced.key;
replaced.key = t;
Object v = deleted.value;
deleted.value = replaced.value;
replaced.value = v;
doRemove(replaced);
return;
}
}
private Node find(int key) {
Node p = root;
while (p != null) {
if (key > p.key) {
//key更大向右找
p = p.right;
} else if (key < p.key) {
//向左找
p = p.left;
} else {
return p;
}
}
return null;
}
//查找删除后的剩余节点
private Node findReplaced(Node deleted) {
if (deleted.left == null & deleted.right == null) {
//没有子节点
return null;
} else if (deleted.left == null) {
return deleted.right;
} else if (deleted.right == null) {
return deleted.left;
} else {
Node s = deleted.right;
while (s != null) {
//右子树的最小值
s = s.left;
}
return s;
}
}
}
11.6 完整代码
package org.alogorithm.tree;import static org.alogorithm.tree.RedBlackTree.Color.BLACK;import static org.alogorithm.tree.RedBlackTree.Color.RED;public class RedBlackTree { enum Color {RED, BLACK} private Node root; private static class Node { int key; Object value; Node left; Node right; Node parent;//父节点 Color color = RED;//颜色 public Node() { } public Node(int key, Object value) { this.key = key; this.value = value; } //是否是左孩子，左未true，右为false boolean isLeftChild() { return parent != null && this == parent.left; } //获取叔叔节点 Node uncle() { //有父节点，和父节点的父节点才气有叔叔节点 if (parent == null || parent.parent == null) { return null; } if (parent.isLeftChild()) { //假如父亲为左子节点则返回右子节点， return parent.parent.right; } else { //假如父亲为右子节点则返回左子节点 return parent.parent.left; } } //获取兄弟节点 Node sibling() { if (parent == null) { return null; } if (this.isLeftChild()) { return parent.right; } else { return parent.left; } } } //判定颜色 boolean isRed(Node node) { return node != null && node.color == RED; } boolean isBlack(Node node) { return node == null || node.color == BLACK; } //和AVL树的不同
// 右旋1.父(Parent)的处理2.旋转后新根的父子关系方法内处理
void rotateRight(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.left;
Node gree = yellow.right;
//右旋之后换色节点的右子结点变为Pink
yellow.right = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.left = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.left == pink) {
//处理父子关系，yellow代替pink
parent.left = yellow;
} else {
parent.right = yellow;
}
}
void rotateLeft(Node pink) {
//获取pink的父级几点
Node parent = pink.parent;
//旋转
Node yellow = pink.right;
Node gree = yellow.left;
//右旋之后换色节点的右子结点变为Pink
yellow.left = pink;
//之前黄色节点的左子结点赋值给pink，完成右旋
pink.right = gree;
if (gree != null) {
//处理父子关系
gree.parent = pink;
}
//处理父子关系
yellow.parent = parent;
pink.parent = yellow;
//如果parent为空则根节点为yellow
if (parent == null) {
root = yellow;
} else if (parent.right == pink) {
//处理父子关系，yellow代替pink
parent.right = yellow;
} else {
parent.left = yellow;
}
} //新增或更新 void put(int key, Object value) { Node p = root; Node parent = null; while (p != null) { parent = p; if (key < p.key) { //向左找 p = p.left; } else if (key > p.key) { p = p.right; } else { //更新 p.value = value; return; } } //插入 Node interestNode = new Node(key, value); //假如parent为空 if (parent == null) { root = interestNode; } else if (key < parent.key) { parent.left = interestNode; interestNode.parent = parent; } else { parent.right = interestNode; interestNode.parent = parent; } fixRedRed(interestNode); } /* * 1.所有节点都有两种颜色:红与黑 * 2.所有 null 视为玄色 * 3.赤色节点不能相邻 * 4.根节点是玄色 * 5.从根到任意一个叶子节点，路径中的玄色节点数一样(玄色完美平衡) * */ //修复红红不平衡 void fixRedRed(Node x) { /* * 插入节点均视为赤色 * 插入节点的父亲为赤色 * 触发红红相邻 * case 3:叔叔为赤色 * case 4:叔叔为玄色 * */ //case 1:插入节点为根节点，将根节点变黑 if (x == root) { x.color = BLACK; return; } //case 2:插入节点的父亲若为玄色树的红黑性质不变，无需调整 if (isBlack(x.parent)) { return; } Node parent = x.parent; Node uncle = x.uncle(); Node grandParent = parent.parent; //插入节点的父亲为赤色 if (isRed(uncle)) { //红红相邻叔叔为赤色时（仅通过变色即可） /* * 为了包管玄色平衡，连带的叔叔也变为玄色· * 祖父假如是玄色不变，会造成这颗子树玄色过多，因此祖父节点变为赤色祖父假如酿成赤色， * 可能会接着触发红红相邻，因此对将祖父举行递归调整，祖父的父亲变为玄色 * */ parent.color = BLACK; uncle.color = BLACK; grandParent.color = RED; fixRedRed(grandParent); return; } else { //触发红红相邻叔叔为玄色 /* * 1.父亲为左孩子，插入节点也是左孩子，此时即 LL不平衡（右旋一次） * 2.父亲为左孩子，插入节点是右孩子，此时即 LR不平衡（父亲左旋，祖父右旋） * 3.父亲为右孩子，插入节点也是右孩子，此时即 RR不平衡（左旋一次） * 4.父亲为右孩子，插入节点是左孩子，此时即 RL不平衡（父亲右旋，祖父左旋） * */ if (parent.isLeftChild() && x.isLeftChild()) { //假如父亲为左子节点，查询节点也为左子结点即为LL（祖父右旋处理） //父节点变黑（和叔叔节点同为玄色） parent.color = BLACK; //祖父节点变红 grandParent.color = RED; rotateRight(grandParent); } else if (parent.isLeftChild() && !x.isLeftChild()) { //parent为左子节点，插入节点为右子节点，LR（父亲左旋，祖父右旋） rotateLeft(parent); //插入节点变为玄色 x.color = BLACK; //祖父变为赤色 grandParent.color = RED; rotateRight(grandParent); } else if (!parent.isLeftChild() && !x.isLeftChild()) { //父节点变黑（和叔叔节点同为玄色） parent.color = BLACK; //祖父节点变红 grandParent.color = RED; rotateLeft(grandParent); } else if (!parent.isLeftChild() && x.isLeftChild()) { rotateRight(parent); //插入节点变为玄色 x.color = BLACK; //祖父变为赤色 grandParent.color = RED; rotateLeft(grandParent); } } } //删除
/*
* 删除
* 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
* */
public void remove(int key) {
Node deleted = find(key);
if (deleted == null) {
return;
}
doRemove(deleted);
}
//检测双黑节点删除
/*
*
* 删除节点和剩下节点都是黑触发双黑，双黑意思是，少了一个黑
* case 3:删除节点或剩余节点的兄弟为红此时两个侄子定为黑
* case 4:删除节点或剩余节点的兄弟、和兄弟孩子都为黑
* case 5:删除节点的兄弟为黑,至少一个红侄子
*
* */
private void fixDoubleBlack(Node x) {
//把case3处理为case4和case5
if (x == root) {
return;
}
Node parent = x.parent;
Node sibling = x.sibling();
if (sibling.color == RED) {
//进入case3
if (x.isLeftChild()) {
//如果是做孩子就进行左旋
rotateLeft(parent);
} else {
//如果是右孩子就进行右旋
rotateRight(parent);
}
//父亲颜色变为红色（父亲变色前肯定为黑色）
parent.color = RED;
//兄弟变为黑色
sibling.color = BLACK;
//此时case3 已经被转换为 case4或者case5
fixDoubleBlack(x);
return;
}
//兄弟为黑
//两个侄子都为黑
if (sibling != null) {
if (isBlack(sibling.left) && isBlack(sibling.right)) {
/*
* case 4:被调整节点的兄弟为黑,两个侄于都为黑
* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
* 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
* 如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
* */
//将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1
sibling.color = RED;
if (isRed(parent)) {
// 如果父亲是红,则需将父亲变为黑，避免红红，此时路径黑节点数目不变
parent.color = BLACK;
} else {
//如果父亲是黑,说明这条路径则少了一个黑，再次让父节点触发双黑
fixDoubleBlack(parent);
}
} else {
//CASE5 至少有一个侄子不是黑色
/*
*
* case 5:被调整节点的兄弟为黑
* 如果兄弟是左孩子，左侄子是红LL 不平衡
* 如果兄弟是左孩子，右侄子是红LR 不平衡
* 如果兄弟是右孩子，右侄于是红RR 不平衡
* 如果兄弟是右孩子，左侄于是红RL 不平衡
* */
if(sibling.isLeftChild()&&isRed(sibling.left)){
// 如果兄弟是左孩子，左侄子是红LL 不平衡
rotateRight(parent);
//兄弟的做孩子变黑
sibling.left.color=BLACK;
//兄弟变成父亲的颜色
sibling.color= parent.color;
//父亲变黑
parent.color=BLACK;
}else if(sibling.isLeftChild()&&isRed(sibling.right)){
//如果兄弟是左孩子，右侄子是红LR 不平衡
//变色必须在上 否则旋转后会空指针
//兄弟的右孩子变为父节点颜色
sibling.right.color= parent.color;
//父节点变黑
parent.color=BLACK;
rotateLeft(sibling);
rotateRight(parent);
}
}
} else {
fixDoubleBlack(parent);
}
}
private void doRemove(Node deleted) {
Node replaced = findReplaced(deleted);
Node parent = deleted.parent;
if (replaced == null) {
//没有子节点
/* case1:删的是根节点,没有子节点
* 删完了，直接将 root=null
* */
if (deleted == root) {
root = null;
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
if (isBlack(deleted)) {
//复杂处理,先调整平衡再删除
fixDoubleBlack(deleted);
} else {
//红色不处理
}
//删除的不是根节点且没有孩子
if (deleted.isLeftChild()) {
parent.left = null;
} else {
parent.right = null;
}
deleted.parent = null;
}
return;
} else if (replaced.left == null || replaced.right == null) {
//有一个子节点
/* case1:删的是根节点,有一个子节点
* 用剩余节点替换了根节点的 key，Value，根节点孩子=null，颜色保持黑色 不变
* */
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
} else {
//删除的不是根节点但是有一个孩子
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.right = deleted.left = deleted.parent = null;
if (isBlack(deleted) && isBlack(replaced)) {
//如果删除的是黑色剩下的也是黑色，需要复杂处理，先删除再平衡
fixDoubleBlack(replaced);
} else {
/*
* Case2:删的是黑，剩下的是红剩下这个红节点变黑
* */
replaced.color = BLACK;
}
}
return;
} else {
//两个子节点
//交换删除节点和删除节点的后几点的key，value，这
// 样被删除节点就只有一个子节点或没有子节点了
int t = deleted.key;
deleted.key = replaced.key;
replaced.key = t;
Object v = deleted.value;
deleted.value = replaced.value;
replaced.value = v;
doRemove(replaced);
return;
}
}
private Node find(int key) {
Node p = root;
while (p != null) {
if (key > p.key) {
//key更大向右找
p = p.right;
} else if (key < p.key) {
//向左找
p = p.left;
} else {
return p;
}
}
return null;
}
//查找删除后的剩余节点
private Node findReplaced(Node deleted) {
if (deleted.left == null & deleted.right == null) {
//没有子节点
return null;
} else if (deleted.left == null) {
return deleted.right;
} else if (deleted.right == null) {
return deleted.left;
} else {
Node s = deleted.right;
while (s != null) {
//右子树的最小值
s = s.left;
}
return s;
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]