树相关算法：AVL 树、红黑树、B/B+ 树_avl 红黑树 b树 b+树

AVL 树

核心

• 必须保证每个节点左子树和右子树高度差值 <= 1

• 只有四种旋转（即四种情况）

  • 右子树高 ：
    H（node.right.left） - H（node.right-right） = 1 --> RL 旋转
    H（node.right.right） - H（node.right-left） = 1 --> L 旋转
  • 左子树高：
    H（node.left.right） - H（node.left-left） = 1 --> LR 旋转
    H（node.left.left） - H（node.left-right） = 1 --> R 旋转

• 算法步骤

  • 1、从被添加节点，然后一直往上走，直到走到 root
  • 2、每次上升到一个节点 node，就比较一下当前节点左子树和右子树的高度，如果满足 |node.left - node.right| > 1 时，就按照上面四种情况判断，到底应该是哪种旋转。

• 应用场景

  • 对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。

四种旋转

左子树高
示例：插入 7

示例：插入 9

右子树高
示例：插入 28

示例：插入 18

红黑树

核心

• 两条核心性质

  • 两个红色节点不可以连续
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。（叶子节点均指nil叶子）

• 最后一条性质确保：没有一条路径会比其他路径长出2倍。因而，红黑树是相对接近平衡的二叉树

  • 因为每次新插入的一个节点都是红色节点（起始时根节点为黑色），所以只要保证每个父子节点不同时为红色，那么就可以保证每条路径都是红黑节点交替，从而满足任何一个节点到叶节点经过的黑色节点数相同，也保证高度差一定在 2 倍以内。

• 算法核心

  • 每次插入一个节点，把父节点变黑，再把祖父变红，然后把父节点旋转成祖父即可（即此时祖父还是黑色，但不存在冲突了）
  • 要解决的问题一：叔叔节点是红色时，无法把祖父变红，不然就红色连续了。
    处理策略：把叔叔一起变黑，再让祖父变为当前节点，然后按照上面的核心思想调整祖父，解决祖父变红的冲突。
  • 要解决的第二个问题：红黑树只有 L 旋转与 R 旋转，所以我上面说的把父节点变黑，然后转为祖父的前提必须是，子节点和父节点在同一个方向。
    处理策略：先以父节点进行一次旋转，把插入节点转到同向

应用示例

• Linux 进程调度的完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间;
• IO多路复用的epoll的的的实现采用红黑树组织管理的的的sockfd，以支持快速的增删改查;
• Java的的的中TreeMap中的中的实现;

算法实现

两种旋转

右旋

左旋

插入的三种情况

case 1： 当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。

• 对策：将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点重新开始算法
  

case 2： 当前结点的父结点是红色，叔叔（假设叔叔是祖父的右子）结点是黑色，当前结点是其父结点的右子。

• 对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋
  

case 3： 当前结点的父结点是红色，叔叔（假设叔叔是祖父的右子）结点是黑色，当前结点是其父结点的左子。

• 对策：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋
• 最终目的都是转换为这种情况
  

代码

int rb_insert_fixup(rb_tree_t *root, rb_node_t *node)
{
	rb_node_t *parent;
	rb_node_t *grand_parent;

	//If parent exist, and the color of parent is RED
	while((parent = node->parent) && parent->color == COLOR_RED)
	{
		grand_parent = parent->parent;

		//parent node is grand_parent node's left child(grand_parent should not be NULL, because parent->color==COLOR_RED)
		if(grand_parent->left == parent)
		{
			rb_node_t *uncle = grand_parent->right;

			//Case 1: uncle is RED
			if(uncle && uncle->color == COLOR_RED)
			{
				parent->color = COLOR_BLACK;
				uncle->color = COLOR_BLACK;
				grand_parent->color = COLOR_RED;
				
				node = grand_parent;
				continue;
			}

			//Case 2: uncle is BLACK, and node is parent's right child
			if(parent->right == node)
			{
				rb_rotate_left(root, parent);
				
				// reset parent and node pointer
				rb_node_t *tmp;
				tmp = parent;
				parent = node;
				node = tmp;
				
				//Here successful convert Case 2 to Case3
			}

			//Case 3: uncle is BLACK, and node is parent's left child
			parent->color = COLOR_BLACK;
			grand_parent->color = COLOR_RED;
			rb_rotate_right(root, grand_parent);

		}
		else{
			rb_node_t *uncle = grand_parent->left;
			
			//Case 1: uncle is RED
			if(uncle && uncle->color == COLOR_RED)
			{
				parent->color = COLOR_BLACK;
				uncle->color = COLOR_BLACK;
				grand_parent->color = COLOR_RED;
				
				node = grand_parent;
				continue;
			}

			//Case 2: uncle is BLACK, and node is parent's left child
			if(parent->left == node)
			{
			rb_rotate_right(root,parent);
			
				//reset parent and node pointer
				rb_node_t *tmp;
				tmp = parent;
				parent = node;
				node = tmp;
				
				//Here success convert Case 2 to Case 3
			}

			//Case 3: uncle is BLACK, and node is parent's right child
			parent->color = COLOR_BLACK;
			grand_parent->color = COLOR_RED;
			rb_rotate_left(root, grand_parent);
		}
	}

	(*root)->color = COLOR_BLACK;
	return 0x0;
}


int insert_rbtree(rb_tree_t *root, rb_node_t *node)
{
	rb_node_t *p = *root;
	rb_node_t *q = NULL;

	//find the position we need to insert
	while(p)
	{
		q = p;
		if(p->key == node->key)
			return 1;
		else if(p->key > node->key)
			p = p->left;
		else
			p = p->right;
	}

	node->parent = q;

	if(q != NULL)
	{
	    if(node->key < q->key)
			q->left = node;
		else
			q->right = node;
	}
	else{
		*root = node;
	}

	node->color = COLOR_RED;

	return rb_insert_fixup(root, node);
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

B/B+ 树

B 树相对于上面说的树，核心区别就是多叉

B+ 树的相对于 B 树的核心区别有两点

• 只有叶子节点保存值
• 叶子节点间有双向指针

存储引擎使用 B+ 树的原因

• 只有叶子节点保存值
  • 相对于 B 树来说，主文件指针只存放在叶子节点，所以这样的话 如果一个索引块可以全部放满的话，那么 B+ 树的节点可以能放的索引项比 B 树多，因为不放行指针或数据值；
  • 而且也不会出现查找不同值时，耗费的时间不同。
• 叶子节点间有双向指针
  • B 树没有删除合并，B+ 树通过删除合并来保证每个节点指针的利用率在 50%~100%，逻辑其实很容易相通，就是下层节点个数决定上层节点的个数，所以只要保证了叶子节点的空间利用率，也就保证了整棵树其他节点的空间利用率，删除节点合并就是 B+ 树独创的，每个节点间的双向指针实现的，会根据被删除元素页子节点的剩余元素个数，与相邻页子节点的现存元素个数，来决定是合并还是窃取元素，然后再逐层向上调整指针；
  • 也正是这个双向指针还可以方便的范围检索。

（具体插入和删除示例可以参考我数据库的文章： 数据库索引之 B+ 树 ）