`
leon_a
  • 浏览: 77792 次
  • 性别: Icon_minigender_1
  • 来自: 拜月神教
社区版块
存档分类
最新评论

红黑树初版

算法 
阅读更多 
package acmcode;

/**
 * Red-Black Tree
 * 
 * @author Leon.Chen
 */
public class RBTree {

    /**
     * 红
     */
    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;
        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;
    }

    /**
     * 右旋转
     * 
     * @param y
     */
    private void rightRotate(RBNode y) {
        RBNode x = y.left;
        y.left = x.right;
        x.right.parent = y;
        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;
    }

    /**
     * 红黑树插入方法
     * 
     * @param z
     */
    public void RBInsert(RBNode z) {
        if (root == null) {
            root = z;
            root.color = BLACK;
        } else {
            RBNode x = root;
            RBNode y = null;
            while (isNotNilNode(x)) {
                y = x;
                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.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) {
        System.out.println("===="+x.value);
        // 解决黑黑冲突,完善中
        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) {
        RBTree tree = new RBTree();
        
        
        tree.RBInsert(new RBNode(new RBValue(3)));
        tree.RBInsert(new RBNode(new RBValue(4)));
        tree.RBInsert(new RBNode(new RBValue(12)));
        tree.RBInsert(new RBNode(new RBValue(13)));
        tree.RBInsert(new RBNode(new RBValue(11)));
        tree.RBInsert(new RBNode(new RBValue(15)));
        tree.RBDelete(new RBNode(new RBValue(12)));
        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;

    public RBNode(String color) {
        this.color = color;
    }

    public RBNode() {

    }

    public RBNode(RBValue value) {
        this.value = value;
    }

}


package acmcode;

public class RBValue {

    public int value;

    public RBValue(int value) {
        this.value = value;
    }

    public int compareTo(RBValue otherValue) {
        int thisVal = this.value;
        int anotherVal = otherValue.value;
        return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));
    }

    public String toString() {
        return new Integer(value).toString();
    }
}

忘了附图
  • 描述: Introduction to Algorithms 2nd Edition
  • 大小: 71.2 KB
1
顶
2
踩
分享到：
| 四则运算的中缀转后缀，逆波兰表达式求值
评论
4 楼 OnJavaRoad 2008-11-07  
先收藏了，找时间研究研究
3 楼 pf_miles 2008-07-17  
引用
原来是树？？？。
小看了一下。。懂了。

是啊，是树～
我家门前有好几棵大的！
2 楼 Wallian_hua 2008-07-17  
原来是树？？？。
小看了一下。。懂了。
1 楼 Wallian_hua 2008-07-17  
没懂。。 这是什么
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    红黑树代码

    红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...

    红黑树-动态演示生成红黑树

    红黑树算法，随机产生数字，动态生成红黑树，可用于演示。

    红黑树原理详解

    红黑树原理详解 红黑树原理详解 红黑树原理详解 红黑树原理详解

    红黑树的插入详细图解，直接拿下红黑树

    红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）...

    Linux内核红黑树封装的通用红黑树

    通用红黑树 说明： 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树： 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者：rcyh 日期：2011年7月21日 ---------------------------------...

    红黑树算法的c实现

    红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树

    红黑树C++代码实现

    描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 1).插入测试，输入 8，11，17，15，6，1，22，25，27，...

    红黑树的插入与删除_详细整理资料

    红黑树的插入与删除_详细整理资料

    红黑树和AVL树的实现

    红黑树和AVL树的代码实现，并显示树的形状，同时红黑树还可以输出个路径以及黑高度

    红黑树算法试验完全实现（花1天时间写的算法作业）

    描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 1).插入测试，输入 8，11，17，15，6，1，22，25，27...

    算法实现及性能比较与红黑树

    问题描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 实验要求： 1).插入测试，输入 8，11，17，15，6，...

    用c实现的红黑树，经典的红黑树，

    用c实现的红黑树，经典的红黑树， 速度与思维的立体化结构

    红黑树-使用C++实现-简单练习

    在学习c++的过程中实现的红黑树,功能比较完善,无优化..

    红黑树的c实现源码与教程

    红黑树的c实现源码与剖析 原作者：那谁 源码剖析作者：July ===================== July说明： 由于原来的程序没有任何一行注释，我把它深入剖析，并一行一行的添加了注释， 详情请参见此文： 教你彻底实现红黑树：...

    红黑树的C实现，算法导论的红黑树C实现

    红黑树的C语言实现 算法导论的红黑树C实现

    红黑树算法C语言实现

    实验1：实现红黑树的基本算法， 对n的取值分别为 12、24、36、48、60，随机生成n 个互异的正整数（K1, K2, K3, ……, Kn）作为节点的关键字，向一棵初始空的红黑树中依次插入这n 个节点，统计算法运行所需时间 ，画...

    红黑树demo python代码

    该资源是一个红黑树的demo程序，包含了红黑树的插入和红黑树的删除过程，实现方式相对比较简单明了，适合于刚刚接触红黑树的入门者阅读。

    红黑树、区间树

    红黑树继承二叉查找树，区间树继承红黑树，main函数中写的是区间树的测试程序

    29.红黑树_2.wmv（目前数据结构最好的视频,共42集，需要哪一集的知识自己下，一集3积分）

    26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS

    红黑树图形化

    研究数据结构的红黑树的时候想验证自己写的红黑树算法总是很麻烦，自己用h5写了个图形化的工具，只需要把红黑树转换成json然后复制粘贴到代码的tree变量即可

Magicbox
Global site tag (gtag.js) - Google Analytics