`
leon_a
  • 浏览: 79035 次
  • 性别: 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）是一种自平衡二叉查找树，由计算机科学家鲁道夫·贝尔在1978年提出。它在保持二叉查找树特性的同时，通过引入颜色属性来确保树的平衡，从而提高了数据操作的效率。红黑树的主要目标是保证在...

    红黑树代码

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

    红黑树的源码与测试函数

    红黑树（Red-Black Tree）是一种自平衡二叉查找树，它的每个节点都带有颜色属性，可以是红色或黑色。这种数据结构被广泛应用于计算机科学的许多领域，特别是操作系统、数据库系统以及编译器中，用于高效地执行插入、...

    红黑树原理详解

    红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年发明。它的名称来源于其节点颜色属性，即红色和黑色。红黑树的主要特性保证了其在插入、删除和查找操作中的高效性能，通常时间复杂度为O(log n)，其中n是树中...

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

    红黑树是一种自平衡二叉查找树，由Rudolf Bayer于1972年提出。它的设计目标是在保持二叉查找树基本属性的同时，通过引入颜色（红色或黑色）来保证树的平衡，从而在插入和删除操作后能够快速恢复平衡状态，减少查找、...

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

    ### 红黑树的插入与删除：详细解析 红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年发明，最初被称为“对称二叉B树”。它在1978年Leo J. Guibas和Robert Sedgewick的论文中获得了现代名称“红黑树”。红黑树...

    红黑树完整实现文件

    红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本属性的同时，通过引入颜色（红色或黑色）来保证树的平衡，从而提高查找、插入和删除操作的效率。在红黑树中，每个...

    gcc 红黑树（二叉搜索树 红黑树 动态排序树 精确计时）

    红黑树是一种自平衡二叉查找树，它的设计目的是为了在保持查找效率的同时，尽可能地减少插入和删除操作带来的性能损失。在计算机科学中，它是一种广泛应用的数据结构，特别是在动态排序和高效查找方面。 二叉搜索树...

    红黑树java操作代码 红黑树是java里面遍历性能最好数据结构

    红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在实现高效的数据结构和算法时。在Java中，虽然标准库并未直接提供红黑树的类，但我们可以自定义实现，如提供的`Red...

    红黑树和AVL树的实现

    红黑树和AVL树是两种自平衡二叉查找树，它们在计算机科学中的数据结构领域扮演着重要的角色，主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡，从而确保搜索、插入和删除...

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

    红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本性质的同时，通过引入颜色属性来保证树的平衡，从而达到高效的插入、删除和查找操作。红黑树的关键特性是： 1. 每...

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

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

    红黑树-数据结构

    红黑树是一种自平衡二叉查找树（self-balancing binary search tree），由计算机科学家Rudolf Bayer在1972年提出。它在保持二叉查找树特性的同时，通过引入颜色属性来确保树的平衡，从而提高数据操作的效率。在红黑...

    红黑树的例子

    ### 红黑树知识点详解 #### 一、红黑树定义与性质 红黑树是一种自平衡二叉查找树，其每个节点除了保存键值、左子节点、右子节点和父节点的信息外，还额外保存了一个表示颜色的属性（红色或黑色）。红黑树在进行...

    红黑树算法的c实现

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

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

    红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年提出。它的设计目标是在保持查询效率高的同时，尽可能地减少由于插入和删除操作引起的树的不平衡。红黑树的主要特点包括： 1. **颜色属性**：每个节点都有...

    红黑树、区间树

    红黑树和区间树是两种在计算机科学中广泛使用的数据结构，主要应用于高效的数据存储和检索。它们在算法和数据结构领域具有重要地位，尤其在处理动态集合或需要快速查找和更新操作的问题时。 首先，我们来详细了解...

    红黑树实现源码

    红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性：红色或黑色。这种颜色属性被用来确保树的某些关键性质，...

    红黑树Java实现

    红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性：红色或黑色。这种颜色属性用于确保树的平衡，使得在树中的...

    红黑树算法及其应用_高庆.pdf

    "红黑树算法及其应用" 红黑树是一种高效的查找树数据结构，广泛应用于信息管理系统中的插入、删除、查找操作。红黑树的定义、优点、基本操作及算法将在下面详细介绍。 红黑树的定义 红黑树是一棵二叉查找树，如果...

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