红黑树

千次阅读 2019-11-16 14:39:10

红黑树


Algorithms code：https://algs4.cs.princeton.edu/30searching/
	RedBlackBST：https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
	二分搜索树：https://blog.csdn.net/qq_40794973/article/details/102937184 
	AVL树：https://blog.csdn.net/qq_40794973/article/details/102978494 







Algorithms(Fourth Edition)：https://baike.baidu.com/item/图灵程序设计丛书：算法
	计算机编程的艺术：https://baike.baidu.com/item/计算机程序设计艺术/6340965?fr=aladdin
	Donald Ervin Knuth：https://baike.baidu.com/item/唐纳德·克努特/1436781?fromtitle=高德纳&fromid=2155233


1 理解2-3树 


红黑树与2-3树的等价性
	理解了2-3树和红黑树之间的关系后，红黑树并不难！
	学习2-3树，不仅对于理解红黑树有帮助
	对于理解B类树，也是有巨大帮助的！




1.1 了解2-3 树如何维持绝对的平衡

添加节点永远不会添加到一个空的位置









演示一种极端情况



2 红黑树与2-3树的等价性


根节点要么是2节点要么是3节点





黑色节点的右孩子一定是黑色的






3 红黑树添加新元素


2-3树中添加一个新元素
	或者添加进 2-节点，形成一个 3-节点 
	或者添加进 3-节点，暂时形成一个 4-节点
永远添加红色节点


3.1 维持根节点为黑色



// 向红黑树中添加新的元素(key, value)
public void add(K key, V value) {
    root = add(root, key, value);
    root.color = BLACK; // 最终根节点为黑色节点
}

 

3.2 左旋转


2-3树：新的元素放入2节点中，把2节点转变为3节点






//   node                     x
//  /   \     左旋转         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
private Node leftRotate(Node node) {
    Node x = node.right;
    // 左旋转
    node.right = x.left;
    x.left = node;
    x.color = node.color;
    node.color = RED;
    return x;
}

 

3.3 颜色翻转


向红黑树中的“3-node"添加元素




// 颜色翻转
private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}

 

3.4 右旋转



//     node                   x
//    /   \     右旋转       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
private Node rightRotate(Node node) {
    Node x = node.left;
    // 右旋转
    node.left = x.right;
    x.right = node;
    x.color = node.color;
    node.color = RED;
    return x;
}

3.5 另一种情况


组合前面子过程实现这种情况




3.6 组合逻辑



// 向红黑树中添加新的元素(key, value)
public void add(K key, V value) {
    root = add(root, key, value);
    root.color = BLACK; // 最终根节点为黑色节点
}
// 向以node为根的红黑树中插入元素(key, value)，递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value) {
    if (node == null) {
        size++;
        return new Node(key, value); // 默认插入红色节点
    }
    if (key.compareTo(node.key) < 0) {
        node.left = add(node.left, key, value);
    } else if (key.compareTo(node.key) > 0) {
        node.right = add(node.right, key, value);
    } else { // key.compareTo(node.key) == 0
        node.value = value;
    }

    //是否需要左旋转
    if (isRed(node.right) && !isRed(node.left)) {
        node = leftRotate(node);
    }
    //是否需要右旋转
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rightRotate(node);
    }
    //是否需要颜色翻转
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }
    return node;
}

4 红黑树中删除节点


待实现...


5 性能测试

5.1 红黑树的性能总结



5.2 代码测试 


只有添加操作，添加的元素随机


 int n = 20000000;
//int n = 20000000;
//Random random = new Random(n);
//ArrayList<Integer> testData = new ArrayList<>(n);
//for (int i = 0; i < n; i++) {
//    testData.add(random.nextInt(Integer.MAX_VALUE));
//}
 Test BST
//long startTime = System.nanoTime();
//BST<Integer, Integer> bst = new BST<>();
//for (Integer x : testData) {
//    bst.add(x, null);
//}
//long endTime = System.nanoTime();
//double time = (endTime - startTime) / 1000000000.0;
//System.out.println("BST: " + time + " s");
 Test AVL
//startTime = System.nanoTime();
//AVLTree<Integer, Integer> avl = new AVLTree<>();
//for (Integer x : testData) {
//    avl.add(x, null);
//}
//endTime = System.nanoTime();
//time = (endTime - startTime) / 1000000000.0;
//System.out.println("AVL: " + time + " s");
 Test RBTree
//startTime = System.nanoTime();
//RBTree<Integer, Integer> rbt = new RBTree<>();
//for (Integer x : testData) {
//    rbt.add(x, null);
//}
//endTime = System.nanoTime();
//time = (endTime - startTime) / 1000000000.0;
//System.out.println("RBTree: " + time + " s");

 


 只有添加操作，从小到大添加元素


//int n = 20000000;
//ArrayList<Integer> testData = new ArrayList<>(n);
//for(int i = 0 ; i < n ; i ++) {
//    testData.add(i);
//}
 Test AVL
//long startTime = System.nanoTime();
//AVLTree<Integer, Integer> avl = new AVLTree<>();
//for (Integer x: testData) {
//    avl.add(x, null);
//}
//long endTime = System.nanoTime();
//double time = (endTime - startTime) / 1000000000.0;
//System.out.println("AVL: " + time + " s");
 Test RBTree
//startTime = System.nanoTime();
//RBTree<Integer, Integer> rbt = new RBTree<>();
//for (Integer x: testData) {
//    rbt.add(x, null);
//}
//endTime = System.nanoTime();
//time = (endTime - startTime) / 1000000000.0;
//System.out.println("RBTree: " + time + " s");

 

6 更多和红黑树相关的问题


红黑树中删除节点 //未实现



前面实现的红黑树正是左倾红黑树





 右倾红黑树




 


红黑树统计性能更优

另一种统计性能优秀的树结构：Splay Tree（伸展树）

局部性原理：刚被访问的內容下次高概率被再次访问



基于红黑树的Map和set

java.util中的TreeMap和 TreeSet基于红黑树



红黑树的其他实现

算法导论中红黑树的实现


public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private class Node {
        public K key;
        public V value;
        public Node left, right;
        public boolean color;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            color = RED;
        }
    }
    private Node root;
    private int size;
    public RBTree() {
        root = null;
        size = 0;
    }
    public int getSize() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    // 判断节点node的颜色
    private boolean isRed(Node node) {
        if (node == null) {
            return BLACK;
        }
        return node.color;
    }
    //   node                     x
    //  /   \     左旋转         /  \
    // T1   x   --------->   node   T3
    //     / \              /   \
    //    T2 T3            T1   T2
    private Node leftRotate(Node node) {
        Node x = node.right;
        // 左旋转
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }
    //     node                   x
    //    /   \     右旋转       /  \
    //   x    T2   ------->   y   node
    //  / \                       /  \
    // y  T1                     T1  T2
    private Node rightRotate(Node node) {
        Node x = node.left;
        // 右旋转
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }
    // 颜色翻转
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
    // 向红黑树中添加新的元素(key, value)
    public void add(K key, V value) {
        root = add(root, key, value);
        root.color = BLACK; // 最终根节点为黑色节点
    }
    // 向以node为根的红黑树中插入元素(key, value)，递归算法
    // 返回插入新节点后红黑树的根
    private Node add(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value); // 默认插入红色节点
        }
        if (key.compareTo(node.key) < 0) {
            node.left = add(node.left, key, value);
        } else if (key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, value);
        } else { // key.compareTo(node.key) == 0
            node.value = value;
        }
        if (isRed(node.right) && !isRed(node.left)) {
            node = leftRotate(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rightRotate(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }
        return node;
    }
    // 返回以node为根节点的二分搜索树中，key所在的节点
    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.equals(node.key)) {
            return node;
        } else if (key.compareTo(node.key) < 0) {
            return getNode(node.left, key);
        } else { // if(key.compareTo(node.key) > 0)
            return getNode(node.right, key);
        }
    }
    public boolean contains(K key) {
        return getNode(root, key) != null;
    }
    public V get(K key) {
        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }
    public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if (node == null) {
            throw new IllegalArgumentException(key + " doesn't exist!");
        }
        node.value = newValue;
    }
}

收起

展开全文

程序员面试、算法研究、编程艺术、红黑树、机器学习5大系列集锦

万次阅读 多人点赞 2011-06-14 12:11:00

程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结作者：July--结构之法算法之道blog之博主。时间：2010年10月-2018年5月，一直在不断更新中.. 出处：...

程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结

作者：July--结构之法算法之道blog之博主。
时间：2010年10月-2018年5月，一直在不断更新中..
出处：http://blog.csdn.net/v_JULY_v 。
说明：本博客中部分文章经过不断修改、优化，已集结出版成书《编程之法：面试和算法心得》。

前言
开博4年有余，回首这4年，自己的研究兴趣从最初的编程、面试、数据结构、算法，转移到最近的数据挖掘、机器学习之上，而自己在本blog上也着实花费了巨大的时间和精力，写的东西可能也够几本书的内容了。然不管怎样，希望我能真真正正的为读者提供实实在在的价值与帮助。

下面，敬请观赏。有任何问题，欢迎随时不吝指正(同时，若你也能帮助回复blog内留言的任何朋友的问题，欢迎你随时不吝分享&回复，我们一起讨论，互帮互助，谢谢)。

无私分享，造福天下
以下是本blog内的微软面试100题系列，经典算法研究系列，程序员编程艺术系列，红黑树系列，及数据挖掘十大算法等5大经典原创系列作品与一些重要文章的集锦：
一、微软面试100题系列

横空出世，席卷Csdn--评微软等数据结构+算法面试100题 （微软面试100题系列原题+答案索引）
微软100题 （微软面试完整第1-100题）
微软面试100题2010年版全部答案集锦（含下载地址）
全新整理：微软、谷歌、百度等公司经典面试100题[第101-160题]
全新整理：微软、Google等公司的面试题及解答[第161-170题]
十道海量数据处理面试题与十个方法大总结（十道海量数据处理面试题）
海量数据处理面试题集锦与Bit-map详解（十七道海量数据处理面试题）
教你如何迅速秒杀掉：99%的海量数据处理面试题（海量数据处理PDF）
九月腾讯，创新工场，淘宝等公司最新面试三十题（第171-200题）（2011年度九月最新面试三十题）
十月上旬百度，阿里巴巴，迅雷搜狗最新面试七十题（第201-270题）（2011年度十月上旬七十题）
十月下旬腾讯，网易游戏，百度最新校园招聘笔试题集锦(第271-330题) （2011年度十月下旬校招）
九月十月百度人搜，阿里巴巴，腾讯华为笔试面试八十题(第331-410题) （2012年度笔试面试八十题）
九月百度，迅雷，华为，阿里巴巴，最新校招笔试面试十(第411-470题) （2013年度校招笔试面试十题）

上述微软面试100题系列(共计11篇文章，300多道面试题)的PDF文档近期已经制作出来，其下载地址为：http://download.csdn.net/detail/v_july_v/4583815。

二、十五个经典算法研究与总结、目录+索引

最新的十五个经典算法研究的PDF文档0积分下载地址如下(1个月5000+人次下载)：http://download.csdn.net/detail/v_july_v/4478027。

「此外原来的十三个经典算法研究[带目录+标签]的PDF文档，Csdn下载地址：http://download.csdn.net/source/3427838；新浪爱问共享下载地址：http://ishare.iask.sina.com.cn/f/16968707.html 」。

三、程序员编程艺术第一~四十章集锦与总结

程序员编程艺术第1~37章带标签的最新PDF下载地址为（3天3000人下载）：http://download.csdn.net/detail/v_july_v/6694053。

编程艺术github优化版阅读地址：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/Readme.md。

重大消息：经过反复修改、优化，编程艺术系列最终成书出版，并改名为《编程之法：面试和算法心得》，目前京东、当当、亚马逊等各大网店均已有现货销售。京东抢购地址：http://item.jd.com/11786791.html。

四、红黑树、B树、R树、Trie树

五、数学·数据挖掘 ·机器学习·深度学习系列

六、其它重要文章节选

6.1、经典数据结构 & 算法系列：
精通八大排序算法系列：一之续、快速排序算法的深入分析

几个最短路径算法Floyd、Dijkstra、Bellman-Ford、SPFA的比较

6.4、推荐 & 搜索算法系列：
细数二十世纪最伟大的10大算法
当今世界最为经典的十大算法--投票进行时（本blog将评选出当今世界最为经典的十大算法）
推荐引擎算法学习导论
搜索引擎技术之概要预览

Machine Learning读书会,面试算法讲座,创业活动,算法班(14年10月) （含所有线下讲座PPT 集锦）
三五杆枪，可干革命，三五个人，可以创业
结构之法算法之道blog博文集锦第6、第7期CHM文件第8期第9期下载（第9期截止到2014年12月9日）
....

后记
世上本无路，走的人多了，也就成了路。世上本无免费的午餐，分享的人多了，也就造就了开源的辉煌。

如果你发现了本blog中的任何一个错误，漏洞，bug，和问题，请一定不吝指正，thanks。此外，你可以永久通过搜索引擎搜索本博客名称的前4个字，即：“结构之法” 这4个关键字，进入本博客。

最后，感谢CSDN，感谢所有一直以来关注本blog的所有朋友。谢谢大家，谢谢。

转发送书

欢迎大家转发下条微博：http://weibo.com/1580904460/zqzTgyAW3，我会不定期抽奖，经典IT图书大赠送（同时，下面个人最喜欢的三篇文章已收录到今2015年10月14日上市销售的我的新书《编程之法：面试和算法心得》中：http://item.jd.com/11786791.html）：

2015年，July团队正式创业，上半年推出在线教育网站：https://www.julyedu.com/category/index（面试、算法、机器学习在线课程）。July、二零一五年九月十五日。

另，我的新书《编程之法：面试和算法心得》终于在2015年10月14日上架开卖了！京东抢购地址：http://item.jd.com/11786791.html。目前，京东、当当、亚马逊等各大网店均已有现货销售。

收起

展开全文

算法

红黑树

1 理解2-3树

1.1 了解2-3 树如何维持绝对的平衡

2 红黑树与2-3树的等价性

3 红黑树添加新元素

3.1 维持根节点为黑色

3.2 左旋转

3.3 颜色翻转

3.4 右旋转

3.5 另一种情况

3.6 组合逻辑

4 红黑树中删除节点

5 性能测试

5.1 红黑树的性能总结

5.2 代码测试

6 更多和红黑树相关的问题

程序员面试、算法研究、编程艺术、红黑树、机器学习5大系列集锦

程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结

转发送书

红黑树

hcsa day4

java注解和反射的个人学习笔记

MySQL 四类管理日志（详解及高阶配置）

（超详细笔记记录）从头开始学Spring 其二

基于FPGA的verilog语言的数码管显示计数程序

Java内存区域--运行时数据区

jquery map方法总结

PPT大神之路高清教程

AcWing 1089. 烽火传递(单调队列优化dp）

2021年系统分析师系列课

【爱码农】C#制作MDI文本编辑器

唯恩.rar电气设备选型资料大全（适合刚刚入行的电气工程师对设备进行选型规划）详解报价

信息安全风险评估培训教材.ppt

腾讯PCG暑期实习-客户端开发面经

Mycat 实现 MySQL的分库分表、读写分离、主从切换

自制的mnist数据集

工程大面向对象课程设计作品（完整）（也适用于软件工程大实验）.7z

教你如何摆脱负债上岸，超详细(视频课程)

MySQL 数据库权限管理（用户高级管理和精确访问控制）

小爱同学windows10版.Appx

红黑树

1 理解2-3树

1.1 了解2-3 树如何维持绝对的平衡

2 红黑树与2-3树的等价性

3 红黑树添加新元素

3.1 维持根节点为黑色

3.2 左旋转

3.3 颜色翻转

3.4 右旋转

3.5 另一种情况

3.6 组合逻辑

4 红黑树中删除节点

5 性能测试

5.1 红黑树的性能总结

5.2 代码测试

6 更多和红黑树相关的问题

程序员面试、算法研究、编程艺术、红黑树、机器学习5大系列集锦

程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结

转发送书

红黑树

hcsa day4

java注解和反射的个人学习笔记

MySQL 四类管理日志（详解及高阶配置）

（超详细笔记记录）从头开始学Spring 其二

基于FPGA的verilog语言的数码管显示计数程序

Java内存区域--运行时数据区

jquery map方法总结

PPT大神之路高清教程

AcWing 1089. 烽火传递(单调队列优化dp）

2021年 系统分析师 系列课

【爱码农】C#制作MDI文本编辑器

唯恩.rar电气设备选型资料大全 （适合刚刚入行的电气工程师对设备进行选型规划）详解 报价

信息安全风险评估培训教材.ppt

腾讯PCG暑期实习-客户端开发面经

Mycat 实现 MySQL的分库分表、读写分离、主从切换

自制的mnist数据集

工程大面向对象课程设计作品（完整）（也适用于软件工程大实验）.7z

教你如何摆脱负债上岸，超详细(视频课程)

MySQL 数据库权限管理（用户高级管理和精确访问控制）

小爱同学windows10版.Appx

2021年系统分析师系列课

唯恩.rar电气设备选型资料大全（适合刚刚入行的电气工程师对设备进行选型规划）详解报价