
- 外文名
- RED-BLACK-TREE
- 发明人
- 鲁道夫·贝尔
- 发明时间
- 1972年
- 别 名
- 对称二叉B树
- 用 途
- 实现关联数组 [1]
- 中文名
- 红黑树
- 性 质
- 平衡二叉查找树 [3]
- 学 科
- 计算机
-
红黑树
2019-11-16 14:39:10红黑树- 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。
- 一、A*搜索算法
- 一(续)、A*,Dijkstra,BFS算法性能比较及A*算法的应用
- 二、Dijkstra 算法初探 (Dijkstra算法系列4篇文章)
- 二(续)、彻底理解Dijkstra算法
- 二(再续)、Dijkstra 算法+fibonacci堆的逐步c实现
- 二(三续)、Dijkstra 算法+Heap堆的完整c实现源码
- 三、dynamic programming
- 四、BFS和DFS优先搜索算法
- 五、教你透彻了解红黑树 (红黑树系列6篇文章之其中两篇)
- 五(续)、红黑树算法的实现与剖析
- 六、教你初步了解KMP算法
- 六(续)、从KMP算法一步一步谈到BM算法
- 六(三续)、从头到尾彻底理解KMP (KMP的PDF)
- 七、遗传算法 透析GA本质
- 八、再谈启发式搜索算法
- 九、图像特征提取与匹配之SIFT算法 (sift算法系列五篇文章)
- 九(续)、sift算法的编译与实现
- 九(再续)、教你一步一步用c语言实现sift算法、上
- 九(再续)、教你一步一步用c语言实现sift算法、下
- 九(三续):SIFT算法的应用--目标识别之Bag-of-words模型
- 九(四续)、SIFT + KD_BBF算法 (此文第3部分)
- 十、从头到尾彻底理解傅里叶变换算法、上
- 十、从头到尾彻底理解傅里叶变换算法、下
- 十一、从头到尾彻底解析Hash表算法
- 十一(续)、倒排索引关键词Hash不重复编码实践
- 十二、快速排序算法 (快速排序算法3篇文章)
- 十二(续)、快速排序算法的深入分析
- 十二(再续):快速排序算法之所有版本的c/c++实现
- 十三、通过浙大上机复试试题学SPFA 算法
- 十四、快速选择SELECT算法的深入分析与实现
- 十五、多项式乘法与快速傅里叶变换
最新的十五个经典算法研究的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 」。
- 第一章、左旋转字符串
- 第二章、字符串是否包含问题
- 第三章、寻找最小的k个数
- 第三章续、Top K算法问题的实现
- 第三章再续:快速选择SELECT算法的深入分析与实现
- 三之三续、求数组中给定下标区间内的第K小(大)元素
- 第四章、现场编写类似strstr/strcpy/strpbrk的函数
- 第五章、寻找满足条件的两个或多个数
- 第六章、求解500万以内的亲和数
- 第七章、求连续子数组的最大和
- 第八章、从头至尾漫谈虚函数
- 第九章、闲话链表追赶问题
- 第十章、如何给10^7个数据量的磁盘文件排序
- 第十一章、最长公共子序列(LCS)问题
- 第十二~十五章:数的判断,中签概率,IP访问次数,回文问题(初稿)
- 第二十六章:基于给定的文档生成倒排索引的编码与实践
- 第二十七章:不改变正负数之间相对顺序重新排列数组
- 第二十八~二十九章:最大连续乘积子串、字符串编辑距离
- 第三十~三十一章:字符串转换成整数,字符串匹配问题
- 第三十二~三十三章:最小操作数,木块砌墙问题
- 第三十四~三十五章:格子取数问题,完美洗牌算法
- 第三十六~三十七章、搜索智能提示suggestion,附近地点搜索
- 第三十八章:Hero在线编程判题、出题系统的演进与优化
- 第三十九~四十章:最近公共祖先LCA问题、打印螺旋矩阵
- 第四十一章~四十二章:荷兰国旗、矩阵相乘Strassen算法
- ...
程序员编程艺术第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树
- 教你初步了解红黑树 (红黑树系列)
- 红黑树算法的实现与剖析
- 红黑树的C实现完整源码
- 一步一图一代码,R-B Tree
- 红黑树插入和删除结点的全程演示
- 红黑树的C++完整实现源码
- 从2-3-4树谈到Red-Black Tree(红黑树)
- 从B树、B+树、B*树谈到R 树 (B树的PDF)
- B树的C 实现
- 从Trie树(字典树)谈到后缀树 (其余树结构)
- 从LSM-Tree、COLA-Tree谈到StackOverflow、OSQA
-
5.1 AI数学基础
- 数据挖掘中所需的概率论与数理统计知识、上
- 一文通透优化算法:从随机梯度、随机梯度下降法到牛顿法、共轭梯度
- 5.2 AI经典模型
- 数据挖掘领域十大经典算法初探
- 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法
- 从决策树学习谈到贝叶斯分类算法、EM、HMM
- 支持向量机通俗导论(理解SVM的三层境界) PDF下载 LaTeX版本1 LaTeX版本2
- 最大熵模型中的数学推导
- 如何通俗理解EM算法
- Adaboost 的原理与推导 LaTeX版本下载
- 从拉普拉斯矩阵说到谱聚类
- 从贝叶斯方法谈到贝叶斯网络 LaTeX版本下载
- 通俗理解LDA主题模型 LaTeX版本下载
- CNN笔记:通俗理解卷积神经网络
- 图解CNN:通过100张图一步步理解CNN
- 一文读懂目标检测:R-CNN、Fast R-CNN、Faster R-CNN、YOLO、SSD
- 通俗理解kaggle比赛大杀器xgboost
- 如何从RNN起步,一步一步通俗理解LSTM
- 如何通俗理解word2vec
- ..
- 5.3 AI工程实践
- 一文读懂特征工程
- 教你从头到尾利用DL学梵高作画:GTX 1070 cuda 8.0 tensorflow gpu版
- 没GPU也能玩梵高作画:Ubuntu tensorflow CPU版
- 基于torch学汪峰写歌词、聊天机器人、图像着色/生成、看图说话、字幕生成
- 教你从头到尾利用DQN自动玩flappy bird(全程命令提示,GPU+CPU版)
- 手把手教你搭建caffe及手写数字识别(Ubuntu下且附mac、纯通俗教程)
- 如何从零起步学习AI(附学习路线)
- GAN之父在NIPS 2016上做的报告:两个竞争网络的对抗(含译文下载)
- Kaggle—So Easy!百行代码实现排名Top 5%的图像分类比赛
- BAT机器学习面试1000题系列(第1~500题)
六、其它重要文章节选
-
6.1、经典数据结构 & 算法系列:
- 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。目前,京东、当当、亚马逊等各大网店均已有现货销售。
-
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