本文共 2862 字，大约阅读时间需要 9 分钟。

第五周介绍平衡查找树和BST的几何应用。

Week5

Balanced Search Tree

2-3 Tree

定义

2-3树也是一种数据结构，能够维护树的平衡。其内部节点（存在子节点的节点）要么有2个孩子和1个数据元素；要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1或2个数据元素。

在维基百科中具体定义如下：

如果一个内部节点拥有一个数据元素、两个子节点，则此节点为2节点；

如果一个内部节点拥有两个数据元素、三个子节点，则此节点为3节点；

当且仅当一下叙述中有一条成立时，T为2-3树：

T为空。即T不包含任何节点；

T为拥有数据元素a的2节点。若T的左孩子为L，右孩子为R，则：

L和R是等高的非空2-3树；

a大于L中的所有数据元素，同时，a小于等于R中的所有数据元素；

T为拥有数据元素a和b的3节点，其中a<b。若T的左孩子为L、中间孩子为M、右孩子为R，则

L、M和R是等高的非空2-3树；

a大于L中的所有数据元素，并且小于等于M中的所有数据元素‘；同时

b大于M中的所有数据元素，并且小于等于R中的所有数据元素。

操作

1. 2-3树的查找：

   

2. 2-3树插入元素：

   往一个2-node节点插入：将新的元素放到此2-node节点里，使其变为3-node节点即可。

   

   往一个3-node节点插入：

   只包含一个3-node节点：暂时将3-node变为一个4-node节点，将此4-node节点的中间元素提升，左边节点作为其左节点，右边元素节点作为其右节点。插入完成，树的高度由0变为1

   

   节点是3-node,父节点是2-node：与第一种情况一样，将节点的中间元素提升到父节点的2-node节点中，使得父节点成为一个3-node节点，然后将左右节点分别挂在这个3-node节点的恰当位置

   

   节点是3-node，父节点也是3-node：当节点拆分，中间元素提升至父节点，但此时父节点是一个3-node，插入后，父节点也要进行分裂，继续将中间元素提至父节点的父节点，一直重复此操作，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需继续拆分。当根节点到字节点都是3-node的时候，在最后一步要进行根节点的分量，此时树的高度加1.

   

3. 本地转换

   

Red-Black Tree（红黑树）

什么是红黑树？

红黑树是一种含有红黑结点并且能够自平衡的二叉查找树。它必须满足以下性质：

1. 每个节点要么是黑色，要么是红色；
2. 根节点是黑色；
3. 每个叶子节点（Nil）是黑色；
4. 每个红色节点的两个子节点一定都是黑色的；
5. 任意一个结点到每个叶子结点的路径都包含数量相同的黑结点；=> 如果一个结点存在黑的子节点，那么该结点肯定有两个子结点；
   （ps：java中，叶子节点为null）
   

三种基本操作：红黑树自平衡的关键——红黑树总是通过旋转和变色达到平衡。

1. 左旋：以某个结点作为支点（旋转结点），其右子节点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变：(左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树移动）
   

private Node rotateLeft(Node h){
   	assert isRight(h.right);	Node x = h.rigth;	h.right = x.left;	x.left = h;	x.color = h.color;	h.color = RED;	return x;}

2. 右旋：以某个结点为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变；（右旋只影响旋转节点和其左子树，把左子树的结点往右子树移动)
   

private Node rotateRight(Node h){
   	assert isRed(h.left);	Node x = h.left;	h.left = x.right;	x.right = h;	x.color = h.color;	h.color = RED;	return x;}

3. 变色：将结点的颜色由红变黑
   

private void flipColors(Node h){
   	assert !isRed(h);	assert isRed(h.left);	assert isRed(h.right);	h.color = RED;	h.left.color = BLACK;	h.right.color = BLACK;}

红黑树插入

插入操作包括：1. 查找插入的位置； 2. 插入后自平衡。

查找插入的父结点很简单，与查找操作区别不大，具体操作：

1. 从根结点开始查找；
2. 若根结点为空，那么插入结点作为根结点，结束；
3. 若根结点不为空，那么把根结点作为当前结点；
4. 若当前结点为null，返回当前结点的父结点，结束；
5. 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点值，结束；
6. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
7. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；

插入只有1结点：

右结点为红link，左旋当前结点；

插入2-node的结点：

1. 做BST插入，将新的link设置为红色
2. 如果新的红link在右边，则进行左旋
   
   如果左右都是red link，则变色——>红变黑；
   如果连续两个red link在同一列，右旋；
   
   
   总结：
   右子节点是红色，左子结点是黑色：左旋；
   左子结点，左子孙结点是红色：右旋；
   两个子节点都是红色：变色；
   

private Node put(Node h, Key key, Value val){
   	if(h == null) return new Node(key, val, RED);	int cmp = key.compareTo(h.key);	if (cmp < 0) h.left = put(h.left, val, RED);	else if (cmp > 0) h.right = put(h.right, val, RED);	else if (cmp == 0) h.val = val;		if(isRed(h.right) && !isRed(h.left))  h = rotateLeft(h); // right child red, left child black:rotate left;	if(isRed(h.left) && isRed(h.left.left) h = rotateRight(h); // left child, left-left grandchild red: rotate right;	if(isRed(h.left) && isRed(h.right)  flipColors(h);		return h;}

时间复杂度：

转载地址：http://ovzsi.baihongyu.com/