tree.class

tree source code vrey good

public Object put(Object key, Object value) {
        Entry t = root;

        if (t == null) {                                   //根为空，即树为空
            incrementSize();                            //增加计数
            root = new Entry(key, value, null); 
            return null;
       }

        while (true) {
            int cmp = compare(key, t.key);        
            if (cmp == 0) {
                return t.setValue(value);  //对比相等，取代原值
            } else if (cmp < 0) {
                if (t.left != null) {
                    t = t.left;   //搜索左子树
                } else {
                    incrementSize();                     

                    t.left = new Entry(key, value, t);  //插入左节点
                    fixAfterInsertion(t.left);  //调整树结构
                    return null;
                }
            } else { // cmp > 0
                if (t.right != null) {
                    t = t.right;    //搜索右子树
                } else {
                    incrementSize();  
                    t.right = new Entry(key, value, t);
                    fixAfterInsertion(t.right);
                    return null;
                }
            }
        }
    }

   下面是fixAfterInsertion（Entry ）的源码

 private void fixAfterInsertion(Entry x) {
        x.color = RED;    //新插入节点总是红色

        while (x != null && x != root && x.parent.color == RED) {  //如果parent颜色是黑色，不需要变换
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {  //x父节点为x祖父节点的左节点
                Entry y = rightOf(parentOf(parentOf(x)));  //y=祖父节点右节点
                if (colorOf(y) == RED) {  //祖父节点右节点为red
                    setColor(parentOf(x), BLACK); //变换父节点为black 
                    setColor(y, BLACK);  //变换y为black
                    setColor(parentOf(parentOf(x)), RED);  //变换祖父节点为红色 
                    x = parentOf(parentOf(x));  //x上行到祖父节点
                } else {
                    if (x == rightOf(parentOf(x))) {  //x为父节点的右节点
                        x = parentOf(x); //x指向父节点
                        rotateLeft(x);  //左转，x的右节点r成为x的父节点（即新插入节点成为x的父节点）
                    }
                    setColor(parentOf(x), BLACK); //设置父节点black
                    setColor(parentOf(parentOf(x)), RED); //设置祖父节点red
                    if (parentOf(parentOf(x)) != null) 
                        rotateRight(parentOf(parentOf(x)));  //右转，祖父节点成为它的左节点的右节点
                }
            } else {
                Entry y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x),  BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    if (parentOf(parentOf(x)) != null) 
                        rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;  //设置根节点黑色
    }