咸阳营销型网站开发,广州个人网站备案要多久,怎么优化关键词,新公司注册工商核名系统1.了解数据结构和算法
1.1 二分查找 二分查找#xff08;Binary Search#xff09;是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两半#xff0c;然后比较目标值与中间元素的大小关系#xff0c;从而确定应该在左半部分还是右半部分继续查找。这个…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));//结果0System.out.println(binarySearch( arr,22));//结果1System.out.println(binarySearch( arr,33));//结果2System.out.println(binarySearch( arr,55));//结果3System.out.println(binarySearch( arr,88));//结果4System.out.println(binarySearch( arr,99));//结果5System.out.println(binarySearch( arr,117));//结果6System.out.println(binarySearch( arr,366));//结果7System.out.println(binarySearch( arr,445));//结果8System.out.println(binarySearch( arr,999));//结果9System.out.println(binarySearch( arr,1111));//结果-1System.out.println(binarySearch( arr,-1));//结果-1}/*** Description* Author LY* Param [arr, target] 待查找升序数组查找的值* return int 找到返回索引找不到返回-1* Date 2023/12/8 16:38**/public static int binarySearch(int[] arr, int target){//设置 i跟j 初始值int i0;int j arr.length-1;//如果ij则表示并未找到该值while (ij){int m(ij)1;
// int m(ij)/2;if (targetarr[m]){//目标在左侧jm-1;}else if(targetarr[m]){//目标在右侧im1;}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 [arr, target] 待查找升序数组查找的值* 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 (ij){while (i j) {//改动2int m (i j) 1;if (target arr[m]) {
// j m - 1;j m; //改动3} else if (arr[m] 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 [arr, target] 待查找数组可以不是升序查找的值* 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[i]target){indexi;break;}}return index;} 1.3 衡量算法第一因素 时间复杂度算法在最坏情况下所需的基本操作次数与问题规模之间的关系。 1.3.1 对比 假设每行代码执行时间都为t数据为n个且是最差的执行情况执行最多次 二分查找 二分查找执行时间为5L4 既5*floor(log_2(x)1)4执行语句执行次数int i0;1int jarr.length-1;1return -1;1循环次数为floor(log_2(n))1之后使用L代替ij;L1int m (ij)1;Lartgetarr[m]Larr[m]artgetLim1;L 线性查找 线性查找执行时间为3x3执行语句执行次数int i0;1ia.length;x1i;xarr[i]targetxreturn -1;1 对比工具Desmos | 图形计算器 对比结果 随着数据规模增加线性查找执行时间会逐渐超过二分查找。 1.3.2 时间复杂度 计算机科学中时间复杂度是用来衡量一个算法的执行随着数据规模增大而增长的时间成本不依赖与环境因素。 时间复杂度的标识 假设要出炉的数据规模是n代码总执行行数用f(n)来表示 线性查找算法的函数f(n)3*n3。 二分查找算法函数f(n)5*floor(log_2(x)1)4。 为了简化f(n)应当抓住主要矛盾找到一个变化趋势与之相近的表示法。 1.3.3 渐进上界 渐进上界代表算法执行的最差情况 以线性查找法为例 f(n)3*n3 g(n)n 取c4在n03后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)) 1.3.4 常见大O表示法 按时间复杂度从低到高 1黑色横线O(1)常量时间复杂度意味着算法时间并不随数据规模而变化。 2绿色O(log(n))对数时间复杂度。 3蓝色O(n)线性时间复杂度算法时间与规模与数据规模成正比。 4橙色O(n*log(n))拟线性时间复杂度。 5红色O(n^2)平方时间复杂度。 6黑色向上O(2^n)指数时间复杂度。 7O(n!)这种时间复杂度非常大通常意味着随着输入规模 n 的增加算法所需的时间会呈指数级增长。因此具有 O(n!) 时间复杂度的算法在实际应用中往往是不可行的因为它们需要耗费大量的计算资源和时间。 1.4 衡量算法第二因素 空间复杂度与时间复杂度类似一般也用O衡量一个算法随着数据规模增大而增长的额外空间成本。 1.3.1 对比 以二分查找为例 二分查找占用空间为4字节执行语句执行次数int i0;4字节int jarr.length-1;4字节int m (ij)1;4字节二分查找占用空间复杂度为O(1) 性能分析 时间复杂度 最坏情况O(log(n))。 最好情况待查找元素在数组中央O(1)。 空间复杂度需要常熟个数指针ijm额外占用空间是O(1)。 1.5 二分查找改进 在之前的二分查找算法中如果数据在数组的最左侧只需要执行L次 if 就可以了但是如果数组在最右侧那么需要执行L次 if 以及L次 else if所以二分查找向左寻找元素比向右寻找元素效率要高。 1左闭右开的区间i指向的可能是目标而j指向的不是目标。 2不在循环内找出等范围内只剩下i时退出循环再循环外比较arr[i]与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));//结果4System.out.println(binarySearchLeftMost1(arr, 999));//结果9System.out.println(binarySearchLeftMost1(arr, 998));//结果-1}/*** return int 找到相同元素返回返回最左侧查找元素索引找不到返回-1* Description 二分查找LeftMost* Author LY* Param [arr, target] 待查找升序数组查找的值* 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[m]) {j m - 1;} else if (arr[m] target) {i m 1;} else {
// return m; 查找到之后记录下来candidatem;jm-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));//结果6System.out.println(binarySearchRightMost1(arr, 999));//结果9System.out.println(binarySearchRightMost1(arr, 998));//结果-1}/*** return int 找到相同元素返回返回最右侧侧查找元素索引找不到返回-1* Description 二分查找RightMost* Author LY* Param [arr, target] 待查找升序数组查找的值* 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[m]) {j m - 1;} else if (arr[m] target) {i m 1;} else {
// return m; 查找到之后记录下来candidatem;i m 1;}}return candidate;} 1.6.3 优化 将leftMost优化后可以在未找到目标值的情况下返回大于等于目标值最靠左的一个索引。 /*** return int 找到相同元素返回返回最左侧查找元素索引找不到返回i* Description 二分查找LeftMost* Author LY* Param [arr, target] 待查找升序数组查找的值* 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[m]) {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的数组结构包含markword8字节class指针4字节数组大小4字节。 1数组本身是一个对象。每个Java对象都有一个对象头Object Header其中包含了类指针和Mark Word等信息。。Mark Word是HotSpot虚拟机设计的一种数据结构用于存储对象的运行时元数据。 2Mark 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} 该数组包含内容包括 单位字节 markword8class指针4数组大小41424344454字节对齐4 大小为8444*44440字节 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[i]);}*/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 IterableInteger {private int size 0;//逻辑大小private int capacity 8;//容量private int[] array {};public void addLast(int value) {/*array[size] value;size;*/add(size, value);}public void add(int index, int value) {//容量不够扩容checkAndGrow();/** param1 要copy的数组* param1 copy的起始位置* param1 要存放数组* param1 要copy的个数* 这个方法表示要将array从index开始copy到index1的位置* copy的个数是数组的大小-indexindex向后的元素* */if (index 0 index size) {System.arraycopy(array, index, array, index 1, size - index);}//合并add方法array[index] value;size;}private void checkAndGrow() {if (size0){arraynew int[capacity];}else if (size capacity) {capacitycapacity1;int[] newArray new int[capacity];//赋值数组System.arraycopy(array,0,newArray,0,size);arraynewArray;}}//查询元素public int get(int index) {return array[index];}//遍历数组 1//查询元素public void foreach(ConsumerInteger consumer) {for (int i 0; i size; i) {//System.out.println(array[i]);//提供array[i]不需要返回值consumer.accept(array[i]);}}//遍历数组2 迭代器模式Overridepublic IteratorInteger iterator() {//匿名内部类return new IteratorInteger() {int i 0;Overridepublic boolean hasNext() {//有没有下一个元素return i size;}Overridepublic Integer next() {//返回当前元素并将指针移向下一个元素return array[i];}};}//遍历数组3 数据流public IntStream stream() {return IntStream.of(Arrays.copyOfRange(array, 0, size));}public int remove(int index) {int removeed array[index];System.arraycopy(array, index 1, array, index, size - index - 1);size--;return removeed;}}
} 2.4 二维数组 1二维数组占32个字节其中array[0]array[1]array[2]元素分别保存了指向三个一维数组的引用。 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[rows][columns];long ijStar System.currentTimeMillis();ij(arr, rows, columns);long ijEnd System.currentTimeMillis();System.out.println(ij执行时间为(ijEnd-ijStar));//ij执行时间为10long 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[i][j];}}System.out.println(sumji);}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[i][j];}}System.out.println(sumij);}
}在计算机中内存是分块存储的。每个内存块称为一个页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 哨兵节点 链表内还有一种特殊的节点成为哨兵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);//使用Consumerwhile实现singLinkList.consumerLoop1(value - System.out.println(value while,));System.out.println(----------------------------------------);singLinkList.addLast(99);//尾部添加一个元素singLinkList.addLast(100);//尾部添加一个元素//使用Consumerfor实现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 IterableInteger {// 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属性为新的Nodelast.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(ConsumerInteger consumer, Node point) {if (point ! null) {consumer.accept(point.value); // 先输出当前节点的值recursionLoop(consumer, point.next); // 再递归处理下一个节点}}//迭代器遍历Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node point head;Overridepublic boolean hasNext() {return point ! null;}Overridepublic Integer next() {int value point.value;point point.next;return value;}};}//循环遍历 forpublic void consumerLoop2(ConsumerInteger consumer) {for (Node point head; point ! null; point point.next) {consumer.accept(point.value);}}//循环遍历 whilepublic void consumerLoop1(ConsumerInteger 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 1Node内部类可以添加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);//使用Consumerwhile实现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(----------------------------------------);//使用Consumerfor实现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 IterableInteger {// head指针Node headnew 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(ConsumerInteger consumer, Node point) {if (point ! null) {consumer.accept(point.value); // 先输出当前节点的值recursionLoop(consumer, point.next); // 再递归处理下一个节点}}//迭代器遍历Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node point head.next;Overridepublic boolean hasNext() {return point ! null;}Overridepublic Integer next() {int value point.value;point point.next;return value;}};}//循环遍历 forpublic void consumerLoop2(ConsumerInteger consumer) {for (Node point head.next; point ! null; point point.next) {consumer.accept(point.value);}}//循环遍历 whilepublic void consumerLoop1(ConsumerInteger 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 IterableInteger{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(nodehead){IndexOutOfBoundsException(head.prev,当前链表为空);}Node prevNode node.prev;//上一个节点prevNode.nexttail;//上一个节点的next指向为哨兵tail.prevprevNode;//尾哨兵的prev的像一个节点为prevNode}public void addLast(int value){Node lastNode tail.prev;//原本最后一个节点Node node new Node(lastNode, value, tail);lastNode.nextnode;//原本节点下一个节点指向当前节点tail.prevnode;//尾哨兵上一个节点设置为当前节点}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指针指向nextNodenextNode.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);}}Overridepublic IteratorInteger iterator() {return new IteratorInteger() {//设置起始指针Node p head.next;Overridepublic boolean hasNext() {return p! tail;}Overridepublic Integer next() {int valuep.value;pp.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 QueueE extends IterableE {/*** Description 向队尾插入值* Author LY* Param [value] 待插入的值* 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 LinkedListQueueE implements QueueE, IterableE {public static void main(String[] args) {LinkedListQueueIntegerqueuenew LinkedListQueueInteger(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();}Overridepublic 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;}Overridepublic E pool() {if(this.isEmpty()){return null;}NodeE firsthead.next;head.nextfirst.next;//如果是最后一个节点if(firsttail){tailhead;}size--;return first.value;}Overridepublic E peek() {if(this.isEmpty()){return null;}return head.next.value;}Overridepublic boolean isEmpty() {return tailhead;}Overridepublic boolean isFull() {return sizecapacity;}//节点类private static class NodeE {E value;NodeE next;public Node(E value, NodeE next) {this.next next;this.value value;}}Overridepublic Iterator iterator() {return new IteratorE() {NodeEphead.next;Overridepublic boolean hasNext() {return p.next!head;}Overridepublic E next() {E valuep.value;return value;}};}NodeE head new NodeE(null, null);NodeE tail head;//当前大小private Integer size0;//容量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 ArrayQueue1E implements QueueE{public static void main(String[] args) {ArrayQueue1Integerqueuenew ArrayQueue1Integer(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 head0;private int tail0;//抑制警告产生SuppressWarnings(all)public ArrayQueue1(int capacity) {this.arr (E[]) new Object[capacity1];}Overridepublic boolean offer(E value) {if(isFull()){return false;}arr[tail]value;//防止当前元素时最后一个tail(tail1)% arr.length;return true;}Overridepublic E pool() {if(isEmpty()){return null;}E e arr[head];head(head1)%arr.length;return e;}Overridepublic E peek() {if(isEmpty()){return null;}return arr[head];}Overridepublic boolean isEmpty() {return tailhead;}Overridepublic boolean isFull() {return (tail1)%arr.lengthhead;}Overridepublic IteratorE iterator() {return new IteratorE() {int phead;Overridepublic boolean hasNext() {return p!tail;}Overridepublic E next() {E e arr[p];p(p1)% arr.length;return e;}};}}4.3.2 环形数组实现2 增加一个size属性保存全部元素个数新建数组时大小判定满和空添加元素移除元素做出相应修改。迭代时也应该增加一个count属性。
public class ArrayQueue2E implements QueueE{public static void main(String[] args) {ArrayQueue2Integer queuenew ArrayQueue2Integer(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 head0;private int tail0;//元素个数private int size0;//抑制警告产生SuppressWarnings(all)public ArrayQueue2(int capacity) {this.arr (E[]) new Object[capacity];}Overridepublic boolean offer(E value) {if(isFull()){return false;}arr[tail]value;//防止当前元素时最后一个tail(tail1)% arr.length;size;return true;}Overridepublic E pool() {if(isEmpty()){return null;}E e arr[head];head(head1)%arr.length;size--;return e;}Overridepublic E peek() {if(isEmpty()){return null;}return arr[head];}Overridepublic boolean isEmpty() {return size0;}Overridepublic boolean isFull() {return sizearr.length;}Overridepublic IteratorE iterator() {return new IteratorE() {int phead;int count0;Overridepublic boolean hasNext() {return countsize;}Overridepublic E next() {E e arr[p];p(p1)% arr.length;count;return e;}};}
} 4.3.3 环形数组实现3 基于方式1做出优化head和tail一直递增使用时在进行计算。 当索引超出int最大值会出现索引为负数的问题。 需要单独处理(int) Integer.toUnsignedLong()。 方法1
public class ArrayQueue3E implements QueueE{public static void main(String[] args) {ArrayQueue3Integer queuenew ArrayQueue3Integer(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 head0;private int tail0;//抑制警告产生SuppressWarnings(all)public ArrayQueue3(int capacity) {this.arr (E[]) new Object[capacity];}Overridepublic boolean offer(E value) {if(isFull()){return false;}arr[(int) Integer.toUnsignedLong(tail% arr.length)]value;//防止当前元素时最后一个tail;return true;}Overridepublic E pool() {if(isEmpty()){return null;}E e arr[(int) Integer.toUnsignedLong(head% arr.length)];head;return e;}Overridepublic E peek() {if(isEmpty()){return null;}return arr[(int) Integer.toUnsignedLong(head%arr.length)];}Overridepublic boolean isEmpty() {return tailhead;}Overridepublic boolean isFull() {return tail-head arr.length;}Overridepublic IteratorE iterator() {return new IteratorE() {int phead;Overridepublic boolean hasNext() {return p!tail;}Overridepublic 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_2E implements QueueE{public static void main(String[] args) {ArrayQueue3_2Integer queuenew ArrayQueue3_2Integer(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 head0;private int tail0;//抑制警告产生SuppressWarnings(all)public ArrayQueue3_2(int capacity) {//方式1/*if((capacitycapacity-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|capacity1;capacity|capacity2;capacity|capacity4;capacity|capacity8;capacity|capacity16;capacity1;this.arr (E[]) new Object[capacity];}Overridepublic boolean offer(E value) {if(isFull()){return false;}arr[tail (arr.length-1)]value;//防止当前元素时最后一个tail;return true;}Overridepublic E pool() {if(isEmpty()){return null;}E e arr[head(arr.length-1)];head;return e;}Overridepublic E peek() {if(isEmpty()){return null;}return arr[head(arr.length-1)];}Overridepublic boolean isEmpty() {return tailhead;}Overridepublic boolean isFull() {return tail-head arr.length;}Overridepublic IteratorE iterator() {return new IteratorE() {int phead;Overridepublic boolean hasNext() {return p!tail;}Overridepublic E next() {E e arr[p(arr.length-1)];p;return e;}};}
} 5.基础数据结构-栈
5.1 相关概念 数据结构栈Stack是一种特殊的线性表 栈顶Top 栈顶是指栈中最靠近“出口”或“操作端”的那个位置。新元素总是被压入push到栈顶当进行弹出pop操作时也是从栈顶移除元素。因此栈顶始终指向当前栈内的最后一个加入的元素。 栈底Bottom 栈底则是指栈中固定不变的那个位置通常是在创建栈时初始化的第一个位置也可以理解为栈中最早加入的那些元素所在的位置。在实际操作中栈底不发生变化除非整个栈为空或者重新初始化。 后进先出Last In First Out, LIFO 最后被压入push到栈中的元素将是第一个被弹出pop的元素。这意味着在没有其他操作的情况下栈顶元素总是最后被添加的那一个。 受限的插入和删除操作 栈只允许在栈顶进行插入称为“压入”或push操作和删除称为“弹出”或pop操作。不能直接访问或修改栈内的中间元素。 5.2 接口 public interface StockE extends IterableE {/*** Description 向栈压入元素* Author LY* Param [value] 待压入的值* 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 LinkedListStockE implements StockE{public static void main(String[] args) {LinkedListStockIntegerstocknew 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 capatityInteger.MAX_VALUE;//元素个数private int size0;private Node headnew Node(null,null);public LinkedListStock() {}public LinkedListStock(int capatity) {this.capatity capatity;}static class NodeE{E value;NodeE next;public Node(E value, NodeE next) {this.value value;this.next next;}}Overridepublic boolean push(E value) {if(isFull()){return false;}Node node new Node(value, head.next);head.nextnode;size;return true;}Overridepublic E pop() {if(isEmpty()){return null;}NodeE first head.next;head.nextfirst.next;size--;return first.value;}Overridepublic E peek() {if(isEmpty()){return null;}NodeE first head.next;return first.value;}Overridepublic boolean isEmpty() {return size0;}Overridepublic boolean isFull() {return sizecapatity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE phead;Overridepublic boolean hasNext() {return p!null;}Overridepublic E next() {E value p.value;pp.next;return value;}};}
} 5.4 数组实现 public class ArrayStockE implements StockE{public static void main(String[] args) {ArrayStockInteger stocknew 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 capatityInteger.MAX_VALUE;public ArrayStock() {}SuppressWarnings(all)public ArrayStock(int capatity) {this.arr (E[]) new Object[capatity];this.capatitycapatity;}Overridepublic boolean push(E value) {if(isFull()){return false;}/* arr[top]value;top;*/arr[top]value;return true;}Overridepublic E pop() {if(isEmpty()){return null;}E e arr[--top];return e;}Overridepublic E peek() {if(isEmpty()){return null;}return arr[top-1];}Overridepublic boolean isEmpty() {return top0;}Overridepublic boolean isFull() {return topcapatity;}Overridepublic IteratorE iterator() {return new IteratorE() {int ptop;Overridepublic boolean hasNext() {return p0;}Overridepublic 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 LinkedListDequeE implements DequeE {public static void main(String[] args) {LinkedListDequeIntegerlinkedListDequenew 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;NodeE sentinelnew NodeE(null,null,null);public LinkedListDeque(int capacity) {this.capacity capacity;sentinel.nextsentinel;sentinel.prevsentinel;}static class NodeE{Node prev;E value;Node next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}Overridepublic boolean offerFirst(E e) {if(isFull()){return false;}//上一个节点是哨兵下一个节点是哨兵.nextNode oldFirst sentinel.next;//新的节点NodeE addNodenew NodeE(sentinel,e,oldFirst);//旧节点修改prev指针oldFirst.prevaddNode;//修改哨兵next指针sentinel.nextaddNode;//增加容量size;return true;}Overridepublic boolean offerLast(E e) {if(isFull()){return false;}//旧的最后一个节点Node oldLast sentinel.prev;//新的节点Node addNodenew Node(oldLast,e,sentinel);//旧节点修改next指针oldLast.nextaddNode;//修改哨兵prev指针sentinel.prevaddNode;size;return true;}Overridepublic E poolFirst() {if(isEmpty()){return null;}//需要出队列的节点NodeE poolNodesentinel.next;//移除节点的下一个节点NodeEnextNodepoolNode.next;//修改下一个节点.prev指针nextNode.prevsentinel;//修改哨兵.next指针sentinel.nextnextNode;size--;return poolNode.value;}Overridepublic E poolLast() {if(isEmpty()){return null;}//需要出队列的节点NodeE poolNodesentinel.prev;//移除节点的上一个节点NodeEprevNodepoolNode.prev;//修改上一个节点.next指针prevNode.nextsentinel;//修改哨兵.prev指针sentinel.prevprevNode;size--;return poolNode.value;}Overridepublic E peekFirst() {if(isEmpty()){return null;}return (E) sentinel.next.value;}Overridepublic E peekLast() {if(isEmpty()){return null;}return (E) sentinel.prev.value;}Overridepublic boolean isEmpty() {return size0;}Overridepublic boolean isFull() {return sizecapacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE piontsentinel.next;Overridepublic boolean hasNext() {return piont!sentinel;}Overridepublic E next() {E val piont.value;piontpiont.next;return val;}};}
}6.2.3 数组实现 public class ArrayDeque1E implements DequeE{public static void main(String[] args) {ArrayDeque1Integer arrayDeque1new 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 [capacity1];}Override/** 先head-1再添加元素* */public boolean offerFirst(E e) {if(isFull()){return false;}head dec(head, array.length);array[head]e;return true;}Override/** 添加元素后tail1* */public boolean offerLast(E e) {if(isFull()){return false;}array[tail]e;tail inc(tail, array.length);return true;}Override/** 先获取值再head转换为合法索引* */public E poolFirst() {if(isEmpty()){return null;}E e array[head];//取消引用自动释放内存array[head]null;headinc(head,array.length);return e;}Override/** 先tail-- 再获取元素转换为合法索引* */public E poolLast() {if(isEmpty()){return null;}taildec(tail,array.length);E e array[tail];//取消引用自动释放内存array[tail]null;return e;}Overridepublic E peekFirst() {if(isEmpty()){return null;}return array[head];}/** 获取 tail-1位置的元素* */Overridepublic E peekLast() {return array[dec(tail-1,array.length)];}Override/** 头尾指向同一个位置即为空* */public boolean isEmpty() {return headtail;}Override/** head ~ tail 数组.length-1* tailhead tail-head 数组.length-1* tailhead head-tail1* */public boolean isFull() {if(head tail){return tail-headarray.length-1;}else if(head tail){return head-tail1;}return false;}Overridepublic IteratorE iterator() {return new IteratorE() {int poinhead;Overridepublic boolean hasNext() {return poin!tail;}Overridepublic E next() {E e array[poin];poin inc(poin 1, array.length);return e;}};}/** 索引之后越界恢复成0* */static int inc(int i, int length){if(ilength){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 PriorityQueueE extends Priority implements QueueE {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 priorityQueuenew 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;}}Getterstatic Priority[] array;private static int size0;public PriorityQueue(int capacity) {array new Priority[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[size] value;size;return true;}Overridepublic E pool() {if(isEmpty()){return null;}int maxIndex getMaxIndex();Priority priority array[maxIndex];remove(maxIndex);return (E) priority;}//移除元素private void remove(int maxIndex) {if(maxIndexsize-1){//不是最后一个元素System.arraycopy(array,maxIndex1,array,maxIndex,size-1-maxIndex);}size--;}private static int getMaxIndex(){int max 0;for (int i 0; i array.length; i) {if (array[max].priority array[i].priority) {max i;}}return max;}Overridepublic E peek() {if(isEmpty()){return null;}int max 0;for (int i 0; i size; i) {if (array[max].priority array[i].priority) {max i;}}Priority priority array[max];return (E) priority;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size array.length;}Overridepublic IteratorE iterator() {return new IteratorE() {private int p;Overridepublic boolean hasNext() {return p array.length;}Overridepublic E next() {Priority priority array[p];p;return (E) priority;}};}
}6.3.3 有序数组实现 基于有序数组的优先级队列 插入元素 插入新元素需要保持数组的有序性因此在插入过程中可能需要移动部分或全部已存在的元素以腾出位置给新元素时间复杂度通常是O(n)。 由于数组本身是有序的可以通过二分查找快速定位到插入点但是插入后的调整仍然涉及元素移动。 删除最高优先级元素 可以直接访问并删除数组的第一个元素假设是最小元素时间复杂度为O(1)。 删除后如果需要维持有序可能需要将最后一个元素移动到被删除元素的位置或者使用某种方法来“填补”空缺总体上删除操作的时间复杂度也是O(n)。 优势 查找最高优先级元素的时间复杂度低为O(1)。 如果插入不是非常频繁且数组大小相对稳定那么其效率可能会较高因为查询和删除最小元素高效。 劣势 插入和删除元素的成本高尤其是当数组较大时频繁的移动操作会显著降低性能。 //基于有序数组的实现
public class PriorityQueue3E extends Priority implements QueueE {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 priorityQueuenew 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;}}Getterstatic Priority[] array;private static int size;public PriorityQueue3(int capacity) {array new Priority[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}insert( value);size;return true;}private void insert(E value) {int isize-1;while (i0 array[i].priority value.priority){//优先级大于入参向上移动array[i1]array[i];i--;}//在比他小的索引后面插入元素array[i1]value;}Overridepublic E pool() {if(isEmpty()){return null;}E priority (E) array[size - 1];array[--size]null;return (priority) ;}Overridepublic E peek() {if(isEmpty()){return null;}return (E) array[size-1];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size array.length;}Overridepublic IteratorE iterator() {return new IteratorE() {private int p;Overridepublic boolean hasNext() {return p array.length;}Overridepublic E next() {Priority priority array[p];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。 已知父节点求子节点为2i2i1。 请注意这些规则适用于采用数组实现的完全二叉树和几乎完全二叉树等特定场景下的节点关系查找。对于其他类型的树或者非完全二叉树可能需要额外的数据结构或不同的逻辑来维护父子节点之间的关系。例如在链表形式的树结构中父节点会直接持有指向其子节点的指针因此不需要通过计算索引来定位子节点。 6.3.4.4 基于大顶堆实现 //基于有序数组的实现
public class PriorityQueue4E extends Priority implements QueueE {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;}}Getterstatic Priority[] array;private static int size;public PriorityQueue4(int capacity) {array new Priority[capacity];}/** 1.入队新元素加入到数组末尾索引child* 2.不断比较新元素与父节点的优先级。* 如果优先级低于新节点则向下移动并寻找下一个paraent* 直至父元素优先级跟高或者child0为止* */Overridepublic boolean offer(E value) {if (isFull()) {return false;}if(isEmpty()){array[0]value;}int child size;int parent (child - 1) / 2;//新元素和父元素优先级对比while (value.priority array[parent].priority child ! 0) {array[child] array[parent];//子节点指向父节点父节点指向原本的父节点的父节点child parent;parent (child - 1) / 2;}array[child] value;return true;}/** 1.由于移除最后一个元素效率比较高* 故应将第一个优先级最高的元素与最后一个元素互换。* 2.将堆顶元素与两个子元素比较与较大的那个更换* 直至该节点为最后一个节点或者子节点都小于该节点** */Overridepublic E pool() {if (isEmpty()) return null;swap(0, size - 1);size--;//保存优先级最大的元素Priority p array[size];//置空垃圾回收array[size] null;//堆顶下潜down(0);return (E) p;}private void swap(int i, int j) {Priority t array[i];array[i] array[j];array[j] t;}private void down(int parent) {int left parent * 2 1;int right left 1;int bigChild parent;//比较左侧元素与父元素if (left size array[left].priority array[bigChild].priority) bigChild left;//比较右侧元素与父元素if (right size array[right].priority array[bigChild].priority) bigChild right;//交换较大的元素if (bigChild ! parent) {swap(bigChild, parent);//以最大的子元素节点索引为参数继续执行下潜操作down(bigChild);}}Overridepublic E peek() {if(isEmpty())return null;return (E) array[0];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size array.length;}Overridepublic IteratorE iterator() {return new IteratorE() {private int p;Overridepublic boolean hasNext() {return p array.length;}Overridepublic E next() {Priority priority array[p];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[10];private int tail 0;private int size 0;ReentrantLock reentrantLock new ReentrantLock();Condition tailWaitsreentrantLock.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[tail] s;if(tail array.length){tail0;}size;} finally {//解锁必须执行reentrantLock.unlock();}}public boolean isFull(){return sizearray.length;}public String toString() {return Arrays.toString(array);}
}6.4.1 单锁实现 /** 用锁保证线程安全。* 条件变量让pool或者offer线程进入等待而不是循环尝试占用cpu* */
public class BlockingQueue1E implements BlockingQueueE {public static void main(String[] args) {BlockingQueue1String blockingQueue1new 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[capacity];}Overridepublic void offer(E e) throws InterruptedException {lock.lockInterruptibly();try {//防止虚假唤醒while (isFull()) {tailWaits.await();}array[tail] e;if (tail array.length) {tail 0;}size;//唤醒等待非空的线程headWaits.signal();} finally {lock.unlock();}}/** 优化后的offer设置等待时间超出则抛出异常* */Overridepublic 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[tail] e;if (tail array.length) {tail 0;}size;//唤醒等待非空的线程headWaits.signal();return true;} finally {lock.unlock();}}Overridepublic E pool() throws InterruptedException {lock.lockInterruptibly();try {while (isFull()) {headWaits.await();}E e array[head];array[head] 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命令可以获取进程idjstack进程id 可以检测死锁等问题。 可以将两个锁列为平级而不是嵌套即可解决。
/** 单锁实现方式offer和pool是互相影响的* 但是head指针和tail执行两者并不互相影响* 会降低运行效率offer和pool不应该互相影响* */
public class BlockingQueue2E implements BlockingQueueE {public static void main(String[] args) {BlockingQueue2String 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 sizenew 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[capacity];}Overridepublic void offer(E e) throws InterruptedException {taillock.lockInterruptibly();try {//防止虚假唤醒while (isFull()) {tailWaits.await();}array[tail] e;if (tail array.length) {tail 0;}size.addAndGet(1);//唤醒等待非空的线程headWaits.signal();} finally {taillock.unlock();}}/** 优化后的offer设置等待时间超出则抛出异常* */Overridepublic 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[tail] e;if (tail array.length) {tail 0;}size.getAndIncrement();//唤醒等待非空的线程,必须配合headlocal使用headlock.lock();headWaits.signal();headlock.unlock();return true;} finally {taillock.unlock();}}Overridepublic E pool() throws InterruptedException {headlock.lockInterruptibly();try {while (isFull()) {headWaits.await();}E e array[head];array[head] 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 BlockingQueue2E implements BlockingQueueE {public static void main(String[] args) {BlockingQueue2String 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[capacity];}Overridepublic void offer(E e) throws InterruptedException {taillock.lockInterruptibly();try {//防止虚假唤醒while (isFull()) {tailWaits.await();}array[tail] e;if (tail array.length) {tail 0;}size.addAndGet(1);//唤醒等待非空的线程headWaits.signal();} finally {taillock.unlock();}}/** 优化后的offer设置等待时间超出则抛出异常* */Overridepublic 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[tail] e;if (tail array.length) {tail 0;}c size.getAndIncrement();
// 如果c1arr.length说明还没有满那么级联唤醒if(c1 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;}Overridepublic E pool() throws InterruptedException {E e;//取走钱的元素个数int c;headlock.lockInterruptibly();try {while (isFull()) {headWaits.await();}e array[head];array[head] 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从根节点非叶子节点中最高层的一个开始。 检查该节点与其两个子节点的关系在最大堆中如果当前节点的值小于其任意一个子节点的值在最小堆中如果当前节点的值大于其任意一个子节点的值。 如果违反了堆的性质则交换当前节点与其较大对于最大堆或较小对于最小堆子节点的值并将当前节点移动到新位置即原来子节点的位置。 重复上述步骤但这次以交换后的子节点作为新的当前节点继续下潜至当前节点没有子节点即成为叶子节点或者当前节点及其子节点均满足堆的性质为止。 时间复杂度 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-1for (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[max] array[leftChild]) max leftChild;if (rightChild size array[max] array[rightChild]) max rightChild;if (max ! parent) {//下潜并再次调用swap(parent, max);down(max);}}/** 上浮操作* */public void up(int offered){int child size;//子元素索引等于0则到达了堆顶while (child0){int parent(child-1)/2;if (offeredarray[parent]){array[child]array[parent];}else {break;}childparent;}array[child] offered;}//交换两个元素private void swap(int i, int j) {isEmptyeException();int temp array[i];array[i] array[j];array[j] temp;}public int peek(){isEmptyeException();return array[0];}/** 从第一个位置移除元素交换头尾在移除最后一个* */public int poll(){isEmptyeException();int temparray[0];//交换首位swap(0,size-1);size--;down(0);return temp;}/** 从指定位置移除元素交换指定位置和尾在移除最后一个* */public int poll(int index){isEmptyeException();int temparray[index];//交换首位swap(index,size-1);size--;down(index);return temp;}/** 替换堆顶部元素* 1.替换堆顶元素* 2.执行下潜直到符合堆的特性* */public void replace(int replaced){isEmptyeException();array[0]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-1for (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[max] array[leftChild]) max leftChild;if (rightChild size array[max] array[rightChild]) 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[parent]) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}//交换两个元素private void swap(int i, int j) {int temp array[i];array[i] array[j];array[j] temp;}
} 8.二叉树
8.1概述 二叉树是一种基本的非线性数据结构它是由nn0个节点构成的有限集合。在二叉树中每个节点最多有两个子节点通常被称作左孩子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(treeNodenull){return;}System.out.print(treeNode.val\t);//根节点preOrder(treeNode.left);//左子树preOrder(treeNode.right);//右子树}/** 中序遍历 左子树》》根节点》右子树* */static void inOrder(TreeNode treeNode){if(treeNodenull){return;}inOrder(treeNode.left);//左子树System.out.print(treeNode.val\t);//根节点inOrder(treeNode.right);//右子树}/** 后序遍历 左子树》右子树 》根节点* */static void postOrder(TreeNode treeNode){if(treeNodenull){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){LinkedListTreeNode 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 popstack.pop();curr pop.right;}}}/** 中序遍历 左子树》》根节点》右子树* */static void inOrder(TreeNode treeNode){LinkedListTreeNode 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 popstack.pop();System.out.print(中序 pop.val \t);curr pop.right;}}}/** 后序遍历 左子树》右子树 》根节点* */static void postOrder(TreeNode treeNode){LinkedListTreeNode 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.rightpop) {//最近一次弹栈的元素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){LinkedListTreeNode 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.rightpop) {//最近一次弹栈的元素与当前元素的右子树相等 说明右子树都处理完了pop stack.pop();System.out.println(后序pop.val);}else {//待处理右子树System.out.println(中序peek.val);curr peek.right;}}}}
} 9.二叉搜索树
9.1 概述 二叉搜索树Binary Search TreeBST是一种特殊的二叉树数据结构其设计目的是为了支持高效的查找、插入和删除操作。在二叉搜索树中每个节点都具有以下性质 节点值的排序性 节点的左子树如果存在包含的所有节点的值都小于该节点的值。 节点的右子树如果存在包含的所有节点的值都大于该节点的值。 递归定义 一个空树是二叉搜索树。 如果一个非空树的根节点满足上述排序性并且它的左子树和右子树分别都是二叉搜索树则这个树整体上也是一个二叉搜索树。 操作特性 查找通过比较待查找值与当前节点值来决定是向左子树还是右子树进行查找可以将查找时间减少到对数级别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 noderoot;while (node!null){if(node.keykey){nodenode.left;} else if (node.keykey) {nodenode.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 泛型keyvalue 只要具备比较大小功能的类都可以作为key而具备比较大小功能只需要继承Comparable接口即可,value也可以用泛型来指定。
public class BSTree2T extends ComparableT,V {BSTNodeT,V root;//根节点public BSTree2(BSTNode root) {this.root root;}public BSTree2() {}//泛型key 优化接口必须继承Comparablepublic V get(T key){BSTNodeT,V noderoot;while (node!null){int res node.key.compareTo(key);if(res0){nodenode.left;} else if (res0) {nodenode.right;}else{return node.value;}}return null;}static class BSTNodeT,V {T key;V value;BSTNodeT,Vleft;BSTNodeT,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, BSTNodeT,V left, BSTNodeT,V right) {this.key key;this.value value;this.left left;this.right right;}}
} 9.3 min,max方法实现 public class BSTree3T extends ComparableT, V {BSTNodeT, V root;//根节点public BSTree3(BSTNode root) {this.root root;}public BSTree3() {}//非递归实现public V min() {BSTNodeT, V curr root;if(curr null) return null;while (curr.left ! null) {curr curr.left;}return curr.value;}public V max() {BSTNodeT, 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(BSTNodeT,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(BSTNodeT,V node){if(node null) return null;if(node.right!null){return max(node.right);}else{return node.value;}}*/static class BSTNodeT, V {T key;V value;BSTNodeT, V left;BSTNodeT, 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, BSTNodeT, V left, BSTNodeT, V right) {this.key key;this.value value;this.left left;this.right right;}}
} 9.4 put方法实现 //put
public class BSTree4T extends ComparableT, V {BSTNodeT, V root;//根节点public BSTree4(BSTNode root) {this.root root;}public BSTree4() {}/** 有该节点更新value没有则新增* */public void put(T key,V value){BSTNodeT,Vnoderoot;BSTNodeT,Vparentnode;while (node!null){parentnode;int res node.key.compareTo(key);if(res0){nodenode.left;} else if (res0) {nodenode.right;}else{node.valuevalue;return;}}//没找到新增节点BSTNodeT,VnewNodenew BSTNode(key,value);//树为空if(parentnull){rootnewNode;return;}int res parent.key.compareTo(key);if(res0){parent.leftnewNode;}else if(res0){parent.rightnewNode;}}static class BSTNodeT, V {T key;V value;BSTNodeT, V left;BSTNodeT, 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, BSTNodeT, V left, BSTNodeT, V right) {this.key key;this.value value;this.left left;this.right right;}}
}9.5 前任 后继方法实现 对于一般的二叉搜索树来说其特性是左子树的所有节点值都小于根节点右子树的所有节点值都大于根节点。 我们首先需要找到目标节点。 然后从目标节点开始回溯到其父节点如果目标节点是其父节点的左孩子则其“前任”就是其父节点 如果不是即目标节点是其父节点的右孩子则继续向上回溯至其父节点的父节点重复此过程。 如果在回溯过程中我们到达了根节点且根节点是目标节点的父节点并且目标节点是其右孩子那么说明目标节点没有“前任”。 前任 如果目标有左子树此时前任就是左子树的最大值。 如果目标没有左子树离他最近的自左而来的祖先就是他的前任。 后继 如果目标有右子树此时前任就是右子树的最小值。 如果目标没有右子树离他最近的自右而来的祖先就是他的前任。
//前任后继
public class BSTree5T extends ComparableT, V {BSTNodeT, V root;//根节点public BSTree5(BSTNode root) {this.root root;}public BSTree5() {}/** 如果目标有左子树此时前任就是左子树的最大值。* 如果目标没有左子树离他最近的自左而来的祖先就是他的前任。* */public V successor(T key) {BSTNodeT, V curr root;BSTNodeT, V leftAncestor null;while (curr ! null) {int res key.compareTo(curr.key);if (res 0) {curr curr.left;} else if (res 0) {leftAncestorcurr;curr curr.right;} else {//curr为查找到的节点break;}}//未找到if(currnull){return null;}//有左子树if(curr.left!null){currcurr.left;while (curr.right!null){currcurr.right;}return curr.value;}//节点没有左子树return leftAncestornull?null:leftAncestor.value;}/** 如果目标有右子树此时前任就是右子树的最大值。* 如果目标没有右子树离他最近的自右而来的祖先就是他的前任。* */public V predecessor(T key){BSTNodeT, V curr root;BSTNodeT, V rightAncestor null;while (curr ! null) {int res key.compareTo(curr.key);if (res 0) {rightAncestorcurr;curr curr.left;} else if (res 0) {curr curr.right;} else {//curr为查找到的节点break;}}//未找到if(currnull){return null;}//有左子树if(curr.right!null){currcurr.right;while (curr.left!null){currcurr.left;}return curr.value;}//节点没有左子树return rightAncestornull?null:rightAncestor.value;}static class BSTNodeT, V {T key;V value;BSTNodeT, V left;BSTNodeT, 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, BSTNodeT, V left, BSTNodeT, 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 BSTree6T extends ComparableT, V {BSTNodeT, V root;//根节点public BSTree6(BSTNode root) {this.root root;}public BSTree6() {}public V delete(T key) {BSTNodeT, V curr root;
// 父节点BSTNodeT, 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.查找被删除节点后继节点BSTNodeT, V proNode curr.right;BSTNodeT, 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.rightcurr.right;}
// 3.用后继节点替换被删除节点(删除当前节点将后继节点托管给父节点)shift(parent, curr, proNode);//将被删除节点的左侧节点托管给后继节点proNode.left curr.left;}return curr.value;}private void shift(BSTNodeT, V parent, BSTNodeT, V curr, BSTNodeT, V child) {if (parent null) {//被删除节点没有父元素root curr;} else if (curr parent.left) {//删除节点为父节点的左孩子parent.left child;} else {//删除节点为父节点的右孩子parent.right child;}}static class BSTNodeT, V {T key;V value;BSTNodeT, V left;BSTNodeT, 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, BSTNodeT, V left, BSTNodeT, V right) {this.key key;this.value value;this.left left;this.right right;}}
}9.6.2 递归实现 //删除节点 非递归
public class BSTree6T extends ComparableT, V {BSTNodeT, V root;//根节点public BSTree6(BSTNode root) {this.root root;}public BSTree6() {}public V delete(T key) {ArrayListV arrayList new ArrayList();root delete(key, root, arrayList);return arrayList.isEmpty() ? null : arrayList.get(0);}private BSTNode delete(T key, BSTNodeT, V node, ArrayListV 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;}//有两个子元素//删除节点与后继节点相邻BSTNodeT, V s node.left;BSTNodeT, 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(BSTNodeT, V parent, BSTNodeT, V curr, BSTNodeT, V child) {if (parent null) {//被删除节点没有父元素root curr;} else if (curr parent.left) {//删除节点为父节点的左孩子parent.left child;} else {//删除节点为父节点的右孩子parent.right child;}}static class BSTNodeT, V {T key;V value;BSTNodeT, V left;BSTNodeT, 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, BSTNodeT, V left, BSTNodeT, V right) {this.key key;this.value value;this.left left;this.right right;}}
} 9.7 范围查询 利用中序遍历从小到大遍历将符合条件的值添加到List中
//范围查询
public class BSTree8T extends ComparableT, V {BSTNodeT, V root;//根节点public BSTree8(BSTNode root) {this.root root;}public BSTree8() {}/** 中序遍历可以得到由小到大的结果* 判断与key的关系添加到list内* 将list返回* *///查找小于keypublic ArrayListV less(T key){ArrayListVresnew ArrayList();BSTNodeT,Vproot;LinkedListBSTNodeT,V stacknew LinkedList();while (p!null || !stack.isEmpty()){if(p!null){//未走到最左stack.push(p);pp.left;}else{//到头之后弹栈BSTNodeT, V pop stack.pop();//处理值int popRes pop.key.compareTo(key);if(popRes0){res.add(pop.value);}else {break;}//弹出之后走右侧节点ppop.right;}}return res;}//查找大于keypublic ArrayListV greater(T key){ArrayListVresnew ArrayList();BSTNodeT,Vproot;LinkedListBSTNodeT,V stacknew LinkedList();while (p!null || !stack.isEmpty()){if(p!null){//未走到最左stack.push(p);pp.left;}else{//到头之后弹栈BSTNodeT, V pop stack.pop();//处理值int popRes pop.key.compareTo(key);if(popRes0){res.add(pop.value);}//弹出之后走右侧节点ppop.right;}}return res;}//查找大于等于key1,小于等于key2public ArrayListV between(T key1,T key2){ArrayListVresnew ArrayList();BSTNodeT,Vproot;LinkedListBSTNodeT,V stacknew LinkedList();while (p!null || !stack.isEmpty()){if(p!null){//未走到最左stack.push(p);pp.left;}else{//到头之后弹栈BSTNodeT, V pop stack.pop();//处理值int popRes1 pop.key.compareTo(key1);int popRes2 pop.key.compareTo(key2);if(popRes10 popRes20){res.add(pop.value);}//弹出之后走右侧节点ppop.right;}}return res;}static class BSTNodeT, V {T key;V value;BSTNodeT, V left;BSTNodeT, 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, BSTNodeT, V left, BSTNodeT, 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更新高度 //增、删、旋转更新节点高度//最大高度1public void updateHeight(AVLNode treeNode) {treeNode.heightInteger.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即左边更高-失衡节点的左孩子的bf0即左孩子这边也是左边更高或等一次右旋可以恢复平衡LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡
RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡RR-失衡节点的 bf-1即右边更高-失衡节点的右孩子的bf0即右孩子这边右边更高或等高一次左旋可以恢复平衡//右旋/*** Description 返回旋转后的节点* Param [avlNode] 需要旋转的节点**/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的leftyellowNode.leftredNode;updateHeight(redNode);updateHeight(yellowNode);return yellowNode;}/** LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡* *///先左旋再右旋private AVLNode leftRightRotate(AVLNode node) {//修正左子结点LLnode.left leftRotate(node.left);return rightRotate(node);}/** RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡* *///先右旋再左旋private AVLNode rightLeftRotate(AVLNode node) {//修正右子节点为RRnode.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 {//左子树右边更高 LRreturn leftRightRotate(node);}} else if (bf -1) {int rightBf bf(node.right);if (rightBf 0) {//右子树左边更高 RR 虑到删除时等于0也要左旋return leftRotate(node);} else {//右子树右边更高 RLreturn 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.valuevalue;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. nodenullif (node null) {return node;}//2.未找到keyif (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.找到keyif (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 snode;while (s.left!null){ss.left;}//s即为后继节点,将节点删除并重新修正右子树s.rightdoRemove(s.right,s.key);//左子树为s.left,右子树为原删除节点的左子树s.leftnode.left;nodes;}}//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;//高度初始值1AVLNode 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;}//增、删、旋转更新节点高度//最大高度1public 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即左边更高-失衡节点的左孩子的bf0即左孩子这边也是左边更高或等一次右旋可以恢复平衡LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡RR-失衡节点的 bf-1即右边更高-失衡节点的右孩子的bf0即右孩子这边右边更高或等高一次左旋可以恢复平衡
*///右旋/*** Description 返回旋转后的节点* Param [avlNode] 需要旋转的节点**/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的leftyellowNode.left redNode;updateHeight(redNode);updateHeight(yellowNode);return yellowNode;}/** LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡* *///先左旋再右旋private AVLNode leftRightRotate(AVLNode node) {//修正左子结点LLnode.left leftRotate(node.left);return rightRotate(node);}/** RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡* *///先右旋再左旋private AVLNode rightLeftRotate(AVLNode node) {//修正右子节点为RRnode.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 {//左子树右边更高 LRreturn leftRightRotate(node);}} else if (bf -1) {int rightBf bf(node.right);if (rightBf 0) {//右子树左边更高 RR 虑到删除时等于0也要左旋return leftRotate(node);} else {//右子树右边更高 RLreturn 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. nodenullif (node null) {return node;}//2.未找到keyif (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.找到keyif (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 snode;while (s.left!null){ss.left;}//s即为后继节点,将节点删除并重新修正右子树s.rightdoRemove(s.right,s.key);//左子树为s.left,右子树为原删除节点的左子树s.leftnode.left;nodes;}}//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右为falseboolean 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(parentnull){return null;}if(this.isLeftChild()){return parent.right;}else {return parent.left;}}} 11.2 判断颜色 //判断颜色boolean isRed(Node node){return node!nullnode.colorRED;}boolean isBlack(Node node){return nodenull||node.colorBLACK;} 11.3 左旋和右旋 //和AVL树的不同// 右旋1.父(Parent)的处理2.旋转后新根的父子关系方法内处理void rotateRight(Node pink) {//获取pink的父级几点Node parent pink.parent;//旋转Node yellow pink.left;Node gree yellow.right;//右旋之后换色节点的右子结点变为Pinkyellow.right pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.left gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.left pink) {//处理父子关系yellow代替pinkparent.left yellow;} else {parent.right yellow;}}void rotateLeft(Node pink) {//获取pink的父级几点Node parent pink.parent;//旋转Node yellow pink.right;Node gree yellow.left;//右旋之后换色节点的右子结点变为Pinkyellow.left pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.right gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.right pink) {//处理父子关系yellow代替pinkparent.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.colorBLACK;//祖父变为红色grandParent.colorRED;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.colorBLACK;//祖父变为红色grandParent.colorRED;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和case5if (x root) {return;}Node parent x.parent;Node sibling x.sibling();if (sibling.color RED) {//进入case3if (x.isLeftChild()) {//如果是做孩子就进行左旋rotateLeft(parent);} else {//如果是右孩子就进行右旋rotateRight(parent);}//父亲颜色变为红色父亲变色前肯定为黑色parent.color RED;//兄弟变为黑色sibling.color BLACK;//此时case3 已经被转换为 case4或者case5fixDoubleBlack(x);return;}//兄弟为黑//两个侄子都为黑if (sibling ! null) {if (isBlack(sibling.left) isBlack(sibling.right)) {/** case 4:被调整节点的兄弟为黑,两个侄于都为黑* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1* 如果父亲是红,则需将父亲变为黑避免红红此时路径黑节点数目不变* 如果父亲是黑,说明这条路径则少了一个黑再次让父节点触发双黑* *///将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1sibling.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.colorBLACK;//兄弟变成父亲的颜色sibling.color parent.color;//父亲变黑parent.colorBLACK;}else if(sibling.isLeftChild()isRed(sibling.right)){//如果兄弟是左孩子右侄子是红 LR 不平衡//变色必须在上 否则旋转后会空指针//兄弟的右孩子变为父节点颜色sibling.right.color parent.color;//父节点变黑parent.colorBLACK;rotateLeft(sibling);rotateRight(parent);}}} else {fixDoubleBlack(parent);}}private void doRemove(Node deleted) {Node replaced findReplaced(deleted);Node parent deleted.parent;if (replaced null) {//没有子节点/* case1:删的是根节点,没有子节点* 删完了直接将 rootnull* */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:删的是根节点,有一个子节点* 用剩余节点替换了根节点的 keyValue根节点孩子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 {//两个子节点//交换删除节点和删除节点的后几点的keyvalue这// 样被删除节点就只有一个子节点或没有子节点了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右为falseboolean 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;//右旋之后换色节点的右子结点变为Pinkyellow.right pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.left gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.left pink) {//处理父子关系yellow代替pinkparent.left yellow;} else {parent.right yellow;}}void rotateLeft(Node pink) {//获取pink的父级几点Node parent pink.parent;//旋转Node yellow pink.right;Node gree yellow.left;//右旋之后换色节点的右子结点变为Pinkyellow.left pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.right gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.right pink) {//处理父子关系yellow代替pinkparent.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和case5if (x root) {return;}Node parent x.parent;Node sibling x.sibling();if (sibling.color RED) {//进入case3if (x.isLeftChild()) {//如果是做孩子就进行左旋rotateLeft(parent);} else {//如果是右孩子就进行右旋rotateRight(parent);}//父亲颜色变为红色父亲变色前肯定为黑色parent.color RED;//兄弟变为黑色sibling.color BLACK;//此时case3 已经被转换为 case4或者case5fixDoubleBlack(x);return;}//兄弟为黑//两个侄子都为黑if (sibling ! null) {if (isBlack(sibling.left) isBlack(sibling.right)) {/** case 4:被调整节点的兄弟为黑,两个侄于都为黑* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1* 如果父亲是红,则需将父亲变为黑避免红红此时路径黑节点数目不变* 如果父亲是黑,说明这条路径则少了一个黑再次让父节点触发双黑* *///将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1sibling.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.colorBLACK;//兄弟变成父亲的颜色sibling.color parent.color;//父亲变黑parent.colorBLACK;}else if(sibling.isLeftChild()isRed(sibling.right)){//如果兄弟是左孩子右侄子是红 LR 不平衡//变色必须在上 否则旋转后会空指针//兄弟的右孩子变为父节点颜色sibling.right.color parent.color;//父节点变黑parent.colorBLACK;rotateLeft(sibling);rotateRight(parent);}}} else {fixDoubleBlack(parent);}}private void doRemove(Node deleted) {Node replaced findReplaced(deleted);Node parent deleted.parent;if (replaced null) {//没有子节点/* case1:删的是根节点,没有子节点* 删完了直接将 rootnull* */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:删的是根节点,有一个子节点* 用剩余节点替换了根节点的 keyValue根节点孩子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 {//两个子节点//交换删除节点和删除节点的后几点的keyvalue这// 样被删除节点就只有一个子节点或没有子节点了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更新高度 //增、删、旋转更新节点高度//最大高度1public void updateHeight(AVLNode treeNode) {treeNode.heightInteger.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即左边更高-失衡节点的左孩子的bf0即左孩子这边也是左边更高或等一次右旋可以恢复平衡LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡
RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡RR-失衡节点的 bf-1即右边更高-失衡节点的右孩子的bf0即右孩子这边右边更高或等高一次左旋可以恢复平衡//右旋/*** Description 返回旋转后的节点* Param [avlNode] 需要旋转的节点**/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的leftyellowNode.leftredNode;updateHeight(redNode);updateHeight(yellowNode);return yellowNode;}/** LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡* *///先左旋再右旋private AVLNode leftRightRotate(AVLNode node) {//修正左子结点LLnode.left leftRotate(node.left);return rightRotate(node);}/** RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡* *///先右旋再左旋private AVLNode rightLeftRotate(AVLNode node) {//修正右子节点为RRnode.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 {//左子树右边更高 LRreturn leftRightRotate(node);}} else if (bf -1) {int rightBf bf(node.right);if (rightBf 0) {//右子树左边更高 RR 虑到删除时等于0也要左旋return leftRotate(node);} else {//右子树右边更高 RLreturn 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.valuevalue;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. nodenullif (node null) {return node;}//2.未找到keyif (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.找到keyif (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 snode;while (s.left!null){ss.left;}//s即为后继节点,将节点删除并重新修正右子树s.rightdoRemove(s.right,s.key);//左子树为s.left,右子树为原删除节点的左子树s.leftnode.left;nodes;}}//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;//高度初始值1AVLNode 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;}//增、删、旋转更新节点高度//最大高度1public 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即左边更高-失衡节点的左孩子的bf0即左孩子这边也是左边更高或等一次右旋可以恢复平衡LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡RR-失衡节点的 bf-1即右边更高-失衡节点的右孩子的bf0即右孩子这边右边更高或等高一次左旋可以恢复平衡
*///右旋/*** Description 返回旋转后的节点* Param [avlNode] 需要旋转的节点**/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的leftyellowNode.left redNode;updateHeight(redNode);updateHeight(yellowNode);return yellowNode;}/** LR-失衡节点的 bf 1即左边更高-失衡节点的左孩子的bf0 即左孩子这边是右边更高左子节点先左旋将树修正为LL情况然后失衡节点再右旋恢复平衡* *///先左旋再右旋private AVLNode leftRightRotate(AVLNode node) {//修正左子结点LLnode.left leftRotate(node.left);return rightRotate(node);}/** RL-失衡节点的 bf -1即右边更高-失衡节点的右孩子的bf0即右孩子这边左边更高右子节点先右旋将树修正为RR情况然后失衡节点再左旋恢复平衡* *///先右旋再左旋private AVLNode rightLeftRotate(AVLNode node) {//修正右子节点为RRnode.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 {//左子树右边更高 LRreturn leftRightRotate(node);}} else if (bf -1) {int rightBf bf(node.right);if (rightBf 0) {//右子树左边更高 RR 虑到删除时等于0也要左旋return leftRotate(node);} else {//右子树右边更高 RLreturn 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. nodenullif (node null) {return node;}//2.未找到keyif (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.找到keyif (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 snode;while (s.left!null){ss.left;}//s即为后继节点,将节点删除并重新修正右子树s.rightdoRemove(s.right,s.key);//左子树为s.left,右子树为原删除节点的左子树s.leftnode.left;nodes;}}//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右为falseboolean 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(parentnull){return null;}if(this.isLeftChild()){return parent.right;}else {return parent.left;}}} 11.2 判断颜色 //判断颜色boolean isRed(Node node){return node!nullnode.colorRED;}boolean isBlack(Node node){return nodenull||node.colorBLACK;} 11.3 左旋和右旋 //和AVL树的不同// 右旋1.父(Parent)的处理2.旋转后新根的父子关系方法内处理void rotateRight(Node pink) {//获取pink的父级几点Node parent pink.parent;//旋转Node yellow pink.left;Node gree yellow.right;//右旋之后换色节点的右子结点变为Pinkyellow.right pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.left gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.left pink) {//处理父子关系yellow代替pinkparent.left yellow;} else {parent.right yellow;}}void rotateLeft(Node pink) {//获取pink的父级几点Node parent pink.parent;//旋转Node yellow pink.right;Node gree yellow.left;//右旋之后换色节点的右子结点变为Pinkyellow.left pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.right gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.right pink) {//处理父子关系yellow代替pinkparent.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.colorBLACK;//祖父变为红色grandParent.colorRED;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.colorBLACK;//祖父变为红色grandParent.colorRED;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和case5if (x root) {return;}Node parent x.parent;Node sibling x.sibling();if (sibling.color RED) {//进入case3if (x.isLeftChild()) {//如果是做孩子就进行左旋rotateLeft(parent);} else {//如果是右孩子就进行右旋rotateRight(parent);}//父亲颜色变为红色父亲变色前肯定为黑色parent.color RED;//兄弟变为黑色sibling.color BLACK;//此时case3 已经被转换为 case4或者case5fixDoubleBlack(x);return;}//兄弟为黑//两个侄子都为黑if (sibling ! null) {if (isBlack(sibling.left) isBlack(sibling.right)) {/** case 4:被调整节点的兄弟为黑,两个侄于都为黑* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1* 如果父亲是红,则需将父亲变为黑避免红红此时路径黑节点数目不变* 如果父亲是黑,说明这条路径则少了一个黑再次让父节点触发双黑* *///将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1sibling.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.colorBLACK;//兄弟变成父亲的颜色sibling.color parent.color;//父亲变黑parent.colorBLACK;}else if(sibling.isLeftChild()isRed(sibling.right)){//如果兄弟是左孩子右侄子是红 LR 不平衡//变色必须在上 否则旋转后会空指针//兄弟的右孩子变为父节点颜色sibling.right.color parent.color;//父节点变黑parent.colorBLACK;rotateLeft(sibling);rotateRight(parent);}}} else {fixDoubleBlack(parent);}}private void doRemove(Node deleted) {Node replaced findReplaced(deleted);Node parent deleted.parent;if (replaced null) {//没有子节点/* case1:删的是根节点,没有子节点* 删完了直接将 rootnull* */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:删的是根节点,有一个子节点* 用剩余节点替换了根节点的 keyValue根节点孩子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 {//两个子节点//交换删除节点和删除节点的后几点的keyvalue这// 样被删除节点就只有一个子节点或没有子节点了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右为falseboolean 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;//右旋之后换色节点的右子结点变为Pinkyellow.right pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.left gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.left pink) {//处理父子关系yellow代替pinkparent.left yellow;} else {parent.right yellow;}}void rotateLeft(Node pink) {//获取pink的父级几点Node parent pink.parent;//旋转Node yellow pink.right;Node gree yellow.left;//右旋之后换色节点的右子结点变为Pinkyellow.left pink;//之前黄色节点的左子结点赋值给pink完成右旋pink.right gree;if (gree ! null) {//处理父子关系gree.parent pink;}//处理父子关系yellow.parent parent;pink.parent yellow;//如果parent为空则根节点为yellowif (parent null) {root yellow;} else if (parent.right pink) {//处理父子关系yellow代替pinkparent.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和case5if (x root) {return;}Node parent x.parent;Node sibling x.sibling();if (sibling.color RED) {//进入case3if (x.isLeftChild()) {//如果是做孩子就进行左旋rotateLeft(parent);} else {//如果是右孩子就进行右旋rotateRight(parent);}//父亲颜色变为红色父亲变色前肯定为黑色parent.color RED;//兄弟变为黑色sibling.color BLACK;//此时case3 已经被转换为 case4或者case5fixDoubleBlack(x);return;}//兄弟为黑//两个侄子都为黑if (sibling ! null) {if (isBlack(sibling.left) isBlack(sibling.right)) {/** case 4:被调整节点的兄弟为黑,两个侄于都为黑* 将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1* 如果父亲是红,则需将父亲变为黑避免红红此时路径黑节点数目不变* 如果父亲是黑,说明这条路径则少了一个黑再次让父节点触发双黑* *///将兄弟变红, 目的是将删除节点和兄弟那边的黑色高度同时减少1sibling.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.colorBLACK;//兄弟变成父亲的颜色sibling.color parent.color;//父亲变黑parent.colorBLACK;}else if(sibling.isLeftChild()isRed(sibling.right)){//如果兄弟是左孩子右侄子是红 LR 不平衡//变色必须在上 否则旋转后会空指针//兄弟的右孩子变为父节点颜色sibling.right.color parent.color;//父节点变黑parent.colorBLACK;rotateLeft(sibling);rotateRight(parent);}}} else {fixDoubleBlack(parent);}}private void doRemove(Node deleted) {Node replaced findReplaced(deleted);Node parent deleted.parent;if (replaced null) {//没有子节点/* case1:删的是根节点,没有子节点* 删完了直接将 rootnull* */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:删的是根节点,有一个子节点* 用剩余节点替换了根节点的 keyValue根节点孩子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 {//两个子节点//交换删除节点和删除节点的后几点的keyvalue这// 样被删除节点就只有一个子节点或没有子节点了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;}}
}
