【树结构】平衡二叉树

小咪咪 2022-02-28 13:52 299阅读 0赞

### 平衡二叉树 ###

*  平衡二叉树定义
 *  数据模型定义(go)：
 *  旋转
 *   *  1. 左左情况（左子树的左边节点）
     *  2.右右情况（右子树的右边节点）
     *  3. 左右情况（左子树的右边节点）
     *  3. 右左情况(右子树的左边节点）
 *  新增节点
 *  删除节点

# 平衡二叉树定义 #

前面我们说过，二叉查找树不是严格的O(logN)，导致了在真实场景中没有用武之地，谁也不愿意有O(N)的情况发生。当有很多数据灌到我的树中时，我肯定会希望最好是以“完全二叉树”的形式展现，这样我才能做到“查找”是严格的O(logN)，

比如把这种”树“调正到如下结构。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70]  
这里就涉及到了二叉树节点的旋转。

**平衡二叉树**： 父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图中我们认为树的高度为h=2。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 1]

# 数据模型定义(go)： #

/* 33 h=3 / \ 22 44 h=2 / \ / \ h=0 11 28 40 49 h=1 /\ \ \ 25 30 42 60 h=0 父节点的左子树和右子树的高度之差不能大于1， */
    type AvlNode struct { 
    	key   int
    	value string
    	// 树的高度, 以当前结点为根节点的子树的最大高度
    	height int
    	left   *AvlNode
    	right  *AvlNode
    }

# 旋转 #

BST中节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。

## 1. 左左情况（左子树的左边节点） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 2]  
我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。

/** 左左旋转，新节点增加在左子树的左结点导致失衡,如下图新增节点1导致节点5失衡： 5 3 / \ / \ 3 6 单旋转 2 5 / \ ------------> / / \ 2 4 1 4 6 / 1 */
    func rotateLL(root *AvlNode) *AvlNode { 
    	/* 这里的root节点类似于上图中的节点5的存在 */
    	// 获得到顶层节点
    	top := root.left
    	// 先截断当前结点的左孩子
    	root.left = top.right
    	// 将当前结点作为新的top节点的右孩子
    	top.right = root
    
    	root.height = int(math.Max(float64(height(root.left)), float64(height(root.right)))) + 1
    	top.height = int(math.Max(float64(height(top.left)), float64(height(top.right)))) + 1
    	return top
    }

## 2.右右情况（右子树的右边节点） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 3]  
同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方将树往下拉一位，最后也就形成了我们希望的平衡效果。

/** 右右旋转，新节点增加在右子树的右结点导致失衡,如下图新增节点9导致节点5失衡： 5 7 / \ / \ 3 7 单旋转 5 8 / \ ------------> / \ \ 6 8 3 6 9 \ 9 */
    func rotateRR(root *AvlNode) *AvlNode { 
    	/* 这里的root节点类似于上图中的节点5的存在 */
    	// 获得到顶层节点
    	top := root.right
    	// 先截断当前结点的左孩子
    	root.right = top.left
    	// 将当前结点作为新的top节点的右孩子
    	top.left = root
    
    	root.height = int(math.Max(float64(height(root.left)), float64(height(root.right)))) + 1
    	top.height = int(math.Max(float64(height(top.left)), float64(height(top.right)))) + 1
    
    	return top
    }

## 3. 左右情况（左子树的右边节点） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 4]  
从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了。

/** 左右旋转，新节点增加在左子树的右结点导致失衡,如下图新增节点9导致节点5失衡： 5 5 3 / \ / \ / \ 3 6 先对1进行右右旋转 3 6 再对5进行左左旋转 2 5 / \ ------------> /\ --------------> / / \ 1 4 转换成左左的case 2 4 1 4 6 \ / 2 1 */
    func rotateLR(root *AvlNode) *AvlNode { 
    	/* 这里的root节点类似于上图中的节点5的存在 */
    	root.left = rotateRR(root.left)
    	return rotateLL(root)
    }

## 3. 右左情况(右子树的左边节点） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 5]  
这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“，然后进行”右右情况旋转“，最终得到了我们满意的平衡。

/** 右左旋转，新节点增加在右子树的左结点导致失衡,如下图新增节点9导致节点5失衡： 5 5 7 / \ / \ / \ 3 7 先对9进行左左旋转 3 7 再对5进行右右旋转 5 8 / \ ------------> /\ --------------> / \ \ 6 9 转换成右右的case 6 8 3 6 9 / \ 8 9 */
    func rotateRL(root *AvlNode) *AvlNode { 
    	/* 这里的root节点类似于上图中的节点5的存在 */
    	root.right = rotateLL(root.right)
    	return rotateRR(root)
    }

# 新增节点 #

完全是基于上面的四种旋转方式来做。

func AddNode(root *AvlNode, k int, v string) *AvlNode { 
    	if root == nil { 
    		root = &AvlNode{ 
    			key:    k,
    			value:  v,
    			height: 0,
    			left:   nil,
    			right:  nil,
    		}
    		return root
    	}
    
    	if k < root.key { 
    		//recursion and get slot for inserting
    		root.left = AddNode(root.left, k, v)
    		if height(root.left)-height(root.right) == 2 { 
    			if k < root.left.key { 
    				// 左左旋转
    				root = rotateLL(root)
    			} else { 
    				// 左右旋转
    				root = rotateLR(root)
    			}
    		}
    	} else if k > root.key { 
    		root.right = AddNode(root.right, k, v)
    		if height(root.right)-height(root.left) == 2 { 
    			if k > root.key { 
    				// 右右旋转
    				root = rotateRR(root)
    			} else { 
    				// 右左旋转
    				root = rotateRL(root)
    			}
    		}
    	} else { 
    		// update
    		root.value = v
    	}
    
    	root.height = int(math.Max(float64(height(root.left)), float64(height(root.right)))) + 1
    	return root
    }

# 删除节点 #

删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。

func DeleteNode(root *AvlNode, k int) *AvlNode { 
    	if root == nil { 
    		return nil
    	}
    	//
    	if k < root.key { 
    		//Recursively delete the left child node
    		root.left = DeleteNode(root.left, k)
    		if height(root.left)-height(root.right) == 2 { 
    			if k < root.left.key { 
    				// 左左旋转
    				root = rotateLL(root)
    			} else { 
    				// 左右旋转
    				root = rotateLR(root)
    			}
    		}
    	} else if k > root.key { 
    		root.right = DeleteNode(root.right, k)
    		if height(root.right)-height(root.left) == 2 { 
    			if k > root.key { 
    				// 右右旋转
    				root = rotateRR(root)
    			} else { 
    				// 右左旋转
    				root = rotateRL(root)
    			}
    		}
    	} else { 
    		// equals
    		if root.left != nil && root.right != nil { 
    			root.key = FindMin(root.right).key
    			DeleteNode(root.right, root.key)
    		} else { 
    			if root.left == nil { 
    				root = root.right
    			} else { 
    				root = root.left
    			}
    			if root == nil { 
    				return nil
    			}
    		}
    	}
    
    	// Statistical height
    	root.height = int(math.Max(float64(height(root.left)), float64(height(root.right)))) + 1
    	return root
    }
    
    func FindMin(root *AvlNode) *AvlNode { 
    	if root == nil { 
    		return nil
    	} else if root.left == nil { 
    		return root
    	}
    	return FindMin(root.left)
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70]: /images/20220228/4ed3b08d8d214caaaf18fcba1f3d91b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 1]: /images/20220228/8c4893b40a28423fa0455da0c3e4731d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 2]: /images/20220228/3daab50a0b9545e39c523289a1e36541.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 3]: /images/20220228/efe78abf841e4c119e3ca403d20c5bc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 4]: /images/20220228/b22348e2efe24fd7b2968e63b90269b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 5]: /images/20220228/45b4d6ca27264f508c724872970d1090.png