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

刺骨的言语ヽ痛彻心扉 2022-10-29 10:26 244阅读 0赞

# 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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]

示例：插入 9

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1][]

**右子树高**  
示例：插入 28

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2][]

示例：插入 18

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3][]

# 红黑树 #

**核心**

*  两条核心性质
    
     *  **两个红色节点不可以连续**
     *  **从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点**。（叶子节点均指nil叶子）
 *  最后一条性质确保：**没有一条路径会比其他路径长出2倍**。因而，红黑树是相对接近平衡的二叉树
    
     *  因为每次新插入的一个节点都是红色节点（起始时根节点为黑色），所以只要保证每个父子节点不同时为红色，那么就可以保证每条路径都是红黑节点交替，从而满足任何一个节点到叶节点经过的黑色节点数相同，也保证高度差一定在 2 倍以内。
 *  算法核心
    
     *  每次插入一个节点，把父节点变黑，再把祖父变红，然后把父节点旋转成祖父即可（即此时祖父还是黑色，但不存在冲突了）
     *  要解决的问题一：叔叔节点是红色时，无法把祖父变红，不然就红色连续了。  
        处理策略：把叔叔一起变黑，再让祖父变为当前节点，然后按照上面的核心思想调整祖父，解决祖父变红的冲突。
     *  要解决的第二个问题：红黑树只有 L 旋转与 R 旋转，所以我上面说的把父节点变黑，然后转为祖父的前提必须是，子节点和父节点在同一个方向。  
        处理策略：先以父节点进行一次旋转，把插入节点转到同向

应用示例

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

### 算法实现 ###

#### 两种旋转 ####

右旋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4]  
左旋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 5]

#### 插入的三种情况 ####

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

*  对策：将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点重新开始算法  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 6]

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

*  对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 7]

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

*  对策：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋
 *  **最终目的都是转换为这种情况**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 8]

### 代码 ###

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);
    }

# B/B+ 树 #

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

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

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

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

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/b8c57002da51408f832e601936405722.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221024/b47d1409838d4813bc681222c6059568.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]: /images/20221024/c46937f4373043089b33141f41d2f972.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]: /images/20221024/321ea65901384f568878ea449c80767c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4]: /images/20221024/5840a2eca93044058bdae47060ae1967.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 5]: /images/20221024/a30bd6a2017841efb3d9a6ba7dc69c63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 6]: /images/20221024/b9a271d6396141ccacee52d34d03f0cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 7]: /images/20221024/5de2b161d1a04fbfacf7801303c3ecd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 8]: /images/20221024/e8fb6b465cc343818fe1195535694759.png
[_ B_ _]: https://yzx66.blog.csdn.net/article/details/110210686