发表于 | 分类于 
//应用缓存API是否可用，默认值false, 结合setAppCachePath(String)使用。
s.setAppCacheEnabled(true);

//设置应用缓存文件的路径。
s.setAppCachePath("");

// 设置是否允许通过 file url 加载的 Javascript 可以访问其他的源(包括http、https等源)
//4.1以后默认禁止
s.setAllowUniversalAccessFromFileURLs(false);

// 设置是否允许通过 file url 加载的 Js代码读取其他的本地文件
//4.1以后默认禁止
s.setAllowFileAccessFromFileURLs(true);

// 是否允许访问文件，默认允许。注意，这里只是允许或禁止对文件系统的访问
// Assets 和 resources 文件使用file:///android_asset和file:///android_res仍是可访问的。
s.setAllowFileAccess(true);
阅读全文 »

发表于 | 分类于

如何理解图

图是一种 非线性表数据结构,和树比起来,更加复杂.图中的元素我们叫做顶点.图中的一个顶点与任意其他顶点建立连接关系,我们把建立的关系叫做边.

社交网络就是一个非常典型的图结构.以微信举例,把每个用户看成一个顶点.如果两个用户加好友,那就在两者之间建立一条边.所以,整个微信的好友关系就可以用一张图来表示.其中每个用户有多少好友,对应到图中,就叫做顶点的度,就跟顶点相连的边的条数.

我们可以把上边的图结构改造一下,引入边的”方向”的概念.我们把这种边有方向的图叫做“有向图”,边没有方向的叫做“无向图”.

在有向图中,把度分为入度和出度.顶点的入度表示有多少条边指向这个顶点;顶点的出度表示有多少条边以这个顶点为起点指向其他顶点.

如果边带有权重,那这种图就叫做带权图,例如QQ好友的亲密度.

存储图

邻接矩阵存储

图最直观的一种存储方法就是,邻接矩阵.

邻接矩阵的底层依赖的是一个二维数组.对于无向图来说,如果顶点i与顶点j之间有边,我们就将 A[i][j] 和 A[j][i] 标记为 1; 对于有向图来说,如果有一条箭头从顶点 i 指向顶点 j 的边,那我们就将 A[i][j] 标记为 1 . 同理,如果有一条箭头从顶点 j 指向顶点 i 的边,那我们就将 A[j][i] 标记为1. 对于权重图,数组中就存储响应的权重.

用邻接矩阵表示一个图,虽然简单直观,但是比较浪费内存空间.

对于无向图来说,如果 A[i][j] 为1, 那么 A[j][i] 也肯定等于 1.实际上我们只需要存储一个就可以了.

如果我们存储的是稀疏图,也就是说顶点很多但每个顶点的边不多,那邻接矩阵的存储方法就更加浪费空间了.

邻接表存储

邻接表存储方式如图.每一个顶点都对应一条链表,链表中存储的是与这个顶点相连的其他点.图中画的是一个有向图,每个顶点对应的链表里面,存储的是指向的顶点.

//TODO 图33

邻接表存储比较节省空间,但是使用起来就比较耗时.但是我们可以将链表改成平衡二叉树.实际开发中,还可以选择红黑树.这样我们就可以更快的查找两个顶点之间是否存在边.

深度和广度优先搜索

在社交网络中有一个六度分割理论,具体的说,你与世界上的另一个的间隔的关系不会超过六度,也就是说平均只需要六步就可以联系到任何两个不认识的人.

一个用户的一度链接用户,就是他的好友.二度链接用户就是他好友的好友.三度链接好友就是他好友的好友的好友.在社交网络中,我们往往通过用户之间的链接关系,来实现推荐”可能认识的人”这么一个功能.

什么是”搜索”算法

算法是作用于具体数据结构上的,深度优先搜索算法和广度优先搜索算法都是基于”图”这种数据结构.这是因为,图这种数据结构表达能力很强,大部分设计搜索的场景都可以抽象成图.

图上的搜索算法,最直接理解的就是,在图中找出从一个顶点出发,到另一个 顶点的路径.具体方法有很多.比如最”暴力”的深度优先,广度优先,还有A, IDA 等启发式搜索算法.

今天我们会用邻接表来存储图.深度优先和广度优先算法既可以用在无向图,可以用在有向图上.今天都是以无向图来讲解.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//无向图
public class Graph{
	private int v; //顶点个数
	private LinkedList<Integer> adj[]; //邻接表

	public Graph(int v){
		this.v = v;
		adj = new LinkedList[v];
		for(int i=0; i<v; i++){
			adj[i] = new LinkedList<>();
		}
	}

	public void addEdge(int s, int t){ //无向图一条边存两次
		adj[s].add(t);
		adj[t].add(s);
	}
}

广度优先搜索 (BFS)

广度优先搜索(Breadth-First-Search),它就是一种”地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索.如图

//TODO 图34

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public void bfs(int s, int t){
	if(s == t) return;
	boolean[] visited = new boolean[v];
	visited[s] = true;
	Queue<Integer> queue = new LinkedList<>();
	queue.add(s);
	int[] prev = new int[v];
	for(int i=0; i<v; i++){
		prev[i] = -1;
	}

	while(queue.size() != 0){
		int w = queue.poll();
		for(int i=0; i < adj[w].size(); i++){
			int q = adj[w].get(i);
			if(!visited[q]){
				prev[q] = w;
				if(q == t){
					print(prev, s, t);
					return;
				}
				visited[q] = true;
				queue.add(q);
			}
		}	
	}
}

//递归打印s->t的路径
private void print(int[] prev, int s, int t){
	if(prev[t] != -1 && t != s){
		print(prev, s, prev[t]);
	}
	System.out.print(t + " ");
}

这里的bfs()方法就是图的广度优先搜索的代码实现,其中s表示起始顶点,t 表示终止顶点.我们搜索一条s到t 的路径.实际上这样求得的路径就是最短路径.

这段代码里有三个重要的变量 visited, queue, prev.

visited是用来标记已经访问到的顶点,用来避免重复访问.

queue是一个队列,用来存储已经被访问,但相连的顶点还没有被访问的顶点.因为广度优先是逐层访问的,也就是说我们只有把第k层的顶点都访问完成之后,才能访问第k + 1 层的顶点.当我们访问到第k层顶点的时候,我们需要把第看层的顶点记录下来稍后才能通过k层顶点来找k+1层的顶点.

prev用来记录搜索路径.当我们从s点开始,广度优先搜索到t后,prev中存储的就是搜索路径.不过这个路径是反向存储的.prev[w] 存储的是,顶点w是从哪个前驱顶点遍历过来的.比如当我们通过顶点2的邻接表访问到顶点3,那prev[3]就等于2.为了正向打印出路径,我们需要递归来打印.

广度优先分解图如下:

//TODO 图35,36,37

最坏情况下终止顶点t 离起始顶点 s 很远,需要遍历整个图才能找到.这个时候每个顶点都要进出一遍队列,每个边也会被访问一次,所以广度搜索的时间复杂度是O(V+E).其中V表示顶点个数,E表示边的个数.对于一个连通图来说,也就是说一个图中所有顶点都是连通的,E肯定要大于等于V-1,所以说时间复杂度也可以简写为O(E).

广度优先搜索的空间消耗主要在visited数据,queue队列,prev数组上,这三个存储的空间的大小不会超过顶点个数,所以空间复杂度是O(V).

深度优先搜索(DFS)

深度优先搜索,最直观的例子就是走迷宫.

//TODO 图38

搜索的起始顶点是 s ,终止顶点是 t ,我们希望从图中找到一条顶点 s 到 顶点 t 的路径.我用深度递归算法把整个搜索路径标记出来了.这里面实线箭头表示遍历,虚线箭头表示回退.

实际上深度优先算法是一种比较著名的算法思想,回溯思想.这种思想解决问题的过程非常适合用递归来实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
boolean found = false; // 全局变量或者类成员变量

public void dfs(int s, int t){
	found = false;
	boolean[] visited = new boolean[v];
	int[] prev = new int[v];
	for(int i=0; i<v; i++){
		prev[i] = -1;
	}
	recurDfs(s, t, visited, prev);
	print(prev, s, t);
}

public void recurDfs(int w, int t, boolean[] visited, int[] prev){
	if(found) return;
	visited[w] = true;
	if(w == t) {
		found = true;
		return;
	}
	for(int i=0; i<adj[w].size(); i++){
		int q = adj[w].get(i);
		if(!visited[q]){
			prev[q] = w;
			recurDfs(q, t, visited, prev);
		}
	}
}

深度优先算法代码实现也用到了 visited, prev 变量,它们跟广度优先算法中的作用是一样的.不过深度优先算法有个一个特殊变量found,用来标识是否找到终点 t ,然后结束递归.

深度优先算法的时间复杂度是O(E).空间复杂度是O(V).

发表于 | 分类于

介绍

“堆”(Heap) 是一种特殊的树,它的应用场景非常多,最经典的莫过于堆排序.堆排序是一种原地的,时间复杂度为O(nlogn)的排序算法.

如何理解”堆”

什么样的树才是堆?需要满足两点要求:

  • 堆是一个完全二叉树
  • 堆中的每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值

对于每个节点的值都大于等于子树中每个节点的值的堆,我们叫做”大顶堆”;对于每个节点的值都小于等于子树中每个节点的值的堆,我们叫做”小顶堆”.

//TODO 图25

其中1,2是”大顶堆”,3是”小顶堆”,4不是堆.对于同一种数据,我们可以构建不同的堆形态.

如何实现一个堆

完全二叉树比较适合用数组来存储,如图一个用数组存储堆的例子:

//TODO 图26

从图中可以看到,数组中下标为i的节点的左子节点,就是下标为i 2的节点,又子节点就是下标为i 2 + 1的节点,父节点就是下标为i/2的节点.

往堆中插入一个元素

往堆中插入一个元素后,我们需要满足堆的两个要求.

如果我们把新插入的元素放到堆的最后,如图,已经不符合堆的特性了,于是我们需要进行调整,让其重新满足特性这个过程就叫堆化.

//TODO 图27

堆化有两种方式,从下往上和从上往下.

堆化_从下往上

堆化非常简单就是顺着节点所在的路径向上或者向下,对比,然后交换.

我们可以让新插入的节点与父节点比较大小.如果不满足子节点小于等于父节点的要求,我们就互换两个节点.一直重复这个过程,直到父子节点之间的关系满足.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Heap{
	private int[] a; //数组a,从下标1开始存储数据
	private int n;   //堆可以存储的最大数据
	private int count; //堆中已经存在的数据个数

	public Heap(int capacity){
		a = new int[capacity + 1];
		n = capacity;
		count = 0;
	}

	public void insert(int data){
		if(count >= n) return;
		++count;
		a[count] = data;
		int i = count;
		while(i/2 > 0 && a[i] > a[i/2]){
			swap(a, i, i/2); //用于交换下标为 i 和 i/2 的两个元素
			i = i/2;
		}
	}
}

删除对顶元素

从堆的第二条定义中,任何节点的值都大于等于(或小于等于)子树节点的值,我们可以发现堆顶元素存储的就是最大值或最小值.

假设我们构造的是大顶堆,堆顶元素就是最大元素,当我们删除堆顶元素后,就需要把第二大元素放在堆顶,那第二大元素肯定会出现在左右子节点中.然后我们再迭代的删除第二大节点,以此类推直到叶子节点被删除.不过这种方法有点问题,就是最后堆化出来的堆并不满足完全二叉树的特性.

实际上,我们需要改变一下思路,来解决这个问题.我们把最后一个节点放在堆顶,然后利用同样的父子节点对比方法.对于不满足父子节点大小关系的,互换两个节点,并且重复执行这个过程,直到父子节点满足大小关系为止.这就是从上往下的堆化方法.

//TODO 图28

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void removeMax(){
	if(count == 0) return;
	a[1] = a[count];
	--count;
	heapify(a, count, 1);
}

public void heapify(int[] a, int n, int i){
	while(true){
		int maxPos = i;
		if(i*2 <= n && a[i] < a[i*2]) maxPos = i * 2;
		if(i*2+1 <=n && a[maxPos] < a[i*2+1]) maxPos = i*2 +1;
		if(maxPos == i) break;
		swap(a, i, maxPos);
		i = maxPos;
	}
}

我们知道,一个包含n个节点的安全二叉树,树的高度不会超过$$log_2n$$.堆化的过程是顺着节点所在的路径来比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是O(logn).插入数据和删除堆顶数据主要逻辑就是堆化,所以往堆中插入一个数据和删除堆顶数据的时间复杂度都是O(logn).

如何基于堆实现排序

我们可以把堆排序的过程大致拆分成两个步骤,建堆和排序.

建堆

我们首先将数组原地建成一个堆.建堆过程有两种思路.

第一种就是借助插入元素的思路.尽管数组中包含n个数据但是我们可以假设,起初堆中只包含一个数据,就是下标为1的数据,然后我们调用插入操作,将下标从2到n的数据依次插入到堆中.

第二种跟第一种截然相反.第一种建堆思路的处理过程是从前往后处理数组数据,并且每个数据插入堆中时,都是从下往上堆化.而第二种是从后往前处理数组,并且每个数据都是从上往下堆化.

//TODO 图29,30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void buildHeap(int[] a, int n){
	for(int i = n/2; i >= 1; --i;){
		heapify(a, n, i);
	}
}

private static void heapify(int[] a, int n, int i){
	while(true){
		int maxPos = i;
		if(i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
		if(i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
		if(maxPos == i) break;
		swap(a, i, maxPos);
		i = maxPos;
	}
}

这段代码中,我们队下标从n/2开始到1的数据进行堆化,下标是 n/2+1 到 n 的节点是叶子节点我们不需要堆化,实际上对于完全二叉树来说,下标从 n/2+1 到 n 的节点都是叶子节点

建堆的时间复杂度是O(n);

排序

建堆完成后,数组中的数据已经是按照大顶堆的特性来组织的.数组的第一个元素就是堆顶,也是最大元素.我们把它跟最后一个数组交换,那最大元素就放到了下标为n的位置.

这个过程有点类似”删除堆顶的操作”,当堆顶元素移除之后,我们把原先下标为n的元素放到堆顶,然后再通过堆化方法,将剩下n-1个数据重新构成堆.重复此过程,直到最后堆中只剩下下标为1的一个元素,排序就完成了.

//todo 图31

1
2
3
4
5
6
7
8
9
10
//n表示数据的个数,数组a 中的数据从下标1到n的位置
public static void sort(int[] a, int n){
	buildHeap(a,n);
	int k = n;
	while(k > 1){
		swap(a,1,k);
		--k;
		heapify(a,k,i);
	}
}

整个排序过程中,都只需要极个别的临时存储空间,所以堆排序是原地排序算法.堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是O(n),排序过程的时间复杂的度是O(nlogn),所以堆排序整体的时间复杂度是O(nlogn).

堆排序不是稳定的排序算法,因为在排序的过程中,存在将堆的最后一个节点跟堆顶节点互换的操作.

实际开发中为什么快速排序比堆排序性能好

堆排序数据访问的方式没有快速排序友好.

对于快速排序来说,数据是顺序访问的而对于堆排序来说,数据是跳着访问的.

对于同样的数据,堆排序算法的交换次数要多余快速排序

堆的应用

应用一: 优先级队列

优先级队列.首先,它是一个队列,队列的最大的特性就是先进先出.不过在优先级队列中数据的出队顺序不是先进先出,而是按照优先级来,优先级最高的优先出队.

用堆来实现优先级队列是最直接,最高效的,这是因为堆和优先级队列非常相似.一个堆就可以看作一个优先级队列.它们只是概念上的区分而已.往优先级队列中插入一个元素就相当于往堆中插入一个元素;从优先级队列中取出优先级最高的元素,就相当于取出栈顶元素.

优先级队列的应用场景非常多.比如,赫夫曼编码,图的最短路径,最小生成树的算法等.不仅如此,很多语言中,都提供了优先级队列的实现,比如Java中的PriorityQueue,C++中的priority_queue.

合并有序小文件

假设有100个小文件,每个文件的大小都是100MB,每个文件中存储的都是有序字符串.我们希望将这100个文件合并成一个有序的大文件.这就需要用到优先级队列.

整体思路有点像归并排序中的合并函数.我们从这100个文件中各取第一个字符串放入数组中,然后比较大小,把最小的字符串放入合并后的大文件中,并从数组中删除.

假设,这个最小字符串来自于13.txt这个文件,我们就再从这个小文件取下一个字符串,并且放到数组中,重新比较大小,并且选择最小的放入合并后的大文件,并将它从数组中删除.依次类推,直到所有文件中的数据都放入到大文件为止.

这里我们用的是数组这种数据结构,来完成上述操作,显然这不是很高效.怎样提高效率呢?

这就可以使用优先队列,也可以说是堆.我们将从小文件中取出的字符串放入到小顶堆中,那堆顶的元素,也就是优先级队列队首的元素,就是最小的字符串,我们将这个字符串放入到大文件中,并将其从堆中删除.然后再从小文件中,取下一个字符串,放入堆中.循环这个过程就可以将100个小文件合并成一个大文件.

高性能定时器

假设我们有一个定时器,定时器中维护了多个定时任务,每个定时任务设置了一个要触发执行的时间点.定时器每过一个很小的单位时间(比如1秒),就扫描一遍任务,看是否有任务到达了执行的时间,如果有就执行.

但是,这样每过一秒就扫描一遍任务列表的做法比较低效.主要原因有两点,第一,任务约定的执行时间离当前时间可能还要很久,这样前面多次的扫描都是徒劳的;第二每次都要扫描整个任务列表,如果列表很大的话,比较耗时.

针对上边这些问题,我们可以用优先级队列来解决.我们按照任务设定的执行时间,将这些任务存储在优先级队列中,队列首部(也就是小顶堆的堆顶)存储的是最先执行的任务.

这样,定时器就不需要每隔1秒就扫描一遍任务列表了.它拿队首任务的执行时间点,与当前时间点,相减,得到一个时间间隔T.

这个时间间隔T就是,从当前时间开始,需要等待多久,才会有第一个任务需要被执行.这样定时器就可以设定在T秒之后,再来执行任务.从当前时间点(T-1)秒这段时间里,定时器都不需要做任何事.

当T秒时间过去后,定时器取优先级队列队首的任务执行.然后再计算新的队首任务的执行时间间隔与当前时间的差值,把这个值作为定时器执行下一个任务需要等待的时间

应用二: 利用堆求TopK

我们把求TopK的问题分成两类.一类是针对静态数据集合,也就说数据集合提前确定,不会改变.另一类是针对动态数据集合.

针对静态数据,如何在一个包含n个数据的数组中,查找前k大数据呢?我们维护一个大小为K的小顶堆,顺序遍历数组,从数组中取出数据与堆顶元素比较.如果比堆顶元素大,我们就把堆顶元素删除,并且将这个元素插入到堆中;如果比堆顶元素小,则不出理,继续遍历数组.

遍历数组的时间复杂度是O(n),一次堆化操作的时间复杂度是O(logK),所以最坏的情况下,n个元素都入堆一次,时间复杂度是O(nlogk).

针对动态数据求TopK.例如一个数据集合中有两个操作,一个是添加操作,一个是询问当前K大数据.

如果每次询问K大数据,我们都基于当前数据计算的话,那时间复杂度就是O(nlogK),n表示当前数据的大小.实际上我们可以一直维护一个K大小的小顶堆,当有数据添加到集合中时,我们就拿它与堆顶元素对比.如果比堆顶元素大,我们就把堆顶元素删除,并且将这个元素插入到堆中;如果比堆顶元素小,则不做处理.这样无论何时何时查询当前K大数据,我们都可以立即返回.

应用三: 求中位数

中位数,就是处在中间位置的那个数.如果数据的个数是奇数,把数据从小到大排列那第 n/2 + 1 个数据就是中位数.如果是偶数,那出于中间位置的有两个,第 n/2 和第 n/2+1 个数据,这时候可以任意取一个作为中位数.

对于一组静态数据,中位数是固定的,先排序,第 n/2 个数就是中位数,每次询问中位数,直接返回这个值就好了.所以,尽管排序的的代价比较大,但是边际成本会很小.

对于动态数据,中位数在不停的变动,如果还是先排序的方法,那每次询问中位数,都要先排序,那效率就不高了.

借助堆这种数据结构,我们不用排序,就可以非常高效的实现求中位数操作.

我们维护两个堆,一个大顶堆,一个小顶堆.大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆的数据都要大于大顶堆中的数据.

也就是说n个数据,n是偶数,我们从小到大排序,那前 n/2 个数据存储在大顶堆中,后 n/2 个数据存储在小顶堆中.这样大顶堆中的堆顶元素就是我们要找的中位数.如果n是奇数,情况类似,大顶堆中就存储 n/2+1 个数据,小顶堆中就存储 n/2 个数据.

我们前面也提到,数据是动态变化的,当新添加一个数据之后,我们如何调整这两个堆呢.

如果新加入的数据小于等于大顶堆的堆顶元素,我们就将这个数据插入到大顶堆;如果新添加的数据大于等于小顶堆的堆顶元素,就将这个数据插入到小顶堆.

这个时候,就会出现,两个堆中的数据个数不符合前面的约定情况.这个时候我们可以从一个堆中不停的将堆顶元素移动到另一个堆.

//TODO 图32

于是我们就用两个堆,一个大顶堆,一个小顶堆,实现在动态集合中求中位数的操作.插入数据因为涉及堆化,时间复杂度就变成了O(logn),但求中位数,我们只需要返回大顶堆的堆顶数据就行,时间复杂度是O(1).

实际上,利用两个堆还可以求出其他百分位的数据,原理类似求中位数.例如如何快速求接口的99% 响应时间

发表于 | 分类于

前言

二叉树在频繁的动态更新中,可能会出现树的高度远大于$$log_2n$$的情况,极端情况下,二叉树会退化成链表,各个操作效率下降.我们需要设计一种平衡二叉查找树,来结局这个问题

什么是平衡二叉查找树

严格定义是这样的:二叉树中任意一个节点的左右子树高度相差不能大于1.

从这个定义来看,满二叉树和完全二叉树都是平衡二叉树.非完全二叉树也有可能是平衡二叉树.

但是很多平衡二叉查找树其实并没有符合上面的定义,为了实际应用,没必要死抠定义,主要是解决问题.所以,平衡二叉查找树中”平衡”的意思其实就是让整个树左右看起来比较”对称”,比较”平衡”,不要出现左子树很高,右子树很矮的情况.这就让整个树高度相对低一些,提高操作效率

如何定义一个”红黑树”

红黑树的节点,一类被标记为黑色,一类被标记为红色.除此之外还要满足以下几个要求:

  • 根节点是黑色的
  • 每个叶子节点都是黑色的空节点,也就是说叶子节点不存储数据
  • 任何相邻的节点都不能同时为红色,也就是说红色节点是被黑色节点隔开的
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点.

上面”叶子节点都是黑色的空节点”,主要是为了简化红黑树代码而设置的.

为什么说红黑树是”近似平衡”

平衡的意思可以等价为性能不退化.”近似平衡”就等价位性能退化不会太严重.

二叉树的很多操作性能都跟树的高度成正比.一棵及其平衡的二叉树的高度大约是$$log_2n$$,所以要证明红黑树是近似平衡的,我们只需要分析红黑树的高度是否比较稳定的趋近$$log_2n$$就好了.

我们来分析一下红黑树的高度.

首先,我们来看,如果将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度是多少呢?

红色节点删除之后,有些节点就没有负节点了,它们会直接拿这些节点的祖父节点作为父节点,所以之前的二叉树,就变成了四叉树.

//todo 图20

前面红黑树定义中有一条:从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点.我们从四叉树中取出某些节点放到节点位置,四叉树就变成了完全二叉树.所以仅包含黑色节点的四叉树高度,比包含相同节点数的完全二叉树的高度还要小.

完全二叉树的高度近似$$log_2n$$,这里的四叉黑树的高度低于完全二叉树,所以去掉黑色节点的黑树的高度也不会超过$$log_2n$$.

那现在把红色节点加回去,高度会变成多少呢?

在红黑树中,红色节点不能相邻,也就是说,有一个红色节点就至少要有一个黑色节点,将它跟其他红色节点隔开.红黑树中包含最多黑色节点的路径不会超过$$log_2n$$,所以加入红色节点后不会超过$$2log_2n$$,也就是说红黑树的高度近似$$2log_2n$$.

实现红黑树的基本思想

红黑树平衡的大致过程就是:遇到什么样的节点排布,我们就对应怎么调整.只有按照这些固定规则来操作,就能将一个非平衡的红黑树调整成平衡的.

在插入和删除节点的过程中,红黑树的第三,第四点要求可能会被破坏.”平衡调整”实际上就是把被破坏的第三,第四点恢复过来.

有两个非常重要的操作<左旋(rotate left),右旋(rotate right).左旋的全称是围绕某个节点的左旋.右旋的全称是围绕某个节点的右旋.

//TODO 图21

插入的平衡操作

红黑树规定,插入的节点必须是红色的.而且,二叉查找树中新插入的节点都是放在叶子节点上.所以,关于插入操作的平衡,有两种特殊情况.

  • 如果插入的节点的父节点是黑色的,那我们什么都不用做,它仍满足红黑树的定义.
  • 如果插入的节点是根节点,那我们直接改变他的颜色,变成黑色就可以了.

除此之外,其他情况都会违背红黑树的定义,需要进行调整,调整的过程包含两种操作:左右旋转和改变颜色.

红黑树的平衡是一个迭代过程,我们把正在处理的节点叫作关注节点.关注节点会随着不停的的迭代处理,而不断发生变化.最开始的关注节点就是新插入的点.

新节点插入之后,如果平衡被打破,那一般会有三种情况.我们根据每种情况不停的调整,就可以让红黑树继续符合定义.

为了简化描述,把父节点的兄弟节点叫作叔叔节点,父节点的父节点叫作祖父节点.

CASE1:如果关注节点是a,它的叔叔节点d是红色,我们依次执行下面操作:

  • 将关注节点a的父节点b,叔叔节点d的颜色都设置成黑色;
  • 将关注节点a的祖父节点c的颜色设置成红色;
  • 关注节点变成a的祖父节点c;
  • 调到CASE2或者CASE3

//TODO 图22

CASE2: 如果关注节点a,它的叔叔节点d是黑色,关注节点a是其父节点b的右子节点

我们就执行下面操作

  • 关注节点变成节点a的父节点b;
  • 围绕新的关注节点b左旋;
  • 跳到CASE3.

//TODO 图23

CASE 3:如果关注节点是a,它的叔叔节点是黑色,a是其父节点的左子树节点.

我们进行如下操作

发表于 | 分类于

先了解树

“树”这种数据结构类似生活中的”树”,里面的每个元素叫做”节点”;用来连线相邻两个节点之间的关系,我们叫作”父子关系”.

在如下图中,A节点就是B节点的父节点,B节点是A节点的子节点.B,C,D这三个节点的父节点是同一个节点,所以称它们为兄弟节点.我们把没有父节点的节点叫作根节点,也就是图中的E.我们把没有子节点的节点叫作叶子节点或叶结点,比如图中的H,G,I,J,K,L都是叶子节点.

阅读全文 »

发表于 | 分类于

哈希算法

将任意长度的二进制串映射为固定长度的二进制串,这个映射规则就是哈希算法,而通过原始数据映射之后得到的二进制串就是哈希值.设计一个哈希算法需要满足几点要求:

阅读全文 »

发表于 | 分类于

散列表

散列表英文名是”Hash Table”,我们平时也叫”哈希表”或者”Hash 表”.

散列表用的是数组支持按照下标随机访问的特性,所以散列表其实就是数组的一种扩展,由数组演化而来.
阅读全文 »