精华内容
下载资源
问答
  • 红黑树问题是各大计算机考研命题以及面试算法题目中的热门,接下来我们为大家图解红黑树及Java进行红黑二叉树遍历的方法,需要的朋友可以参考下
  • 程序完美运行!!! 实现功能: 1.建立一个100个节点的红黑树 2.删除节点 3.前序遍历输出红黑树 4.中序遍历输出红黑树 5.查找节点
  • 红黑树的插入和遍历时间复杂度分析    在平常的工作中,最常用的一种数据结构恐怕是std::map了。因此对其的时间复杂度分析是有必要的,编写程序时做到心中有底。   一、理论分析  在stl中std::map和std::set都...

    红黑树的插入和遍历时间复杂度分析

     

           在平常的工作中,最常用的一种数据结构恐怕是std::map了。因此对其的时间复杂度分析是有必要的,编写程序时做到心中有底。

     

    一、理论分析

           在stl中std::map和std::set都采用红黑树的方式实现。我们知道插入一个元素到红黑树的时间为log(N),其中N为当前红黑树的元素个数,因此,采用插入方式构建元素个数为N的红黑树的时间复杂度为:

                  log(1) + log(2) + log(N-1) = log((N-1)!) = Nlog(N)

     

           那么采用迭代器遍历一棵红黑树的时间复杂度是多少呢? 是O(N)。 也就是说非递归遍历一棵红黑树的时间复杂度和遍历数组的时间复杂度是一样的,多么令人惊奇的结果。

           我们将分析得出这一结果。采用迭代器遍历红黑树的算法主要在迭代器增1操作:

     

    1.       判断右子树是不是空,如果不为空,找到右子树的最小值begin(right(tree)),结束。如果右子树为空,如果右子树为空,转2;

    2.       往根节点爬,直到父节点为空或者本节点是父节点的左子节点,然后取父节点的值。

     

    我们将证明红黑树的一条边最多被访问两次:一条边最多只能被从父节点到子节点访问一次和从子节点到父节点访问一次。如果有第三次访问,注意到我们的遍历过程是完全无状态的(步骤1和2判断的唯一是根据当前节点,没有任何其余状态变量)。那么必然会导致至少一个访问的重复,与现实矛盾。证明出一条边最多被访问两次。另外一条边最小要被访问一次,原因是很显然的。因此二叉树的遍历是O(E)的,其中E为树的边数,我们知道一个节点的节点数和边数的关系为N = E + 1,故得出迭代器遍历一棵红黑树的时间复杂度是O(N)。

     

    二、实验证明

     

           空口无凭,下面采用程序测试理论是否和实际相符。采用std::set<int>做为实验对象,对其分别插入和遍历10000、100000、1000000和10000000次,得到的时间消耗如下表:

     

    单位/微秒

     

    插入

    遍历

    10000次

    9070

    111

    100000次

    611655

    2641

    1000000次

    1575464

    26836

    10000000次

    12621089

    251810

     

    从遍历的时间消耗很容易看出遍历是线性时间的,并且对于比较小的遍历次数,遍历消耗的时间还会减小。

    但插入的时间消耗甚至小于线性时间(亚线性?)这可能与插入的数据有关吧,插入的数据是从0开始增1的,结果还有待分析。


    附录:

    测试程序环境

    系统:Windows 7。

    开发工具:VS208,Release编译。

    程序:

     

    #include <set>

    #include <boost/chrono.hpp>

    #include <iostream>

     

    void test(const int N)

    {

        std::cout << "N = " << N << std::endl;

        std::set<intsi;

        boost::chrono::high_resolution_clock::time_point t1 = boost::chrono::high_resolution_clock::now();

        for (int i = 0; i < Ni++)

        {

            si.insert(i);

        }

        boost::chrono::high_resolution_clock::time_point t2 = boost::chrono::high_resolution_clock::now();

        for (std::set<int>::iterator i = si.begin(); i != si.end(); ++i)

        {

            volatile int j = *i;

        }

        boost::chrono::high_resolution_clock::time_point t3 = boost::chrono::high_resolution_clock::now();

        std::cout << "insert time elapse " << boost::chrono::duration_cast<boost::chrono::microseconds>(t2 - t1) << std::endl;

        std::cout << "traverse time elapse " << boost::chrono::duration_cast<boost::chrono::microseconds>(t3 - t2) << std::endl;

    }

     

    int _tmain(int argc_TCHARargv[])

    {

        test(10000);

        test(100000);

        test(1000000);

        test(10000000);

         return 0;

    }

    展开全文
  • 红黑树 时间限制:3000ms | 内存限制:65535KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论》上可不是这么说...

     

    红黑树

    时间限制: 3000 ms  |  内存限制:65535 KB
    难度: 3
     
    描述

    什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。

    当然,这个是我说的。。。

    《算法导论》上可不是这么说的:

    如果一个二叉查找树满足下面的红黑性质,那么则为一个红黑树。

    1)每个节点或是红的,或者是黑的。

    2)每个叶子节点(NIL)是黑色的

    3)如果一个节点是红色的,那么他的两个儿子都是黑的。

    4)根节点是黑色的。

    5)对于每个节点,从该节点到子孙节点的所有路径上包含相同数目的黑色节点。

    我们在整个过程中会用到这些性质,当然,为了公平起见,其实即使你不知道这些性质,这个题目也是可以完成的(为什么不早说。。。。)。在红黑树的各种操作中,其核心操作被称为旋转,那么什么是旋转呢,我们来看一个例子:

    假设我们这里截取红黑树的一部分,放在左边,通过操作如果可以把他转化为右边的形式,那么我们就称将根为x的子树进行了左旋,反之我们称将根为Y的树进行了右旋:

    恰好慢板同学把自己红黑树弄乱了,然后请你帮忙进行修复,他将向你描述他的红黑树(混乱的。。。)。然后告诉他需要用哪种方式旋转某个节点。在你完成工作之后,直接向大黄提交新的树的中序遍历结果就好了。

     

    Hint:

    在这里好心的慢板同学给你简单的解释下样例:

    最开始的时候树的样子是这样的:

        0

      /    \

    1       2

    然后对于标号为0的节点进行右旋,结果将变为:

     1

      \

       0

        \

          2

    然后呢。。。

    中序遍历?这个是什么东西,哪个人可以告诉我下。。。。

     
    输入
    输入分两部分:
    第一部分:一个整数T(1<=T<=10),表示测试的组数。
    第二部分:第一行是一个数字N,表示红黑树的节点个数。0<N<10
    然后下面有N行,每行三个数字,每个数字的大小都在-1~N-1之间。第一个数字表示当前节点的标号,后面两个数字表示这个节点的左孩子和右孩子。如果是-1的话表示是空节点。对于所有的输入来说标号为0节点为根。
    然后是一个数字M表示需要旋转的次数。M<100
    接下来M行,每行有两个数字,分别表示你要旋转的节点标号和你需要的操作。标号的范围为0~n-1,如果标号后面的数字0,那么表示为左旋。如果是1,则表示右旋。
    输出
    每组测试返回N行数字,表示对树的中序遍历。在每组测试数据之后留一行空行。
    样例输入
    1
    3
    0 1 2
    1 -1 -1
    2 -1 -1
    1
    0 1
    样例输出
    1
    0
    2

    解题思路:红黑树有一个特性,不论怎么旋转都不能影响中序遍历,所以说这个题就只是输出中序遍历。

    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    typedef struct node{
        int left;
        int right;
    };
    struct node t[10];
    
    void inorder(int x){
        if(x!=-1){
            inorder(t[x].left);
            printf("%d\n",x);
            inorder(t[x].right);
        }
    }
    
    int main()
    {
        int tt;
        int a,b,c;
        scanf("%d",&tt);
        while(tt--){
            int n;
            memset(t,-1,sizeof(t));
            scanf("%d",&n);
            while(n--){
    
                scanf("%d %d %d",&a,&b,&c);
                t[a].left=b;
                t[a].right=c;
            }
            scanf("%d",&a);
            while(a--){
                scanf("%d %d",&b,&c);
            }
            inorder(0);
            printf("\n");
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/TWS-YIFEI/p/5821295.html

    展开全文
  • 红黑树 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论》上可不是这么...

    红黑树

    时间限制: 3000 ms  |  内存限制: 65535 KB
    难度: 3
    描述

    什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。

    当然,这个是我说的。。。

    《算法导论》上可不是这么说的:

    如果一个二叉查找树满足下面的红黑性质,那么则为一个红黑树。

    1)每个节点或是红的,或者是黑的。

    2)每个叶子节点(NIL)是黑色的

    3)如果一个节点是红色的,那么他的两个儿子都是黑的。

    4)根节点是黑色的。

    5)对于每个节点,从该节点到子孙节点的所有路径上包含相同数目的黑色节点。

    我们在整个过程中会用到这些性质,当然,为了公平起见,其实即使你不知道这些性质,这个题目也是可以完成的(为什么不早说。。。。)。在红黑树的各种操作中,其核心操作被称为旋转,那么什么是旋转呢,我们来看一个例子:

    假设我们这里截取红黑树的一部分,放在左边,通过操作如果可以把他转化为右边的形式,那么我们就称将根为x的子树进行了左旋,反之我们称将根为Y的树进行了右旋:

    恰好慢板同学把自己红黑树弄乱了,然后请你帮忙进行修复,他将向你描述他的红黑树(混乱的。。。)。然后告诉他需要用哪种方式旋转某个节点。在你完成工作之后,直接向大黄提交新的树的中序遍历结果就好了。

     

    Hint:

    在这里好心的慢板同学给你简单的解释下样例:

    最开始的时候树的样子是这样的:

        0

      /    \

    1       2

    然后对于标号为0的节点进行右旋,结果将变为:

     1

      \

       0

        \

          2

    然后呢。。。

    中序遍历?这个是什么东西,哪个人可以告诉我下。。。。

    输入
    输入分两部分:
    第一部分:一个整数T(1<=T<=10),表示测试的组数。
    第二部分:第一行是一个数字N,表示红黑树的节点个数。0<N<10
    然后下面有N行,每行三个数字,每个数字的大小都在-1~N-1之间。第一个数字表示当前节点的标号,后面两个数字表示这个节点的左孩子和右孩子。如果是-1的话表示是空节点。对于所有的输入来说标号为0节点为根。
    然后是一个数字M表示需要旋转的次数。M<100
    接下来M行,每行有两个数字,分别表示你要旋转的节点标号和你需要的操作。标号的范围为0~n-1,如果标号后面的数字0,那么表示为左旋。如果是1,则表示右旋。
    输出
    每组测试返回N行数字,表示对树的中序遍历。在每组测试数据之后留一行空行。
    样例输入
    1
    3
    0 1 2
    1 -1 -1
    2 -1 -1
    1
    0 1
    样例输出
    1
    0
    2
    题目链接: NYOJ 202 红黑树 【二叉树 中序遍历】

    红黑树性质   旋转后,中序 序列不变,直接中序遍历,旋转对结果无影响

    已AC代码:

    #include<cstdio>
    #include<cstring>
    #define M 20
    struct TREE{
    	int left,right;
    }tree[M];
    int n,m;
    void Tree(int rt)
    {
    	if(rt<0)
    		return ;
    	Tree(tree[rt].left);
    	printf("%d\n",rt);
    	Tree(tree[rt].right);
    }
    int main()
    {
    	int T,i,rt,a,b;
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d",&n);
    		for(i=0;i<n;++i)
    		{
    			scanf("%d",&rt);
    			scanf("%d%d",&tree[rt].left,&tree[rt].right);
    		}
    		scanf("%d",&m);
    		while(m--)//旋转的次数
    		{
    			scanf("%d%d",&a,&b);
    		}
    		Tree(0);
    	}
    	return 0;
    }


    展开全文
  • 红黑树的性质 1.节点是红色或黑色 2.根节点是黑色 3.所有叶子都是黑色。(叶子是NUIL节点) 4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从...

    红黑树的性质
     1.节点是红色或黑色

     2.根节点是黑色

     3.所有叶子都是黑色。(叶子是NUIL节点)

     4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

     5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    java实现

    package com.goat.api.data.structure;
    
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * BRTree (红黑树)
     *
     * 1.创建RBTree,定义颜色
     * 2.创建RBNode
     * 3.辅助方法定义:parentOf(node),isRed(node),isBlack(node),setRed(node),setBlack(node),inOrderPrint()
     * 4.左旋方法定义:leftRotate(node)
     * 5.右旋方法定义:rightRotate(node)
     * 6.公有插入方法定义:insert(K key,V value)
     * 7.私有插入方法定义:insert(RBNode node)
     * 8.插入重新平衡方法定义:insertBalance(RBNode node);
     * 9.测试红黑树的正确性
     * @param <K>
     * @param <V>
     */
    public class RBTree<K extends Comparable<K>, V> {
    
        /**红色*/
        private static final boolean RED = true;
    
        /**黑色*/
        private static final boolean BLACK = false;
    
        private RBNode root;
    
        /**
         * 获取节点的父节点
         * @param node
         * @return
         */
        private RBNode parentOf(RBNode node){
            return node == null ? null : node.parent;
        }
    
        /**
         * 获取节点的颜色
         * @param node
         * @return
         */
        private boolean colorOf(RBNode node){
            return node.color;
        }
    
        /**
         * 节点红色设置成黑色
         * @param node
         * @return
         */
        private void setBlack(RBNode node){
            if (node != null){
                node.color = BLACK;
            }
        }
    
        /**
         * 节点红色设置成红色
         * @param node
         * @return
         */
        private void setRed(RBNode node){
            if (node != null){
                node.color = RED;
            }
        }
    
        /**
         * 节点是否是红色
         * @param node
         * @return
         */
        private boolean isRed(RBNode node){
            return node == null ? false : node.color;
        }
    
        /**
         * 节点是否是黑色
         * @param node
         * @return
         */
        private boolean isBlack(RBNode node){
            return node == null ? false : node.color == BLACK;
        }
    
        /**
         * 前序遍历
         *           A
         *        |    \
         *       B      C
         *    |   \    |
         *    D    E   F
         * 访问顺序:根节点→左子树→右子树
         * 前序遍历的结果是:A→B→D→E→C→F
         */
        public void preOrderTraversal(){
            System.out.println("    递归:");
            preOrderTraversalRecursive(this.root);
            System.out.println();
            System.out.println("    非递归:");
            preOrderTraversalUnRecursive(this.root);
        }
    
        /**
         * 前序遍历
         * 递归
         * @param node
         */
        private void preOrderTraversalRecursive(RBNode node){
            if (node != null){
                System.out.print(node.k + "-");
                preOrderTraversalRecursive(node.left);
                preOrderTraversalRecursive(node.right);
            }
        }
    
        /**
         * 前序遍历
         * 非递归
         * @param node
         */
        private void preOrderTraversalUnRecursive(RBNode node){
            if (node == null) return;
            Stack<RBNode> stack = new Stack<RBNode>();
            stack.push(node);
            while (!stack.isEmpty()){
                node = stack.pop();
                System.out.print(node.k + "-");
                if (node.right != null){
                    stack.push(node.right);
                }
                if (node.left != null){
                    stack.push(node.left);
                }
            }
        }
    
        /**
         * 中序遍历
         *           A
         *        |    \
         *       B      C
         *    |   \    |
         *    D    E   F
         * 访问顺序:左子树→根节点→右子树
         * 前序遍历的结果是:D→B→E→A→F→C
         *
         * 一般遍历用到的都是中序遍历,因为中序遍历是有序的。
         */
        public void inOrderTraversal(){
            System.out.println("    递归:");
            inOrderTraversalRecursive(this.root);
            System.out.println();
            System.out.println("    非递归:");
            inOrderTraversalUnRecursive(this.root);
        }
    
        /**
         * 中序遍历递归的写法
         * @param node
         */
        private void inOrderTraversalRecursive(RBNode node) {
            if (node != null){
                inOrderTraversalRecursive(node.left);
                System.out.print(node.k + "-");
                inOrderTraversalRecursive(node.right);
            }
        }
    
        /**
         * 中序遍历非递归的写法
         * @param node
         */
        private void inOrderTraversalUnRecursive(RBNode node) {
            Stack<RBNode> stack = new Stack();
            while (node != null || !stack.isEmpty()){
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                if (!stack.isEmpty()) {
                    node = stack.pop();
                    System.out.print(node.k + "-");
                    node = node.right;
                }
            }
        }
    
        /**
         * 后序遍历
         *           A
         *        |    \
         *       B      C
         *    |   \    |
         *    D    E   F
         * 访问顺序:左子树→右子树→根节点
         * 后序遍历的结果是:D→E→B→F→C→A
         */
        public void postOrderTraversal(){
            System.out.println("    递归:");
            postOrderTraversalRecursive(this.root);
            System.out.println();
            System.out.println("    非递归1:");
            postOrderTraversalUnRecursive(this.root);
            System.out.println();
            System.out.println("    非递归2:");
            postOrderTraversalNoRecursive(this.root);
        }
    
        /**
         * 后序遍历递归写法
         */
        private void postOrderTraversalRecursive(RBNode node){
            if (node != null){
                postOrderTraversalRecursive(node.left);
                postOrderTraversalRecursive(node.right);
                System.out.print(node.k + "-");
            }
        }
    
        /**
         * 后序遍历非递归写法
         */
        private void postOrderTraversalUnRecursive(RBNode node){
            Stack<RBNode> stack1 = new Stack<RBNode>();
            Stack<RBNode> stack2 = new Stack<RBNode>();
            stack1.push(node);
            while (!stack1.isEmpty()){
                node = stack1.pop();
                stack2.push(node);
                if (node.left != null){
                    stack1.push(node.left);
                }
                if (node.right != null){
                    stack1.push(node.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().k + "-");
            }
        }
    
        /**
         * 非递归的另外一种写法
         * @param node
         */
        private void postOrderTraversalNoRecursive(RBNode node) {
            if (node != null){
                Stack<RBNode> stack = new Stack();
                stack.push(node);
                RBNode tmp;
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.left != null && node != tmp.left && node != tmp.right) {
                        stack.push(tmp.left);
                    } else if (tmp.right != null && node != tmp.right) {
                        stack.push(tmp.right);
                    } else {
                        System.out.print(stack.pop().k + "-");
                        node = tmp;
                    }
                }
            }
        }
    
        /**
         * BFS(广度优先搜索)
         *           A
         *        |    \
         *       B      C
         *     |   \   |
         *    D    E   F
         * 访问顺序:先访问上一层,在访问下一层,一层一层的往下访问
         * BFS遍历的结果:A→B→C→D→E→F
         * @param node
         */
        public void breadthFirstSearch(){
            System.out.println("    递归:");
            breadthFirstSearchRecursive(this.root);
            System.out.println();
            System.out.println("    非递归:");
            breadthFirstSearchUnRecursive(this.root);
        }
    
        /**
         * 广度优先搜索
         * 递归写法
         * @param node
         */
        private void breadthFirstSearchRecursive(RBNode node){
            int depth = depth(node);
            for (int i = 0; i < depth; i++){
                printByLevel(node,i);
            }
        }
    
        /**
         * 按层打印树
         * @param node
         * @param level
         */
        private void printByLevel(RBNode node, int level) {
            if (node != null){
                if (level == 0){
                    System.out.print(node.k + "-");
                }else{
                    printByLevel(node.left,level - 1);
                    printByLevel(node.right,level - 1);
                }
            }
        }
    
        /**
         * 获取树的深度
         * @param node
         * @return
         */
        private int depth(RBNode node) {
            if (node == null) return 0;
            int leftDepth = depth(node.left);
            int rightDepth = depth(node.right);
            return Math.max(leftDepth,rightDepth) + 1;
        }
    
        /**
         * 广度优先搜索
         * 非递归写法
         * @param node
         */
        private void breadthFirstSearchUnRecursive(RBNode node){
            if (node != null){
                LinkedList<RBNode> list = new LinkedList();
                list.add(node);
                RBNode tmp;
                while(!list.isEmpty()){
                    tmp = list.poll();
                    System.out.print(tmp.k + "-");
                    if (tmp.left != null){
                        list.add(tmp.left);
                    }
                    if (tmp.right != null){
                        list.add(tmp.right);
                    }
                }
            }
        }
    
        /**
         * DFS(深度优先搜索))
         *           A
         *        |    \
         *       B      C
         *     |   \   |
         *    D    E   F
         * 访问顺序:先访根节点,然后左结点,一直往下,直到最左结点没有子节点的时候然后往上退一步到父节点,
         *          然后父节点的右子节点在重复上面步骤……
         * BFS遍历的结果:A→B→D→E→C→F
         * @param node
         */
        public void depthFirstSearch(){
            System.out.println("    递归:");
            depthFirstSearchRecursive(this.root);
            System.out.println();
            System.out.println("    非递归:");
            depthFirstSearchUnRecursive(this.root);
        }
    
        /**
         * 深度优先搜索
         * 递归写法
         * @param node
         */
        private void depthFirstSearchRecursive(RBNode node) {
            if (node != null){
                System.out.print(node.k + "-");
                depthFirstSearchRecursive(node.left);
                depthFirstSearchRecursive(node.right);
            }
        }
    
        /**
         * 深度优先搜索
         * 非递归写法
         * @param node
         */
        private void depthFirstSearchUnRecursive(RBNode node) {
            Stack<RBNode> stack = new Stack<RBNode>();
            stack.push(node);
            while(!stack.isEmpty()){
                node = stack.pop();
                System.out.print(node.k + "-");
                if (node.right != null){
                    stack.push(node.right);
                }
                if (node.left != null){
                    stack.push(node.left);
                }
            }
        }
    
        public void printTree(){
            printTree(this.root);
        }
    
        public void printTree(RBNode node){
            if (node == null)
                return;
            LinkedList<RBNode> list = new LinkedList<RBNode>();//链表,这里我们可以把它看做队列
            list.add(node);//相当于把数据加入到队列尾部
            boolean line = false;
            while (!list.isEmpty()) {
                RBNode n = list.poll();//poll方法相当于移除队列头部的元素
                if (line){
                    if (n.color == true){
                        System.out.print(n.k + " - RED      ");
                    }else {
                        System.out.print(n.k + " - BLACK        ");
                    }
                }else{
                    if (n.color == true){
                        System.out.println(n.k + " - RED        ");
                    }else {
                        System.out.println(n.k + " - BLACK      ");
                    }
                }
                if (n.left != null)
                    list.add(n.left);
                if (n.right != null){
                    list.add(n.right);
                }
                if (n.left != null && n.right != null){
                    line = true;
                }else{
                    line = false;
                }
            }
        }
    
        /**
         * 左旋方法
         * 示意图:
         *       P                              P
         *       |                              |
         *       x                              y
         *    |    \        ------>          |    \
         *   xl     y                       x      ry
         *        |   \                   |   \
         *       ly    ry                xl    ly
         * 1.将y的左子节点(ly)的父节点更新为x(ly要挂在x的右边),并将ly的父节点更新为x(双向关联的)
         * 2.如果x父节点不为空,将y的父节点更新成x的父节点,如果x是x父节点的左节点,则更新x父节点
         *   的左子节点为y,否则(不是左子节点就是右子节点)则更新x的父节点的右子节点为y(记住节点之
         *   间的关系都是双向的,所以更新的时候要双向更新)
         * 3.将x的父节点更新为y,将y的左子节点更新为x.
         * @param node 以node为当前节点左旋
         */
        private void leftRotate(RBNode x){
            RBNode y = x.right;
            //第一步
            x.right = y.left;
            if (y.left != null)
                y.left.parent = x;
            //第二步
            y.parent = x.parent;
            if (x.parent != null){
                if (x == x.parent.left)
                    x.parent.left = y;
                else
                    x.parent.right = y;
            }else{
                this.root = y;
            }
            //第三步
            x.parent = y;
            y.left = x;
        }
    
        /**
         * 右旋方法
         * 示意图:
         *              P                               P
         *              |                               |
         *              y                               x
         *           |    \         ------>          |    \
         *          x      ry                       xl     y
         *        |   \                                  |   \
         *      xl    ly                                ly    ry
         * 1.将x的右子节点(ly)的父节点更新为y(ly要挂在y的左边),并将ly的父节点更新为y(双向关联的)
         * 2.如果y父节点不为空,将x的父节点更新成y的父节点,如果y是y父节点的左节点,则更新y父节点
         *   的左子节点为x,否则(不是左子节点就是右子节点)则更新y的父节点的右子节点为x(记住节点之
         *   间的关系都是双向的,所以更新的时候要双向更新)
         * 3.将y的父节点更新为x,将x的右子节点更新为y.
         * @param node 以node为当前节点左旋
         */
        private void rightRotate(RBNode y){
            //第一步
            RBNode x = y.left;
            y.left = x.right;
            if (x.right != null)
                x.right.parent = y;
            //第二步
            x.parent = y.parent;
            if (y.parent != null){
                if (y == y.parent.left)
                    y.parent.left = x;
                else
                    y.parent.right = x;
            }else {
                this.root = x;
            }
            //第三步
            y.parent = x;
            x.right = y;
        }
    
        /**
         * 从指定节点开始搜索指定k对应的节点
         * @param node
         * @param k
         * @return
         */
        private RBNode search(RBNode node, K k) {
            if (node == null) return null;
            int cmp;
            if ((cmp = node.k.compareTo(k)) == 0){
                return node;
            }else if (cmp > 0){
                node = search(node.left, k);
            }else{
                node = search(node.right, k);
            }
            return node;
        }
    
        /**
         * 根据K,V插入
         * @param k 插入的键
         * @param v 插入的值
         * @return 如果替换,则返回原值。否则返回null
         */
        public V insert(K k,V v){
            return insert(new RBNode(k, v,RED));
        }
    
        /**
         * 根据Node插入
         * @param node 插入节点
         * @return 如果替换,则返回原值。否则返回null
         */
        private V insert(RBNode node){
            RBNode parent = null;
            RBNode x = this.root;
            while (x != null){//从根节点开始遍历,x!=null,则说明没找到叶节点。
                parent = x;//因为循环跳出后x为叶节点null,所以提前保存期父节点。
                int cmp = node.k.compareTo(x.k);//当前节点的k与x的k比较
                if (cmp > 0){//大于0,则将x.right赋值给x继续遍历
                    x = x.right;
                }else if (cmp == 0){//等于0说明找到了相同的key,直接替换原值
                    Object old = x.v;
                    x.v = node.v;
                    return (V)old;
                }else {
                    x = x.left;//小于0,则将x.left赋值给x继续遍历
                }
            }
            node.parent = parent;//跳出循环后说明找到了,存放的位置(对应叶节点)。将其parent赋值给node的parent。
            if (parent != null){
                if (parent.k.compareTo(node.k) > 0){//比较parent.key与node的key,大于0则说明节点存放于父节点的左子节点
                    parent.left = node;
                }else {
                    parent.right = node;//否则存放于右子节点
                }
            }else{
                this.root = node;
            }
            //至此插入完成
    
            //调整红黑树,使其重新平衡
            insertReBalance(node);
            return null;
        }
    
        /**
         * 插入后重新平衡红黑树
         * 分情况:
         *        1.红黑树为空树(root == null),第一次插入直接将节点染色为黑色,赋值给根节点。
         *        2.插入节点的key已经存在,直接替换原值。不需要处理。
         *        3.插入节点的父节点为黑色,因为插入路径中黑色节点没有变化,红黑树依然平衡,不需要处理。
         *
         *        第四种情况需要我们自己处理:
         *        4.插入节点的父节点为红色。
         *              4.1.叔叔节点存在,且为红色(父-叔 双红)。将父节点染色为黑色,将爷爷节点染色为红色。再以爷爷节点为当前节点处理。
         *              4.2.叔叔节点不存在或者为黑色,且父节点为爷爷节点的左子节点。
         *                  4.2.1.插入节点为父节点的左子节点。(LL情况),将父节点染为黑色,将爷爷节点染为红色,然后以爷爷节点右旋,就完成了。
         *                  4.2.2.插入节点为父节点的右子节点。(LR情况),以父节点为当前节点左旋,得到LL情况(4.2.1)。然后按照4.2.1处理
         *              4.3.叔叔节点不存在或者为黑色,且父节点为爷爷节点的右子节点。
         *                  4.3.1.插入节点为父节点的右子节点。(RR情况),将父节点染为黑色,将爷爷节点染为红色,然后以爷爷节点左旋,就完成了。
         *                  4.3.2.插入节点为父节点的左子节点。(RL情况),以父节点为当前节点右旋,得到RR情况(4.3.1)。然后按照4.3.1处理
         * @param node
         */
        private void insertReBalance(RBNode node){
            setBlack(this.root);
            RBNode parent = parentOf(node);
            RBNode grandParent = parentOf(parent);
            if (parent != null && isRed(parent)){//如果父节点为红色,父节点为红色时一定存在爷爷节点,因为根节点一定为黑色。
                RBNode uncle = null;
                if (parent == grandParent.left){//父节点是爷爷节点的左节点
                    uncle = grandParent.right;//则叔叔节点为爷爷节点的右节点
                    if (uncle != null && isRed(uncle)){//4.1.叔叔节点存在,且为红色(父-叔 双红)。将父节点染色为黑色,将爷爷节点染色为红色。再以爷爷节点为当前节点处理。
                        setBlack(parent);
                        setBlack(uncle);
                        setRed(grandParent);
                        insertReBalance(grandParent);
                        return;
                    }
                    if (uncle == null || isBlack(uncle)){//4.2.叔叔节点不存在或者为黑色
                        if (node == parent.left){//4.2.1.插入节点为父节点的左子节点(LL),将父节点染为黑色,将爷爷节点染为红色,然后以爷爷节点右旋,就完成了。
                            setBlack(parent);
                            setRed(grandParent);
                            rightRotate(grandParent);
                        }
                        if (node == parent.right){//4.2.2.插入节点为父节点的右子节点(LR),以父节点为当前节点左旋,得到LL情况(4.2.1)。然后按照4.2.1处理
                            leftRotate(parent);
                            insertReBalance(parent);
                            return;
                        }
                    }
                }else{//否则父节点为爷爷节点的右子节点
                    uncle = grandParent.left;//则叔叔节点为爷爷节点的左子节点
                    if (uncle != null && isRed(uncle)){//4.1.叔叔节点存在,且为红色(父-叔 双红)。将父节点染色为黑色,将爷爷节点染色为红色。再以爷爷节点为当前节点处理。
                        setBlack(parent);
                        setBlack(uncle);
                        setRed(grandParent);
                        insertReBalance(grandParent);
                        return;
                    }
                    if (uncle == null || isBlack(uncle)){//4.3.叔叔节点不存在或者为黑色,且父节点为爷爷节点的右子节点。
                        if (node == parent.right){//4.3.1.插入节点为父节点的右子节点。(RR情况),将父节点染为黑色,将爷爷节点染为红色,然后以爷爷节点左旋,就完成了。
                            setBlack(parent);
                            setRed(grandParent);
                            leftRotate(grandParent);
                            return;
                        }
                        if (node == parent.left){//4.3.2.插入节点为父节点的左子节点。(RL情况),以父节点为当前节点右旋,得到RR情况(4.3.1)。然后按照4.3.1处理
                            rightRotate(parent);
                            insertReBalance(parent);
                            return;
                        }
                    }
                }
            }
        }
    
        /**
         * 树节点
         * @param <K>
         * @param <V>
         */
        static class RBNode<K extends Comparable<K>, V>{
    
            private RBNode parent;
    
            private RBNode left;
    
            private RBNode right;
    
            private boolean color;
    
            private K k;
    
            private V v;
    
            public RBNode() {}
    
            public RBNode(K k, V v, boolean color){
                this.k = k;
                this.v = v;
                this.color = color;
            }
    
            public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K k, V v) {
                this.parent = parent;
                this.left = left;
                this.right = right;
                this.color = color;
                this.k = k;
                this.v = v;
            }
    
            public RBNode getParent() {
                return parent;
            }
    
            public void setParent(RBNode parent) {
                this.parent = parent;
            }
    
            public RBNode getLeft() {
                return left;
            }
    
            public void setLeft(RBNode left) {
                this.left = left;
            }
    
            public RBNode getRight() {
                return right;
            }
    
            public void setRight(RBNode right) {
                this.right = right;
            }
    
            public boolean isColor() {
                return color;
            }
    
            public void setColor(boolean color) {
                this.color = color;
            }
    
            public K getK() {
                return k;
            }
    
            public void setK(K k) {
                this.k = k;
            }
    
            public V getV() {
                return v;
            }
    
            public void setV(V v) {
                this.v = v;
            }
        }
    }
    
    

    测试代码

    package com.goat.api.data.structure;
    
    import java.util.Random;
    import java.util.Scanner;
    
    public class RBTreeTest {
        public static void main(String[] args) {
            RBTree<Integer, String> tree = new RBTree();
            tree.insert(1,"1");
            tree.insert(3,"1");
            tree.insert(23,"1");
            tree.insert(7,"1");
            tree.insert(234,"1");
            tree.insert(676,"1");
            tree.insert(2,"1");
            tree.insert(78,"1");
            tree.insert(12,"1");
            tree.insert(19,"1");
            System.out.println("前序遍历:");
            tree.preOrderTraversal();
            System.out.println();
            System.out.println("中序遍历:");
            tree.inOrderTraversal();
            System.out.println();
            System.out.println("后序遍历:");
            tree.postOrderTraversal();
            System.out.println();
            System.out.println("广度优先搜索:");
            tree.breadthFirstSearch();
            System.out.println();
            System.out.println("深度优先搜索:");
            tree.depthFirstSearch();
            System.out.println();
            tree.printTree();
        }
    }
    
    展开全文
  • NYOJ202 红黑树 【中序遍历

    千次阅读 2014-06-22 16:25:37
    红黑树 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论》上可不是这么...
  • 红黑树、B+树都是在搜索这块利用很多;用于java的一些hashmap结构,红黑树B+树主要用于在文件数据库 1、红黑树 参考:https://www.bilibili.com/video/av75529951?p=1 红黑树(Red Black Tree) 是一种自平衡二叉...
  • 红黑树的实现与遍历

    千次阅读 2014-08-24 20:52:41
    // 另一个类,仅用于测试,可以对红黑树进行遍历 }; ;">3、红黑树类的定义: ;">template class RBTree { public: RBTree():root(0){} ~RBTree(){} void insert(const T& elem); // 插入元素 void erase...
  • 红黑树时间限制:3000 ms | 内存限制:65535 KB难度:3描述什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。当然,这个是我说的。。。《算法导论》上可不是这么说的:如果一个...
  • 红黑树 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论》上可不是...
  • NYOJ 202 红黑树 数组模拟中序遍历

    千次阅读 2012-05-09 08:35:21
    题目其实在迷惑人了,红黑树经过旋转后中序遍历其实是不变的,所以不用管下面的旋转,直接输出中序遍历就可以了。可以用数组模拟实现树的中序遍历。  题目连接:...
  • ???? 想要了解更多不掺水的原创,请戳上方蓝色字体:政采云前端团队 关注我们吧~本文首发于政采云前端团队博客:通俗易懂的红黑树图解(上)...所以学习红黑树之前,需要先了解一下二叉查找树的知...
  • 红黑树 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论》上可不是...
  • 左倾红黑树在经典红黑树上加了一个限制:红色结点只能是左孩子。建议学习红黑树从2-3树——左倾红黑树——经典红黑树学起,方便理解及进一步学习。下面记录一下我学红黑树的过程及记录: 一、左倾红黑树的定义 左倾...
  • 红黑树 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论...
  • 红黑树 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。 当然,这个是我说的。。。 《算法导论》上可不是这么说的...
  • 红黑树  红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,因而近似于...
  • C语言 红黑树插入/删除/查找/遍历

    千次阅读 2018-12-14 18:31:04
    1 红黑树介绍 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的...
  • //反树型化方法仅仅是遍历然后创建的新链表,代码易读就不再说明了 final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != ...
  • //定义红黑树的节点 private class TreeNood<T extends Comparable>{ TreeNood<T> left; TreeNood<T> right; TreeNood<T> parent; T value; String color; } }
  • 红黑树

    千次阅读 多人点赞 2019-12-03 16:48:25
    红黑树 从 234 树 到 红黑树:https://blog.csdn.net/asdfsadfasdfsa/article/details/86500552 定义 2-3-4 树和红黑树是完全等价的,由于绝大多数编程语言直接实现2-3-4树会非常繁琐,所以一般是通过实现红黑树来...
  • 红黑树插入建立算法

    2014-12-17 16:35:27
    算法导论红黑树插入算法来建立一颗红黑树并且遍历输出
  • nyist 202 红黑树(二叉树中序遍历)

    千次阅读 2013-08-08 10:42:56
    旋转对中序遍历没有影响,直接中序输出即可。 #include #include using namespace std; int n; struct Shu { int left,rigth; }shu[1000005]; int zhong(int id) { if(id>=0) { zhong(shu[id].left); cout...
  • 红黑树时间限制:3000 ms | 内存限制:65535 KB难度:3描述什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。当然,这个是我说的。。。《算法导论》上可不是这么说的:如果一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 68,689
精华内容 27,475
关键字:

红黑树如何遍历