我在看《算法4》的红黑树实现时对于他的删除操作很不理解。这本书中的红黑树所有红键都位于左孩子结点，同时不同于算法导论中的红黑树，他没有指向父节点的指针.
public class RedBlackTree
{
private final boolean BLACK = false ;
private final boolean RED = true ;
private Node root ;
private class Node
{
int value ;
int key ;
Node left , right ;
boolean color ; //true为红轴
int n ;//子树的节点总数
public Node(int value, int key, boolean color, int n) {
this.value = value;
this.key = key;
this.color = color;
this.n = n;
}
}
private boolean isRed(Node x)
{
return x != null && x.color ;
}
public void insert(int key , int value)
{
root = put(root , key , value) ;
root.color = BLACK ;
}
private Node put(Node root , int key , int value)
{
if(root == null)
return new Node(value , key , RED , 1) ;
int cmp = root.key - key ;
if(cmp > 0)
root.left = put(root.left , key , value) ;
else if(cmp < 0)
root.right = put(root.right , key , value) ;
else
root.value = value ;
if(!isRed(root.left) && isRed(root.right))
root = rotateLeft(root) ;
if(isRed(root.left.left) && isRed(root.left))
rotateRight(root) ;
if(isRed(root.left) && isRed(root.right))
flipColors(root) ;
root.n = lenght(root) ;
return root ;
}
private Node rotateLeft(Node root)
{
Node temp = root.right ;
root.right = temp.left ;
boolean color = root.color ;
root.color = temp.color ;
temp.left = root ;
temp.color = color ;
root.n = lenght(root) ;
temp.n = lenght(temp) ;
return temp ;
}
private Node rotateRight(Node root)
{
Node temp = root.left ;
root.left = temp.right ;
temp.right = root ;
boolean color = root.color ;
root.color = temp.color ;
temp.color = color ;
root.n = lenght(root) ;
temp.n = lenght(temp) ;
return temp ;
}
private void flipColors(Node h)
{
if(h.left != null)
h.left.color = flip(h.left) ;
if(h.right != null)
h.right.color = flip(h.right) ;
h.color = flip(h) ;
}
private boolean flip(Node h)
{
return !h.color ;
}
private int lenght(Node root)
{
if(root == null)
return 0 ;
int num = 0 ;
if(root.left != null)
num+=root.left.n ;
if(root.right != null)
num+=root.right.n ;
num++ ;
return num ;
}
public void delete(int num)
{
if(root == null)
return ;
if(!isRed(root.left) && !isRed(root.right))
root.color = RED ;
root = delete(root , num) ;
if(root != null)
root.color = BLACK ;
}
private Node delete(Node node , int key)
{
if(node == null)
return null ;
int cmp = node.key - key ;
if(cmp > 0) //说明在他的左子树上
{
//说明是一个2-节点, 需要从右子树上借一个给他
if(node.left != null && !isRed(node.left) && !isRed(node.left.left))
node = moveRedLeft(node) ;
node.left = delete(node.left , key) ;
}
else //说明key在右子树上
{
if(isRed(node.left))//说明该节点本身就是3-节点, 直接分一个给右子树即可
node = rotateRight(node) ;
if(cmp == 0 && node.right == null)
return null ;
//如果右节点是一个2-节点, 那么就从左子树上借一个给他
if(node.right != null && !isRed(node.right) && !isRed(node.right.left))
node = moveRedRight(node) ; //cmp失效, 重新计算
cmp = node.key-key ;
if(cmp == 0)
{
//和普通二叉树的删除相同, 将右子树的最小节点放在这个节点的位置
Node x = min(node.right) ;
node.key = x.key ;
node.value = x.value ;
//将原来的最小节点删除
node.right = deleteMin(node.right) ;
}
else
{
node.right = delete(node.right , key) ;
}
}
//维持红黑树的性质
return balance(node) ;
}
public int min()
{
return min(root).key ;
}
private Node min(Node node)
{
while (node.left != null)
node = node.left ;
return node ;
}
/**
* 删除最大值的思路和删除最小值的思路类似,
* 如果该节点的右子节点是一个2-节点, 且他的兄弟节点也是一个2-节点, 那么就和该节点的最小值合并成一个4-节点
* 如果该节点的右子节点是一个2-节点, 且他的兄弟节点是一个3-节点, 那么就和他的兄弟节点借一个节点变成3-节点
* 否则该节点的右子节点一定是一个3-节点,停止.
*/
public void deleteMax()
{
if(root == null)
return ;
if(!isRed(root.left) && !isRed(root.right)) //为了防止在moveRedRight中该节点变成5-节点
root.color = RED ;
root = deleteMax(root) ;
if(root != null)
root.color = BLACK ;
}
private Node deleteMax(Node n)
{
if(isRed(n.left)) //说明该节点是一个3-节点, 那么直接借给右子节点一个key即可
n = rotateRight(n) ;
if(n.right == null)
return null ;
if(!isRed(n.right) && !isRed(n.right.left)) //说明右节点仅仅是一个黑色的节点,因此需要从父节点和左兄弟节点借一个过来
n = moveRedRight(n) ;
n.right = deleteMax(n.right) ;
return balance(n) ;
}
//基于一个前提: node的颜色为红色, 而且node的right和right.left均为黑色
//这个函数的作用是将该节点的右子节点变成非2节点, 因此必须假设node为红色(这样才能给右子节点借一个节点), node的right和right.left为黑色
//此时交换颜色才能保证node和他的两个子节点变成4-节点, 而不是5-节点
private Node moveRedRight(Node node)
{
flipColors(node) ; //转换颜色后, 父节点和两个子节点合并成一个3-节点
//如果左子节点为3-节点, 那么就可以从左子节点借一个节点给右节点, 因此右旋
if(isRed(node.left.left))
{
//调整过程
node = rotateRight(node) ; //将两个红键右旋变换
flipColors(node) ; //调整之后, node的左右两个子节点都是红键, 因此需要转换颜色以使左边变成平衡的红黑树
}
return node ;
}
/**
* 思路:
* 一般思路: 当前节点的左子节点不是2-节点时, 停止;
* 当前节点的左子节点是2-节点, 而他的兄弟节点也是2-节点时, 那么当前节点的最小值和左子节点和左子节点的兄弟借点合并成一个4-节点
* 当前节点的左子节点是2-节点,而他的兄弟节点是2-节点, 那么就和他的兄弟节点借一个给左子节点.
*/
public void deleteMin()
{
if(root == null)
return ;
if(!isRed(root.left) && !isRed(root.right)) //是为了防止在moveRedLeft的交换颜色变成5-节点
root.color = RED ;
root = deleteMin(root) ;
if(root != null)
root.color = BLACK ;
}
/**
* root是不是2-节点都没有关系
* @param root
* @return
*/
private Node deleteMin(Node root)
{
if(root.left == null)
return null ;
if(!isRed(root.left) && !isRed(root.left.left)) //说明当前节点的左子节点是2-节点, 需要借一个节点
root = moveRedLeft(root) ;
root.left = deleteMin(root.left) ;
root = balance(root) ;
return root ;
}
private Node balance(Node h)
{
if(h == null)
return null ;
if(isRed(h.right))
h = rotateLeft(h) ;
if(isRed(h.left) && isRed(h.left.left))
h = rotateRight(h) ;
if(isRed(h.left) && isRed(h.right))
flipColors(h) ;
h.n = lenght(h) ;
return h ;
}
/**
* root一定是红键(因为只有这样才会在flipColors变成4-节点, 而不是5-节点
*/
private Node moveRedLeft(Node node)
{
flipColors(node); //假设右节点是2-节点, 那么就合并成4-节点
if(isRed(node.right.left))//说明右节点是3-节点, 那么就应该是从右节点借一个节点给左节点, 所以进行右旋和变换颜色
{
node.right = rotateRight(node.right) ;
node = rotateLeft(node) ;
flipColors(node) ;
}
return node ;
}
public boolean isEmpty()
{
return root == null ;
}
}
我这几天将deleteMax和deleteMin思考明白了, 但是对于delete却仍不明白...求指点
我想明白这个问题了...这个是我模拟标准实现写的代码, 标准实现是先确定红黑树中存在该元素,然后删除; 我的则是直接删除,不管存不存在. 暂时还没有测试, 不过和标准代码实现基本一致
public void delete(int num)
{
if(root == null)
return ;
if(!isRed(root.left) && !isRed(root.right))
root.color = RED ;
root = delete(root , num) ;
if(root != null)
root.color = BLACK ;
}
{
if(node == null)
return null ;
int cmp = node.key - key ;
if(cmp > 0) //说明在他的左子树上
{
//说明是一个2-节点, 需要从右子树上借一个给他
if(node.left != null && !isRed(node.left) && !isRed(node.left.left))
node = moveRedLeft(node) ;
node.left = delete(node.left , key) ;
}
else //说明key在右子树上
{
if(isRed(node.left))//说明该节点本身就是3-节点, 直接分一个给右子树即可
node = rotateRight(node) ;
if(cmp == 0 && node.right == null)
return null ;
//如果右节点是一个2-节点, 那么就从左子树上借一个给他
if(node.right != null && !isRed(node.right) && !isRed(node.right.left))
node = moveRedRight(node) ; //cmp失效, 重新计算
cmp = node.key-key ;
if(cmp == 0)
{
//和普通二叉树的删除相同, 将右子树的最小节点放在这个节点的位置
Node x = min(node.right) ;
node.key = x.key ;
node.value = x.value ;
//将原来的最小节点删除
node.right = deleteMin(node.right) ;
}
else
{
node.right = delete(node.right , key) ;
}
}
//维持红黑树的性质
return balance(node) ;
}
删除的思路和删除最小值最大值的思路类似, 之前的思维局限于如何模拟2-3树的删除而导致没有认清楚他们之间的关系...