PipedInputStream和PipedOutputStream
管道输入输出流也是一对内存操作可循环读写的数组的输入输出流,基本上读写的方法都是放在 PipedInputStream
这个对象中,在做读写操作的时候需要把输入输出流进行关联,否则不能做对应的读写操作。
用最初的心,做永远的事.
在Java中有输入、输出两种IO流,每种输入、输出流又分为字节流和字符流两大类。
一个字节 8 个bit
Java采用unicode
编码,2个字节来表示一个字符。(C语言中采用ASCII,在大多数系统中,一个字符通常占1个字节,但是在0~127整数之间的字符映射,unicode
向下兼容ASCII。)
Java采用unicode
来表示字符,一个中文或英文字符的unicode
编码都占2个字节。但如果采用其他编码方式,一个字符占用的字节数则各不相同。
Java中的String类是按照unicode进行编码的,当使用 String(byte[] bytes, String encoding)
构造字符串时,encoding所指的是bytes中的数据是按照那种方式编码的,而不是最后产生的String是什么编码方式。换句话说,是让系统把bytes中的数据由encoding编码方式转换成unicode编码。如果不指明,bytes的编码方式将由jdk根据操作系统决定。
1 | <!--事物管理类--> |
2 | <bean id="dataSourceTransactionManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager"> |
3 | <property name="dataSource" ref="dataSource"/> |
4 | </bean> |
5 | <!--开启注解模式--> |
6 | <!-- 基于注解的事务管理:事务开启的入口 --> |
7 | <tx:annotation-driven transaction-manager="dataSourceTransactionManager"/> |
8 | <!--<tx:jta-transaction-manager/>--> |
堆(heap)又被为优先队列(priority queue). 尽管名为优先队列,但堆并不是队列。在队列中,我们可以进行的限定操作是dequeue和enqueue。dequeue是按照进入队列的先后顺序来取出元素。而在堆中,我们不是按照元素进入队列的先后顺序取出元素的,而是按照元素的优先级取出元素。
这就好像候机的时候,无论谁先到达候机厅,总是头等舱的乘客先登机,然后是商务舱的乘客,最后是经济舱的乘客。每个乘客都有头等舱、商务舱、经济舱三种个键值(key)中的一个。头等舱->商务舱->经济舱依次享有从高到低的优先级。
Linux内核中的调度器(scheduler)会按照各个进程的优先级来安排CPU执行哪一个进程。计算机中通常有多个进程,每个进程有不同的优先级(该优先级的计算会综合多个因素,比如进程所需要耗费的时间,进程已经等待的时间,用户的优先级,用户设定的进程优先程度等等)。内核会找到优先级最高的进程,并执行。如果有优先级更高的进程被提交,那么调度器会转而安排该进程运行。优先级比较低的进程则会等待。“堆”是实现调度器的理想数据结构。
(Linux中可以使用nice命令来影响进程的优先级)
堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。
n个元素序列 { k1, k2, k3, k4, k5, k6 …. kn } 当且仅当满足以下关系时才会被称为堆:
1 | ki <= k2i,ki <= k2i+1 或者 ki >= k2i,ki >= k2i+1 (i = 1,2,3,4 .. n/2) |
如果数组的下表是从0开始,那么需要满足
1 | ki <= k2i+1,ki <= k2i+2 或者 ki >= k2i+1,ki >= k2i+2 (i = 0,1,2,3 .. n/2) |
比如 { 1,3,5,10,15,9 } 这个序列就满足 [1 <= 3; 1 <= 5], [3 <= 10; 3 <= 15], [5 <= 9] 这3个条件,这个序列就是一个堆。
所以堆其实是一个序列(数组),如果这个序列满足上述条件,那么就把这个序列看成堆。
首先,二叉堆和二叉树有啥关系呢,为什么人们总数把二叉堆画成一棵二叉树?
因为,二叉堆其实就是一种特殊的二叉树(完全二叉树),只不过存储在数组里。一般的链表二叉树,我们操作节点的指针,而在数组里,我们把数组索引作为指针:
1 | // 父节点的索引 |
2 | int parent(int root){ |
3 | return root / 2; |
4 | } |
5 | // 左孩子的索引 |
6 | int left(int root) { |
7 | return root * 2; |
8 | } |
9 | // 右孩子的索引 |
10 | int right(int root) { |
11 | return root * 2 + 1; |
12 | } |
堆的实现通常是通过构造二叉堆,因为二叉堆应用很普遍,当不加限定时,堆通常指的就是二叉堆。
你看到了,把 arr[1] 作为整棵树的根的话,每个节点的父节点和左右孩子的索引都可以通过简单的运算得到,这就是二叉堆设计的一个巧妙之处。为了方便讲解,下面都会画的图都是二叉树结构,相信你能把树和数组对应起来。
二叉堆还分为最大堆和最小堆。最大堆的性质是:每个节点都大于等于它的两个子节点。类似的,最小堆的性质是:每个节点都小于等于它的子节点。
堆的一个经典的实现是完全二叉树(complete binary tree)。这样实现的堆成为二叉堆(binary heap)。
二叉堆是一种特殊的堆,是一棵完全二叉树或者是近似完全二叉树,同时二叉堆还满足堆的特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
上图中的最小堆对应的序列是: [1,3,5,9,10,15] 满足最小堆的特性(父节点的键值小于或等于任何一个子节点的键值,并且也满足堆的性质 [1 <= 3; 1 <= 5], [3 <= 9; 3 <= 10], [5 <= 15])
上图中的最大堆对应的序列是: [15,10,9,7,5,3] 满足最大堆的特性(父节点的键值大于或等于任何一个子节点的键值,并且也满足堆的性质 [15 >= 10; 15 >= 9], [10 >= 7; 10 >= 5], [9 >= 3])
两种堆核心思路都是一样的,本文以最大堆为例讲解。
对于一个最大堆,根据其性质,显然堆顶,也就是 arr[1] 一定是所有元素中最大的元素。
优先级队列这种数据结构有一个很有用的功能,你插入或者删除元素的时候,元素会自动排序,这底层的原理就是二叉堆的操作。
数据结构的功能无非增删查该,优先级队列有两个主要 API,分别是 insert 插入一个元素和 delMax 删除最大元素(如果底层用最小堆,那么就是 delMin)。
下面我们实现一个简化的优先级队列,先看下代码框架:
1 | public class MaxPq<T extends Comparable> { |
2 | /** |
3 | * 存储元素的数组 |
4 | */ |
5 | private T[] pq; |
6 | /** |
7 | * 当前 Priority Queue 中的元素个数 |
8 | */ |
9 | private int N = 0; |
10 | public MaxPq(int cap) { |
11 | // 索引 0 不用,所以多分配一个空间 |
12 | pq = (T[]) new Comparable[cap + 1]; |
13 | } |
14 | /** |
15 | * 返回当前队列中最大元素 |
16 | * @return |
17 | */ |
18 | public T max(){ |
19 | return pq[1]; |
20 | } |
21 | /* 插入元素 e */ |
22 | public void insert(T e) { |
23 | //..... |
24 | } |
25 | /* 删除并返回当前队列中最大元素 */ |
26 | public T delMax() { |
27 | //... |
28 | return null; |
29 | } |
30 | /* 上浮第 k 个元素,以维护最大堆性质 */ |
31 | private void swim(int k) { |
32 | //... |
33 | } |
34 | /* 下沉第 k 个元素,以维护最大堆性质 */ |
35 | private void sink(int k) { |
36 | //... |
37 | } |
38 | /* 交换数组的两个元素 */ |
39 | private void exch(int i, int j) { |
40 | T temp = pq[i]; |
41 | pq[i] = pq[j]; |
42 | pq[j] = temp; |
43 | } |
44 | /* pq[i] 是否比 pq[j] 小? */ |
45 | private boolean less(int i, int j) { |
46 | return pq[i].compareTo(pq[j]) < 0; |
47 | } |
48 | /* 还有 left, right, parent 三个方法 */ |
49 | } |
为什么要有上浮 swim 和 下沉 sink 的操作呢?为了维护堆结构。
我们要讲的是最大堆,每个节点都比它的两个子节点大,但是在插入元素和删除元素时,难免破坏堆的性质,这就需要通过这两个操作来恢复堆的性质了。
对于最大堆,会破坏堆性质的有有两种情况:
当然,错位的节点 A 可能要上浮(或下沉)很多次,才能到达正确的位置,恢复堆的性质。所以代码中肯定有一个 while
循环。
细心的读者也许会问,这两个操作不是互逆吗,所以上浮的操作一定能用下沉来完成,为什么我还要费劲写两个方法?
是的,操作是互逆等价的,但是最终我们的操作只会在堆底和堆顶进行(等会讲原因),显然堆底的「错位」元素需要上浮,堆顶的「错位」元素需要下沉。
1 | private void swim(int k) { |
2 | // 如果浮到堆顶,就不能再上浮了 |
3 | while (k > 1 && less(parent(k), k)) { |
4 | // 如果第 k 个元素比上层大 |
5 | // 将 k 换上去 |
6 | exch(parent(k), k); |
7 | k = parent(k); |
8 | } |
9 | } |
如下图:
下沉比上浮略微复杂一点,因为上浮某个节点 A,只需要 A 和其父节点比较大小即可;但是下沉某个节点 A,需要 A 和其两个子节点比较大小,如果 A 不是最大的就需要调整位置,要把较大的那个子节点和 A 交换。
1 | private void sink(int k) { |
2 | // 如果沉到堆底,就沉不下去了 |
3 | while (left(k) <= N) { |
4 | // 先假设左边节点较大 |
5 | int older = left(k); |
6 | // 如果右边节点存在,比一下大小 |
7 | if (right(k) <= N && less(older, right(k))) |
8 | older = right(k); |
9 | // 结点 k 比俩孩子都大,就不必下沉了 |
10 | if (less(older, k)) break; |
11 | // 否则,不符合最大堆的结构,下沉 k 结点 |
12 | exch(k, older); |
13 | k = older; |
14 | } |
15 | } |
如下图:
至此,二叉堆的主要操作就讲完了,一点都不难吧,代码加起来也就十行。明白了 sink
和 swim
的行为,下面就可以实现优先级队列了。
这两个方法就是建立在 swim
和 sink
上的。
insert
方法先把要插入的元素添加到堆底的最后,然后让其上浮到正确位置。
1 | public void insert(Key e) { |
2 | N++; |
3 | // 先把新元素加到最后 |
4 | pq[N] = e; |
5 | // 然后让它上浮到正确的位置 |
6 | swim(N); |
7 | } |
delMax
方法先把堆顶元素 A 和堆底最后的元素 B 对调,然后删除 A,最后让 B 下沉到正确位置。
1 | public Key delMax() { |
2 | // 最大堆的堆顶就是最大元素 |
3 | Key max = pq[1]; |
4 | // 把这个最大元素换到最后,删除之 |
5 | exch(1, N); |
6 | pq[N] = null; |
7 | N--; |
8 | // 让 pq[1] 下沉到正确位置 |
9 | sink(1); |
10 | return max; |
11 | } |
至此,一个优先级队列就实现了,插入和删除元素的时间复杂度为 O(logK)O(logK),KK 为当前二叉堆(优先级队列)中的元素总数。因为我们时间复杂度主要花费在 sink 或者 swim 上,而不管上浮还是下沉,最多也就树(堆)的高度,也就是 log 级别。
二叉堆就是一种完全二叉树,所以适合存储在数组中,而且二叉堆拥有一些特殊性质。
二叉堆的操作很简单,主要就是上浮和下沉,来维护堆的性质(堆有序),核心代码也就十行。
优先级队列是基于二叉堆实现的,主要操作是插入和删除。插入是先插到最后,然后上浮到正确位置;删除是调换位置后再删除,然后下沉到正确位置。核心代码也就十行。
平衡二叉搜索树(Balanced Binary Search Tree),英文简称 BBST。经典常见的平衡二叉搜索树是 AVL 树和红黑树。
二叉搜索树(Binary Search Tree)是二叉树的一种,英文简称 BST。又称为二叉查找树、二叉排序树。
它的特点是任何一个结点的值都大于其左子树的所有结点的值,任何一个结点的值都小于其右子树的所有结点的值。
平衡(Balance):就是当结点数量固定时,左右子树的高度越接近,这棵二叉树越平衡(高度越低)。而最理想的平衡就是完全二叉树/满二叉树,高度最小的二叉树。
一棵二叉搜索树平均时间复杂度可以认为是树的高度 O(h)。像左边这棵,结点的左右子树的高度接近,属于一棵平衡二叉搜索树,O(h) = O(logn);而右边这棵,高度达到了最大,已经退化成了链表,O(h)=O(n)。
当二叉树退化成链表时,性能是很低的,所以我们需要在结点的插入、删除操作之后,想办法让二叉搜索树恢复平衡(减小树的高度)。但是如果为了追求最理想的平衡,而增加了时间复杂度也不是很有必要,因此比较合理的方案就是:用尽量少的调整次数达到适度平衡。
由此引申出 AVL 树的概念。
AVL 树是最早发明的自平衡二叉搜索树之一,它取名自两位发明家的名字:G.M.Adelson-Velsky 和 E.M.Landis。
举例:
再看这棵 AVL 树和它每个结点对应的平衡因子:
可以看到 AVL 树具有以下特点:
B 树(Balanced Tree)是一种平衡的多路搜索树,多用于文件系统、数据库的实现。这是一个简单的 3 阶 B 树:
m 阶 B 树指的是一个结点最多拥有 m 个子结点.假设一个结点存储的元素个数为 x,那么如果这个结点是:
如果有子结点,子结点个数 为 y = x + 1,那么如果这个结点是:
向上取整(Ceiling),指的是取比自己大的最小整数,用数学符号 ┌ ┐ 表示。
向下取整(Floor),指的是取比自己小的最大整数,用数学符号 └ ┘ 表示。
比如 m = 3, 子结点个数 2 ≤ y ≤ 3,这个 B 树可以称为(2,3)树、2-3 树;
比如 m = 4, 子结点个数 2 ≤ y ≤ 4,这个 B 树可以称为(2,4)树、2-3-4 树;
比如 m = 5, 子结点个数 3 ≤ y ≤ 4,这个 B 树可以称为(3,5)树、3-4-5 树;
这是一棵二叉搜索树,通过某些父子结点合并,恰好能与上面的 B 树对应。我们可以得到结论:
红黑树,本质上是一颗二叉查找树,但他在二叉查找树的基础上增加了着色和相关的性质,使得红黑树相对平衡,从而保证了红黑树的查找,插入,删除的复杂度最坏为O(log n).
如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢?这就引出了红黑树的5条性质.
红黑树是一种含有红黑结点并能自平衡的二叉搜索树。
上文中我们所说的 “叶结点” 或”NULL结点”,它不包含数据而只充当树在此结束的指示,这些结点以及它们的父结点,在绘图中都会经常被省略。
根据上面的性质,可以画出这样一棵红黑树。接下来对红黑树做等价变换,即将所有的红色结点上升一层与它的父结点放在同一行,这就很像一棵 4 阶 B 树,转换效果如下图所示。
当我们对一棵平衡二叉搜索树进行插入、删除的时候,很可能会让这棵树变得失衡(最坏可能导致所有祖先结点失衡,但是父结点和非祖先结点都不可能失衡),为了达到平衡,需要对树进行旋转。而红黑树能够达到自平衡,靠的也就是左旋、右旋和变色。
旋转操作是局部的。当一侧子树的结点少了,向另一侧“借”一些结点;当一侧子树的结点多了,则“租”一些结点给另一侧。
左旋指的是以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。
不考虑结点颜色,可以看到左旋只影响旋转结点和其右子树的结构,把右子树的结点往左子树移动。
右旋指的是以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。
不考虑结点颜色,可以看到右旋只影响旋转结点和其左子树的结构,把左子树的结点往右子树移动。
左旋和右旋知识详见 al_05_平衡二叉树的 @ 二叉树的修正机制 章节;
变色指的是结点的颜色由红变黑或由黑变红。
将左旋、右旋和变色结合起来,得到一套变换规则。
如果当前结点的父结点和叔父结点是红色,那么:
当前结点是右子树,且父结点是红色,叔父结点是黑色,对它的父结点左旋
当前结点是左子树,且父结点是红色,叔父结点是黑色,那么:
由于红黑树本来就是平衡二叉搜索树,并且搜索也不会破坏树的平衡,所以搜索算法也与平衡二叉搜索树一致:
具体步骤:
具体步骤:
建议新添加的结点默认为红色,因此这样能够让红黑树的性质尽快满足。不过如果添加的结点是根结点,设为黑色即可。
总结一下红黑树插入可能出现的所有场景。
红黑树的性质 2:根结点必须是黑色。
处理:直接把插入结点设成黑色并作为根结点。
二叉搜索树中不能插入相同元素,既然结点的 key 已经存在,红黑树也已平衡,无需重复插入。
处理:
插入的结点默认是红色的,当它的父结点是黑色时,并不会破坏平衡。
处理:直接插入。
如果插入结点的父结点为红色,那么父结点不可能为根结点,所以插入结点总是存在祖父结点。这点很重要,后续的旋转操作需要祖父结点的参与。
由红黑树性质 4 可知:红色结点不能连续。那么此时该插入子树的红黑层数的情况是:黑-红-红。显然最简单的处理方式就是将其改为:红-黑-红。
处理:
这种场景下,叔父结点所在的子树的黑色结点就比父结点所在子树的多,不满足红黑树的性质 5。
处理:
这种场景显然可以转换为 4.2.1。
处理:
相当于场景 4.2 的方向反转,直接看图。
处理:
处理:
红黑树的插入过程和二叉查找树插入过程基本类似,不同的地方在于,红黑树插入新节点后,需要进行调整,以满足红黑树的性质。
下来,将分析插入红色节点后红黑树的情况。这里假设要插入的节点为 N,N 的父节点为 P,祖父节点为 G,叔叔节点为 U。插入红色节点后,会出现5种情况,分别如下:
插入的新节点 N 是红黑树的根节点,这种情况下,我们把节点 N 的颜色由红色变为黑色,性质2(根是黑色)被满足。同时 N 被染成黑色后,红黑树所有路径上的黑色节点数量增加一个,性质5(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点)仍然被满足。
N 的父节点是黑色,这种情况下,性质4(每个红色节点必须有两个黑色的子节点)和性质5没有受到影响,不需要调整。
N 的父节点是红色(节点 P 为红色,其父节点必然为黑色),叔叔节点 U 也是红色。由于 P 和 N 均为红色,所有性质4被打破,此时需要进行调整。这种情况下,先将 P 和 U 的颜色染成黑色,再将 G 的颜色染成红色。此时经过 G 的路径上的黑色节点数量不变,性质5仍然满足。但需要注意的是 G 被染成红色后,可能会和它的父节点形成连续的红色节点,此时需要递归向上调整。
N 的父节点为红色,叔叔节点为黑色。节点 N 是 P 的右孩子,且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋,调整 N 与 P 的位置。接下来按照情况五进行处理,以恢复性质4。
N 的父节点为红色,叔叔节点为黑色。N 是 P 的左孩子,且节点 P 是 G 的左孩子。此时对 G 进行右旋,调整 P 和 G 的位置,并互换颜色。经过这样的调整后,性质4被恢复,同时也未破坏性质5。
上面五种情况中,情况一和情况二比较简单,情况三、四、五稍复杂。但如果细心观察,会发现这三种情况的区别在于叔叔节点的颜色,如果叔叔节点为红色,直接变色即可。如果叔叔节点为黑色,则需要选选择,再交换颜色。当把这三种情况的图画在一起就区别就比较容易观察了,如下图:
红黑树删除操作也分为两步:
定位删除位置可以复用红黑树搜索的操作。
如果不存在目标结点,忽略本次操作;如果找到目标结点,删除后进行自平衡处理。
二叉搜索树删除的时候可能出现三种场景:
具体应用,可以借助这张图理解:
我们可以发现,另外两种二叉树的删除场景都可以通过相互转换变为场景一。
在场景二情况下:删除结点用其唯一的子结点替换,子结点替换为删除结点后,可以认为删除的是子结点,若子结点又有两个子结点,那么相当于转换为场景三,一直自顶向下转换,总是能转换为场景一。
在场景三情况下:删除结点用后继结点,如果后继结点有右子结点,那么相当于转换为场景二,否则转为场景一。
综上所述,删除的结点可以看作删除替换结点,且替换结点最后总是在树末。
下面总结一下红黑树删除可能出现的所有场景。
为了方面理解,我们先约定一下结点的叫法:
注意:R 是即将被替换到删除结点的位置的替换结点,在删除前,它还在原来所在位置参与树的子平衡,平衡后再替换到删除结点的位置,才算删除完成。
我们把替换结点换到了删除结点的位置时,由于替换结点为红色,删除也了不会影响红黑树的平衡,只要把替换结点的颜色变为删除的结点的颜色即可重新平衡。
处理:替换结点颜色变为删除结点的颜色。
当替换结点是黑色时,就必须进行自平衡处理了,我们可以通过区分替换结点是其父结点的左子结点还是右子结点,来做不同的旋转,使树重新平衡。
若兄弟结点是红结点,那么根据红黑树性质 4,兄弟结点的父结点和子结点肯定为黑色,按照下图方式处理,得到删除场景 2.1.2.3。
处理:
当兄弟结点为黑时,其父结点和子结点的具体颜色也无法确定,此时又得考虑多种子场景。
即将删除的左子树的一个黑色结点,显然左子树的黑色结点少 1 了,然而右子结点又是红色,那么我们直接向右子树“借”个红结点来补充黑结点,并进行旋转处理。如图所示:
处理:
兄弟结点所在的子树有红结点,又可以向兄弟子树“借”个红结点过来,这就转换回了场景 2.1.2.1。如图所示:
处理:
兄弟子树没有红结点可以“借”了,再向父结点“借”。如果父结点是黑色,为了让父结点在所在的子树中保证平衡(替换结点即将删除,少了一个黑色结点,子树也需要少一个)先把兄弟结点变为红色,再让父结点成为新的替换结点。
处理:
实际上是场景 2.1 的镜像操作。
处理:
处理
处理:
处理:
处理:
相较于插入操作,红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子,如果有两个孩子,不能直接删除该节点。而是要先找到该节点的前驱(该节点左子树中最大的节点)或者后继(该节点右子树中最小的节点),然后将前驱或者后继的值复制到要删除的节点中,最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点,这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题,问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点,只要节点里的值最终被删除就行了,至于树结构如何变化,这个并不重要。
红黑树删除操作的复杂度在于删除节点的颜色,当删除的节点是红色时,直接拿其孩子节点补空位即可。因为删除红色节点,性质5(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点)仍能够被满足。
当删除的节点是黑色时,那么所有经过该节点的路径上的黑节点数量少了一个,破坏了性质5。如果该节点的孩子为红色,直接拿孩子节点替换被删除的节点,并将孩子节点染成黑色,即可恢复性质5。但如果孩子节点为黑色,处理起来就要复杂的多。分为6种情况,下面会展开说明。
在展开说明之前,我们先做一些假设,方便说明。这里假设最终被删除的节点为X
(至多只有一个孩子节点),孩子节点为N
,X
的兄弟节点为S
,S
的左节点为 SL,右节点为 SR,接下来讨论是建立在节点 X
被删除,节点 N
替换X
的基础上进行的。这里说明把被删除的节点X
特地拎出来说一下的原因是防止大家误以为节点N
会被删除,不然可能看不明白。
在上面的基础上,接下来就可以展开讨论了。红黑树删除有6种情况,分别是:
N 是新的根。在这种情形下,我们就做完了。我们从所有路径去除了一个黑色节点,而新根是黑色的,所以性质都保持着。
上面是维基百科中关于红黑树删除的情况一说明,由于没有配图,看的有点晕。经过思考,我觉得可能会是下面这种情形:
要删除的节点 X 是根节点,且左右孩子节点均为空节点,此时将节点 X 用空节点替换完成删除操作。
S 为红色,其他节点为黑色。这种情况下可以对 N 的父节点进行左旋操作,然后互换 P 与 S 颜色。但这并未结束,经过节点 P 和 N 的路径删除前有3个黑色节点(P -> X -> N
),现在只剩两个了(P -> N
)。比未经过 N 的路径少一个黑色节点,性质5仍不满足,还需要继续调整。不过此时可以按照情况四、五、六进行调整。
N 的父节点,兄弟节点 S 和 S 的孩子节点均为黑色。这种情况下可以简单的把 S 染成红色,所有经过 S 的路径比之前少了一个黑色节点,这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点,此时需要从情况一开始对 P 进行平衡处理。
N 的父节点为红色,叔叔节点为黑色。节点 N 是 P 的右孩子,且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋,调整 N 与 P 的位置。接下来按照情况五进行处理,以恢复性质4。
这里需要特别说明一下,上图中的节点 N 并非是新插入的节点。当 P 为红色时,P 有两个孩子节点,且孩子节点均为黑色,这样从 G 出发到各叶子节点路径上的黑色节点数量才能保持一致。既然 P 已经有两个孩子了,所以 N 不是新插入的节点。情况四是由以 N 为根节点的子树中插入了新节点,经过调整后,导致 N 被变为红色,进而导致了情况四的出现。考虑下面这种情况(PR 节点就是上图的 N 节点):
如上图,插入节点 N 并按情况三处理。此时 PR 被染成了红色,与 P 节点形成了连续的红色节点,这个时候就需按情况四再次进行调整。
S 为黑色,S 的左孩子为红色,右孩子为黑色。N 的父节点颜色可红可黑,且 N 是 P 左孩子。这种情况下对 S 进行右旋操作,并互换 S 和 SL 的颜色。此时,所有路径上的黑色数量仍然相等,N 兄弟节点的由 S 变为了 SL,而 SL 的右孩子变为红色。接下来我们到情况六继续分析。
S 为黑色,S 的右孩子为红色。N 的父节点颜色可红可黑,且 N 是其父节点左孩子。这种情况下,我们对 P 进行左旋操作,并互换 P 和 S 的颜色,并将 SR 变为黑色。因为 P 变为黑色,所以经过 N 的路径多了一个黑色节点,经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径,则有以下两种情况:
红黑树删除的情况比较多,大家刚开始看的时候可能会比较晕。可能会产生这样的疑问,为啥红黑树会有这种删除情况,为啥又会有另一种情况,它们之间有什么联系和区别?和大家一样,我刚开始看的时候也有这样的困惑,直到我把所有情况对应的图形画在一起时,拨云见日,一切都明了了。此时天空中出现了4个字,原来如此、原来如此、原来如此。所以,请看图吧:
红黑树是一种重要的二叉树,应用广泛,但在很多数据结构相关的书本中出现的次数并不多。很多书中要么不说,要么就一笔带过,并不会进行详细的分析,这可能是因为红黑树比较复杂的缘故。我在学习红黑树的时候也找了很多资料,但总体感觉讲的都不太好。尤其是在我学习删除操作的时候,很多资料是实在人看不下去,看的我很痛苦。直到我看到维基百科上关于红黑树的分析时,很是欣喜。这篇文章分析的很有条理,言简意赅,比很多资料好了太多。本文对红黑树的分析也主要参考了维基百科中的红黑树分析,并对维基百科中容易让人产生疑问和误解的地方进行了说明。同时维基百科中文版红黑树文中的图片较为模糊,这里我重新进行了绘制。需要说明的是,维基百科中文版无法打开了,文中关于维基百科的链接都是英文版的。另外在给大家推荐一个数据结构可视化的网站,里面包含常见数据结构可视化过程,地址为:t.cn/RZFgryr。
另外,由于红黑树本身比较复杂,实现也较为复杂。在写这篇文章之前,我曾尝试过用 Java 语言实现红黑树的增删操作,最终只写出了新增节点操作,删除没做出来。而且自己写的新增逻辑实在太繁琐,写的不好看,没法拿出来 show。所以最后把 Java 中的 TreeMap 增删相关源码拷出来,按照自己的需求把源码修改了一下,也勉强算是实现了红黑树吧。代码放到了 github 上,传送门 -> RBTree.java。
最后,如果你也在学习红黑树,希望这篇文章能够帮助到你。另外,由于红黑树本身比较复杂,加之本人水平有限,难免会出一些错误。如果有错,还望大家指出来,我们共同讨论。
Balanced BinaryTree
平衡二叉树,又被称作VAL 树.特点:为一颗空树,或者它的左右两颗子树之前的高度差的绝对值不能超过1,并且左右两颗子树都是一颗平衡二叉树.
平衡二叉树一般是一个有序树,它具有二叉树的所有性质,其遍历操作和二叉树的遍历操作相同。但是由于其对二叉树施加了额外限制,因而其添加、删除操作都必须保证平衡二叉树的因子被保持。
指的是该节点的两个子树,即左子树和右子树的高度差.即用左子树的高度减去右子树的高度,如果该节点的某个子树不存在,则该子树的高度为0,如果高度差的绝对值超过1就要根据情况进行调整。
下图中:
1 | /** |
2 | * 平衡二叉树的节点 |
3 | * <br/> |
4 | * @author zbcn8 |
5 | * @since 2020/8/19 13:32 |
6 | */ |
7 | public static class Node<T>{ |
8 | |
9 | /** |
10 | * 节点值 |
11 | */ |
12 | private T val; |
13 | |
14 | /** |
15 | * 深度,这里计算每个结点的深度,通过深度的比较可得出是否平衡 |
16 | */ |
17 | private int depth; |
18 | |
19 | /** |
20 | * 父节点 |
21 | */ |
22 | private Node<T> parent; |
23 | |
24 | /** |
25 | * 左子树 |
26 | */ |
27 | private Node<T> left; |
28 | |
29 | /** |
30 | * 右子树 |
31 | */ |
32 | private Node<T> right; |
33 | |
34 | public Node(T val) { |
35 | this.val = val; |
36 | depth=0; |
37 | parent=null; |
38 | left= null; |
39 | right = null; |
40 | |
41 | } |
42 | } |
某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子(BF,Balance Factor)。平衡二叉树中不存在平衡因子大于 1 的节点,在一棵平衡二叉树中,节点的平衡因子只能取 0 (左右子树等高)、1(左子树比较高) 或者 -1(右子树比较高) ,分别对应着。
在新插入的结点向上查找,以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说,一棵失衡的树,是有可能有多棵子树同时失衡的。而这个时候,我们只要调整最小的不平衡子树,就能够将不平衡的树调整为平衡的树。
如下图:
上图中,增加99节点后,节点 66 的左子树高度为 1,右子树高度为 3,此时平衡因子为 -2,树失去平衡。
平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式,左旋 与 右旋 。
上图中:加入新节点 99 后, 节点 66 的左子树高度为 1,右子树高度为 3,此时平衡因子为 -2。为保证树的平衡,此时需要对节点 66 做出旋转,因为右子树高度高于左子树,对节点进行左旋操作。
如下图:
右旋操作与左旋类似,
如下图:
插入方式 | 描述 | 旋转方式 |
---|---|---|
LL | 在 A 的左子树根节点的左子树上插入节点而破坏平衡 | 右旋转 |
RR | 在 A 的右子树根节点的右子树上插入节点而破坏平衡 | 左旋转 |
LR | 在A的左子树根节点的右子树上插入节点而破坏平衡 | 先左旋后右旋 |
RL | 在 A 的右子树根节点的左子树上插入节点而破坏平衡 | 先右旋后左旋 |
RL | 在 A 的右子树根节点的左子树上插入节点而破坏平衡 | 先右旋后左旋 |
在结点的左孩子的左子树中插入数据。
1 | /** |
2 | * 右旋 |
3 | * @param node |
4 | * @return |
5 | */ |
6 | public Node<T> rotateRight(Node<T> node){ |
7 | //获取左儿子 |
8 | Node<T> left = node.getLeft(); |
9 | //将左儿子的右儿子("拖油瓶"结点)链接到旋转后的node的左链接中 |
10 | node.setLeft(left.getRight()); |
11 | // 调转node和它左儿子的父子关系,使node成为它原左儿子的右子树 |
12 | left.setRight(node); |
13 | // 更新并维护受影响结点的height |
14 | node.setHeight(max(height(node.getLeft()), height(node.getRight()))+1); |
15 | // 更新并维护受影响结点的height |
16 | left.setHeight(max(height(left.getLeft()),height(left.getRight()))+1); |
17 | return left; |
18 | } |
只需要执行一次左旋即可。
1 | /** |
2 | * 左旋 |
3 | * @param node |
4 | * @return |
5 | */ |
6 | public Node<T> rotateLeft(Node<T> node){ |
7 | //获取右儿子 |
8 | Node<T> right = node.getRight(); |
9 | //将右儿子的左儿子("拖油瓶"结点)链接到旋转后的node的右侧链接中 |
10 | node.setRight(right.getLeft()); |
11 | //调转node 节点和它右侧儿子的父子关系,使node 成为它原右生儿子的左子树 |
12 | right.setLeft(node); |
13 | node.setHeight(max(height(node.getRight()),height(node.getLeft()))+1); |
14 | right.setHeight(max(height(right.getLeft()),height(right.getRight()))+1); |
15 | return right; |
16 | } |
若 A 的左孩子节点 B 的右子树 E 插入节点 F ,导致节点 A 失衡
需要执行两步操作,使得旋转之后为 原来根结点的左孩子的右孩子作为新的根节点,即E作为根节点
也就是说,经过这两步操作,使得 原来根节点的左孩子的右孩子 E 节点成为了新的根节点。
由于在a的左子树根结点的右子树上插入结点(LR), 导致a的平衡因子由1变成2,导致以a为根结点的子树失去平衡,需要进行两次旋转, 先左旋后右旋
若 A 的右孩子节点 C 的左子树 D 插入节点 F ,导致节点 A 失衡,
要执行两步操作,使得旋转之后为 原来根结点的右孩子的左孩子作为新的根节点 。
经过这两步操作,使得 原来根节点的右孩子的左孩子 D 节点成为了新的根节点。
由于在a的右子树根结点的左子树上插入结点(RL), a的平衡因子由-1变成-2,导致以a为根结点的子树失去平衡, 则需要进行两次旋转,先右旋后左旋
VL 树和二叉查找树的删除操作情况一致,都分为四种情况:
AVL 树在删除节点后需要重新检查平衡性并修正,同时,删除操作与插入操作后的平衡修正区别在于,插入操作后只需要对插入栈中的弹出的第一个非平衡节点进行修正,而删除操作需要修正栈中的所有非平衡节点。
对于删除操作造成的非平衡状态的修正,可以这样理解:对左或者右子树的删除操作相当于对右或者左子树的插入操作,然后再对应上插入的四种情况选择相应的旋转就好了。
具体数字演示:
树有多个节点(node),用以储存元素。某些节点之间存在一定的关系,用连线表示,连线称为边(edge)。边的上端节点称为父节点,下端称为子节点。树像是一个不断分叉的树根。
没有任何父节点的节点:最顶层的节点被称为根(root)节点
没有任何子节点的节点被称为叶子节点(leaf node)或者终端节点(terminal node)。
最深的叶节点与根节点之间的距离(即边的数量)
A
为根节点的树 的高度是 3。I
为根节点的树 的高度是 0(子树也是树,I 的度是指 I 为根节点的子树的度)。深度(Depth)或者层次(level)是节点与根节点的距离。
H
的层次是 2。B
的层次是 1。tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true