区间树

package acmcode;


/**
 * @author Leon.Chen
 *
 */
public class IntervalTree {


    /**
     * 红
     */
    private static final String RED = "red";

    /**
     * 黑
     */
    private static final String BLACK = "black";

    /**
     * 根节点
     */
    private RBNode root;

    /**
     * 左旋转
     * 
     * @param x
     */
    private void leftRotate(RBNode x) {
        RBNode y = x.right;
        x.right = y.left;
        y.left.parent = x;
        x.setMinPointAndMaxPoint();
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else {
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        }
        y.left = x;
        x.parent = y;
        y.setMinPointAndMaxPoint();
    }

    /**
     * 右旋转
     * 
     * @param y
     */
    private void rightRotate(RBNode y) {
        RBNode x = y.left;
        y.left = x.right;
        x.right.parent = y;
        y.setMinPointAndMaxPoint();
        x.parent = y.parent;
        if (y.parent == null) {
            root = x;
        } else {
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        }
        x.right = y;
        y.parent = x;
        x.setMinPointAndMaxPoint();
    }

    /**
     * 红黑树插入方法
     * 
     * @param z
     */
    public void RBInsert(RBNode z) {
        if (root == null) {
            root = z;
            root.color = BLACK;
            root.setMinPointAndMaxPoint(z);
        } else {
            RBNode x = root;
            RBNode y = null;
            while (isNotNilNode(x)) {
                y = x;
                x.setMinPointAndMaxPoint(z);
                if (z.value.compareTo(x.value) < 0) {
                    x = x.left;
                } else {
                    x = x.right;
                }
            }
            if (z.value.compareTo(y.value) < 0) {
                y.left = z;
            } else {
                y.right = z;
            }
            z.color = RED;
            z.setMinPointAndMaxPoint(z);
            z.parent = y;
        }
        z.left = new RBNode(BLACK);
        z.right = new RBNode(BLACK);
        RBInsertFixUp(z);
    }

    /**
     * 解决插入冲突
     * 
     * @param z
     */
    private void RBInsertFixUp(RBNode z) {
        while (z.parent != null && z.parent.color.equals(RED)) {
            if (z.parent == z.parent.parent.left) {
                RBNode y = z.parent.parent.right;
                if (y.color.equals(RED)) {
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else if (z == z.parent.right) {
                    z = z.parent;
                    leftRotate(z);
                } else if (z == z.parent.left) {
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    rightRotate(z.parent.parent);
                }
            } else {
                RBNode y = z.parent.parent.left;
                if (y.color.equals(RED)) {
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else if (z == z.parent.left) {
                    z = z.parent;
                    rightRotate(z);
                } else if (z == z.parent.right) {
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    leftRotate(z.parent.parent);
                }
            }
        }
        root.color = BLACK;
    }

    /**
     * @param deleteNode
     */
    public void RBDelete(RBNode deleteNode) {
        RBNode y = null;
        RBNode z = serach(deleteNode.value);
        if (isNilNode(z.left) || isNilNode(z.right)) {
            y = z;
        } else {
            y = treeSuccessor(z);
        }
        RBNode x = null;
        if (isNotNilNode(y.left)) {
            x = y.left;
        } else {
            x = y.right;
        }
        x.parent = y.parent;
        if (isNilNode(y.parent)) {
            root = x;
        } else {
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        }
        if (y != z) {
            z.value = y.value;
        }
        if (y.color.equals(BLACK)) {
            RBDeleteFixUp(x);
        }
    }

    /**
     * @param x
     */
    private void RBDeleteFixUp(RBNode x) {
        // 解决黑黑冲突,完善中
        while (x != root && x.color.equals(BLACK)) {
            if (x == x.parent.left) {
                RBNode w = x.parent.right;
                if (w.color.equals(RED)) {
                    w.color = BLACK;
                    x.parent.color = RED;
                    leftRotate(x.parent);
                    w = x.parent.right;
                } else if (w.left.color.equals(BLACK) && w.right.color.equals(BLACK)) {
                    w.color = RED;
                    x = x.parent;
                } else if (w.right.color.equals(BLACK)) {
                    w.left.color = BLACK;
                    w.color = RED;
                    rightRotate(w);
                    w = x.parent.right;
                } else if (w.left.color.equals(BLACK)) {
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.right.color = BLACK;
                    leftRotate(x.parent);
                    x = root;
                }
            } else {
                RBNode w = x.parent.left;
                if (w.color.equals(RED)) {
                    w.color = BLACK;
                    x.parent.color = RED;
                    rightRotate(x.parent);
                    w = x.parent.left;
                } else if (w.left.color.equals(BLACK) && w.right.color.equals(BLACK)) {
                    w.color = RED;
                    x = x.parent;
                } else if (w.left.color.equals(BLACK)) {
                    w.right.color = BLACK;
                    w.color = RED;
                    leftRotate(w);
                    w = x.parent.left;
                } else if (w.right.color.equals(BLACK)) {
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.left.color = BLACK;
                    rightRotate(x.parent);
                    x = root;
                }
            }
        }
        x.color = BLACK;
    }

    /**
     * 找后继
     * 
     * @param node
     * @return RBNode
     */
    public RBNode treeSuccessor(RBNode node) {
        if (node.right != null) {
            return treeMiniMum(node.right);
        }
        RBNode currentNode = getParentNode(node);
        while (currentNode != null && node == currentNode.right) {
            node = currentNode;
            currentNode = getParentNode(node);
        }
        return currentNode;
    }

    /**
     * 找前驱
     * 
     * @param node
     * @return RBNode
     */
    public RBNode treePrecursor(RBNode node) {
        if (node.left != null) {
            return treeMaxiMum(node.left);
        }
        RBNode currentNode = getParentNode(node);
        while (currentNode != null && node == currentNode.left) {
            node = currentNode;
            currentNode = getParentNode(node);
        }
        return currentNode;
    }

    /**
     * 最大节点
     * 
     * @param node
     * @return RBNode
     */
    public RBNode treeMaxiMum(RBNode node) {
        while (isNotNilNode(node.right)) {
            node = node.right;
        }
        return node;
    }

    /**
     * 最小节点
     * 
     * @param node
     * @return RBNode
     */
    public RBNode treeMiniMum(RBNode node) {
        while (isNotNilNode(node.left)) {
            node = node.left;
        }
        return node;
    }

    /**
     * 找节点的父节点
     * 
     * @param node
     * @return TreeNode
     */
    public RBNode getParentNode(RBNode node) {
        RBNode current = root;
        RBNode trailCurrent = null;
        while (isNotNilNode(current)) {
            if (current.value.compareTo(node.value) == 0) {
                break;
            }
            trailCurrent = current;
            if (node.value.compareTo(current.value) < 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return trailCurrent;
    }

    /**
     * 搜索
     * 
     * @param value
     * @return TreeNode
     */
    public RBNode serach(RBValue value) {
        return treeSerach(root, value);
    }

    /**
     * 搜索
     * 
     * @param node
     * @param value
     * @return TreeNode
     */
    public RBNode treeSerach(RBNode node, RBValue value) {
        if (isNotNilNode(node) && node.value.compareTo(value) == 0) {
            return node;
        }
        if (value.compareTo(node.value) < 0) {
            return treeSerach(node.left, value);
        } else {
            return treeSerach(node.right, value);
        }
    }

    /**
     * 中序遍历
     * 
     * @param node
     */
    public void inOrder(RBNode node) {
        if (isNotNilNode(node)) {
            inOrder(node.left);
            System.out.println(node.value+","+node.color);
            inOrder(node.right);
        }
    }
    
    /**
     * 先序遍历
     * 
     * @param node
     */
    public void perOrder(RBNode node) {
        if (isNotNilNode(node)) {
            System.out.println(node.value+","+node.color);
            perOrder(node.left);
            perOrder(node.right);
        }
    }

    /**
     * @param node
     * @return 是否为NIL[T]节点
     */
    private boolean isNotNilNode(RBNode node) {
        return node != null && node.value != null;
    }

    /**
     * @param node
     * @return 是否为NIL[T]节点
     */
    private boolean isNilNode(RBNode node) {
        return !isNotNilNode(node);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        IntervalTree tree = new IntervalTree();
        tree.RBInsert(new RBNode(new RBValue(0,3)));
        tree.RBInsert(new RBNode(new RBValue(5,8)));
        tree.RBInsert(new RBNode(new RBValue(6,10)));
        tree.RBInsert(new RBNode(new RBValue(8,9)));
        tree.RBInsert(new RBNode(new RBValue(15,23)));
        tree.RBInsert(new RBNode(new RBValue(16,21)));
        tree.RBInsert(new RBNode(new RBValue(17,19)));
        tree.RBInsert(new RBNode(new RBValue(19,20)));
        tree.RBInsert(new RBNode(new RBValue(25,30)));
        tree.RBInsert(new RBNode(new RBValue(26,26)));
        System.out.println("=================");
        System.out.println("root = "+tree.root.value);
        System.out.println("=================");
        tree.inOrder(tree.root);
        System.out.println("=================");
        tree.perOrder(tree.root);
    }

}

package acmcode;

/**
 * @author Leon.Chen
 *
 */
public class RBNode {

    /**
     * 
     */
    public RBNode parent;

    /**
     * 
     */
    public RBNode left;

    /**
     * 
     */
    public RBNode right;

    /**
     * 
     */
    public RBValue value;

    /**
     * 
     */
    public String color;

    /**
     * @param color
     */
    public RBNode(String color) {
        this.color = color;
    }

    /**
     * 
     */
    public RBNode() {

    }

    /**
     * @param value
     */
    public RBNode(RBValue value) {
        this.value = value;
    }
    
    /**
     * @param node
     */
    public void setMinPointAndMaxPoint(RBNode node) {
        if(node.value.startPoint<this.value.minPoint) {
            this.value.minPoint = node.value.startPoint;
        }
        if(node.value.endPoint>this.value.maxPoint) {
            this.value.maxPoint = node.value.endPoint;
        }
    }
    
    /**
     * 
     */
    public void setMinPointAndMaxPoint() {
        int min = 0;
        int max = 0;
        if (this.left.value == null && this.right.value == null) {
            min = this.value.startPoint;
            max = this.value.endPoint;
        } else {
            min = getMin();
            max = getMax();
        }
        this.value.minPoint = min;
        this.value.maxPoint = max;
    }
    
    /**
     * @return min
     */
    private int getMin() {
        RBNode left = this.left;
        RBNode right = this.right;
        int temp = getMin(left,right);
        if(this.value.startPoint > temp) {
            return temp;
        }
        return this.value.startPoint;
    }
    
    /**
     * @return max
     */
    private int getMax() {
        RBNode left = this.left;
        RBNode right = this.right;
        int temp = getMax(left,right);
        if(this.value.endPoint >temp) {
            return this.value.endPoint;
        }
        return temp;
    }
    
    /**
     * @param node1
     * @param node2
     * @return min
     */
    private int getMin(RBNode node1, RBNode node2) {
        if (node1.value == null && node2.value == null) {
            return 2147483647;
        }
        if (node1.value == null) {
            return node2.value.minPoint;
        }
        if (node2.value == null) {
            return node1.value.minPoint;
        }
        return (node1.value.minPoint < node2.value.minPoint ? node1.value.minPoint : node2.value.minPoint);
    }
    
    /**
     * @param node1
     * @param node2
     * @return max
     */
    private int getMax(RBNode node1, RBNode node2) {
        if (node1.value == null && node2.value == null) {
            return 0;
        }
        if (node1.value == null) {
            return node2.value.maxPoint;
        }
        if (node2.value == null) {
            return node1.value.maxPoint;
        }
        return (node1.value.maxPoint < node2.value.maxPoint ? node2.value.maxPoint : node1.value.maxPoint);
    }
}

package acmcode;

/**
 * @author Leon.Chen
 *
 */
public class RBValue {

    /**
     * 
     */
    public int startPoint;

    /**
     * 
     */
    public int endPoint;

    /**
     * 初始化minPoint为无穷大
     */
    public int minPoint = 2147483647;

    /**
     * 
     */
    public int maxPoint;

    /**
     * @param startPoint
     * @param endPoint
     */
    public RBValue(int startPoint, int endPoint) {
        this.startPoint = startPoint;
        this.endPoint = endPoint;
    }

    /**
     * @param otherValue
     * @return 比较结果
     */
    public int compareTo(RBValue otherValue) {
        int thisVal = this.startPoint;
        int anotherVal = otherValue.startPoint;
        return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
    }

    public String toString() {
        return "[" + startPoint + "," + endPoint + "]" + " , [" + minPoint + "," + maxPoint + "]";
    }
}

评论

1 楼 liuxuejin 2011-04-19  

好！慢慢下载来看看