一些基于二分查找树的简单操作

1.获得给定小于给定key中的最大值，如果包含给定key，则返回该key；

        不谈找到指定key，这个问题就是寻找如果将给定key插入到树中，其后趋。如果是获得大于key中的最小值，则是寻找将该值插入到树中的前趋。

        2分查找树中的中序遍历就是按升序排列的数列。

K floorKey(K key){
    160         K p = root;
    161         while(p!=null){
    162                 if(key>p){
    163                         if(p.right!=null){
    164                                 p = p.right;
    165                         } else {
    166                                 return p;
    167                         }
    168                 } else {
    169                         if(p.left!=null){
    170                                 p = p.left;
    171                         } else {
    172                                 K parent = p.parent;
    173                                 K ch = p;
    174                                 while(parent!=null&&ch == parent.left){
    175                                         ch = parent;
    176                                         parent = parent.parent;
    177                                 }
    178                                 return parent;
                                    }
                            } 

 

2.红黑树的插入算法实现；

两点,显式的是插入节点设置为红色会破坏红黑树的颜色规则，隐式的是插入节点导致的颜色调整会破坏红黑树的平衡性，即通过旋转而破坏最大黑长度大于（2lnh-1）；

 

//红黑树的插入
void insert(K key){
	K p = root;	
	while(p!=null){
		if(key<p){
			p = p.left;
		} else if(key>p) {
			p = p.right;
		}
	}
	p = key;
	p.color = red;
	fixAfterInsert(p);
}

void fixAfterInsert(K p){
	K parent = p.parent;
	while(parent!=null&&parent.color == red){
		if(parent == parent.parent.left){
			K uncle = parent.parent.right;
			if(uncle.color == red){
				parent.color = black;
				uncle.color = black;
				parent.parent.color = red;
				p = parent.parent;
			} else {
				if(p == parent.right){
					p = parent;
					leftrotate(p);
				}
				p.parent = black;
				p.parent.parent = red;
				rightrotate(p.parent.parent);
			}
		} else {
			K Uncle = p.parent.parent.left;
			if(uncle.color = red){
				parent.color = black;
				uncle.color = black;
				parent.parent.color = red;
				p = parent.parent;
			} else {
				if(p = parent.left){
					p = parent;
					rightrotate(p);
				}
				p.parent = black;
				p.parent.parent = red;
				leftrotate(p.parent.parent);
			}
		}
	}
	root.color = black;
}

 3.红黑树的删除实现；

 

依旧是那条原则，基于数据结构的操作不能违背数据结构的定义。所以，红黑树的删除可能导致的问题第一是将一个红色节点作为根，或者删除节点的父节点和子节点都是红色，还有最最重要的是删除的黑色节点会影响到从删除节点到其余叶子的路径上黑色节点的数量减少（如果是删除了红色节点，对其不影响）。

1.如果将一红色节点设置为根，那么只要设置其为黑色，从根到所有叶子节点的黑高度减1；

2.红红，红黑节点相连接，也很简单，设置其为黑色；

3.这个就复杂了，删除节点的子节点为黑色（如果为根就是case1），那么，通过对其父节点和兄弟节点颜色的设置，再进行旋转，就可到达要求（为什么需要对兄弟节点考虑不同情况，旋转嘛，固然和该sib有关啦）：

                1.兄弟节点（sib）为红色，其父节点为黑色，删除节点后导致替换该位置的子树比兄弟子树黑高度少，那么父节点设置为红色，sib为黑，旋转即可。

                2.sib为黑色并且两个子节点都为黑色，动动脑子也知道对sib设置红色，那么从该两节点（sib和该节点）的父节点的子树黑高度都减少了1，那么将该父节点开始递归操作，直到某节点是红色或者为根。

                3.sib为黑色节点而右孩子为黑色，左节点为红色，转换该左孩子和sib颜色，然后对sib旋转，现在的情况是sib为红色，原左孩子为黑色，新sib是它。

                4.其实case3是为了转换为case4，sib的右节点为红色的情况，现在sib节点子树黑高度大于删除节点的子树，我开始的想法是直接旋转，发现旋转后原sib节点的父节点的孩子的子树上黑高度太“高”了，所以，将父节点设置为黑色，而sib设置为红色。

 

代码的话，treemap里面第2100行左右有，呵呵，懒，不愿意cp了。

 

 

 

最后，我的文章都是写给自己看的，所以，很多地方很懒，自己懂就好了。