- 浏览: 34716 次
- 性别:
- 来自: 重庆
最新评论
二叉树:红黑树
- 博客分类:
- Tree
红黑树是一种自平衡的二叉树,它的查找,插入,删除操作时间复杂度皆为O(logN),不会出现普通二叉搜索树在最差情况时时间复杂度会变为O(N)的问题.
红黑树必须遵循红黑规则,规则如下
1、每个节点不是红就是黑。
2、根总是黑的
3、如果节点是红的,它的子节点必须全部是黑的
4、从根到叶节点或者空子节点的每条路径,必须包含相同数量的黑色节点(黑色高度一致)
红黑树的插入操作比二叉搜索树复杂,为了保证黑红规则,要进行必要的变色和旋转.
插入操作:
查找例程遇到一个有两个红色子节点的黑色节点时,必须要把子节点变成黑色,把父节点变成红色(除非父节点为根节点).这样做是为了连接新的红色节点更容易.但有可违背规则3,当违背规则3时,X为违规节点(子节点违规),P为X的父节点,G为P的父节点则:
如果X是G的外侧子孙节点:
1、改变G的颜色
2、改变P的颜色
3、以G为顶点旋转,向X上升的方向(即X为左外侧子孙就右旋,为右外侧子孙就左旋)
如果X是G的内侧子孙节点:
1、改变G的颜色
2、改变X的颜色
3、以P为顶点旋转,向X上升的方向
4、以G为顶点旋转,向X上升的方向
在找到要插入的位置并插入节点后,会面临2种情况,即:插入节点的父节点是红色的(违背规则3);插入节点的父节点是黑色的(不违规).在父节点是黑色的情况下就不需要再做什么处理.而如果是红色的又分为两种情况:插入节点是外侧子孙节点;插入节点是内侧子孙节点.两者的处理方式与插入例程中的相同,即:
如果P为红色,X是G的外侧子孙节点:
1、改变G的颜色
2、改变P的颜色
3、以G为顶点旋转,向X上升的方向
如果P为红色,X是G的内侧子孙节点:
1、改变G的颜色
2、改变X的颜色
3、以P为顶点旋转,向X上升的方向
4、以G为顶点旋转,向X上升的方向
删除操作:
说实话,本人愚钝,研究插入操作蛋已经碎了一地,好不容易才粘起来,删除操作则更加的复杂,于是还是尽量回避删除操作的好,比如设个作废标记神马的...
查找操作:
跟普通的二叉搜索树一样.
tree代码:
node代码:
红黑树必须遵循红黑规则,规则如下
1、每个节点不是红就是黑。
2、根总是黑的
3、如果节点是红的,它的子节点必须全部是黑的
4、从根到叶节点或者空子节点的每条路径,必须包含相同数量的黑色节点(黑色高度一致)
红黑树的插入操作比二叉搜索树复杂,为了保证黑红规则,要进行必要的变色和旋转.
插入操作:
查找例程遇到一个有两个红色子节点的黑色节点时,必须要把子节点变成黑色,把父节点变成红色(除非父节点为根节点).这样做是为了连接新的红色节点更容易.但有可违背规则3,当违背规则3时,X为违规节点(子节点违规),P为X的父节点,G为P的父节点则:
如果X是G的外侧子孙节点:
1、改变G的颜色
2、改变P的颜色
3、以G为顶点旋转,向X上升的方向(即X为左外侧子孙就右旋,为右外侧子孙就左旋)
如果X是G的内侧子孙节点:
1、改变G的颜色
2、改变X的颜色
3、以P为顶点旋转,向X上升的方向
4、以G为顶点旋转,向X上升的方向
在找到要插入的位置并插入节点后,会面临2种情况,即:插入节点的父节点是红色的(违背规则3);插入节点的父节点是黑色的(不违规).在父节点是黑色的情况下就不需要再做什么处理.而如果是红色的又分为两种情况:插入节点是外侧子孙节点;插入节点是内侧子孙节点.两者的处理方式与插入例程中的相同,即:
如果P为红色,X是G的外侧子孙节点:
1、改变G的颜色
2、改变P的颜色
3、以G为顶点旋转,向X上升的方向
如果P为红色,X是G的内侧子孙节点:
1、改变G的颜色
2、改变X的颜色
3、以P为顶点旋转,向X上升的方向
4、以G为顶点旋转,向X上升的方向
删除操作:
说实话,本人愚钝,研究插入操作蛋已经碎了一地,好不容易才粘起来,删除操作则更加的复杂,于是还是尽量回避删除操作的好,比如设个作废标记神马的...
查找操作:
跟普通的二叉搜索树一样.
tree代码:
public class Tree { private Node root; /** * 插入数据 * @param data */ public void insert(int data){ Node node = new Node(data); if(this.root == null){ this.setRoot(node); return; } Node current = this.root; while(true){ //在变色后如果违反规则3,旋转平衡 if(!this.changeColor(current)){ this.rotate(current); } if(current.getData() > data){ if(current.hasLeft()){ current = current.getLeft(); }else{ current.setLeft(node); break; } }else if(current.getData() < data){ if(current.hasRihgt()){ current = current.getRight(); }else{ current.setRight(node); break; } }else{ current.setValid(true); return; } } //插入后如果违反规则3,旋转平衡 if(node.getParent().isRed()){ this.rotate(node); } } /** * 查找数据 * @param key */ public void find(int key){ Node node = this.findNode(key); if(node != null && node.isValid()){ System.out.println(node); }else{ System.out.println("No find"); } } /** * 删除节点 * @param key */ public void remove(int key){ Node node = this.findNode(key); if(node != null){ node.setValid(false); } } /** * 树是否为空 * @return */ public boolean isEmpty(){ return this.root == null; } /** * 清空树 */ public void clear(){ this.setRoot(null); } /** * 查找节点 * @param i * @return */ private Node findNode(int key){ Node current = this.root; while(current != null){ if(current.getData() > key){ current = current.getLeft(); }else if(current.getData() < key){ current = current.getRight(); }else{ return current; } } return null; } /** * 右旋转 * @param top 顶点 */ private void rotateRight(Node top){ if(top.hasLeft()){ Node parent = top.getParent(); Node left = top.getLeft(); if(left.hasRihgt()){ top.setLeft(left.getRight()); }else{ top.setLeft(null); } if(!top.isRoot()){ if(top.isLeft()){ parent.setLeft(left); }else{ parent.setRight(left); } }else{ this.setRoot(left); } left.setRight(top); } } /** * 左旋转 * @param top 顶点 */ private void rotateLeft(Node top){ if(top.hasRihgt()){ Node parent = top.getParent(); Node right = top.getRight(); if(right.hasLeft()){ top.setRight(right.getLeft()); }else{ top.setRight(null); } if(!top.isRoot()){ if(top.isLeft()){ parent.setLeft(right); }else{ parent.setRight(right); } }else{ this.setRoot(right); } right.setLeft(top); } } /** * 如果一个节点的为黑色,并且它的两个子节点均为红色,将父节点变味红色,子节点变为黑色 * @param node 父节点 * @return 是否违反规则3,false为违反 */ private boolean changeColor(Node node){ if(node.isBlack() && node.hasLeft() && node.hasRihgt() && node.getLeft().isRed() && node.getRight().isRed()){ node.getLeft().changeColor(); node.getRight().changeColor(); if(!node.isRoot()){ node.changeColor(); if(node.getParent().isRed()){ return false; } } } return true; } /** * 在违反规则3时做旋转操作平衡 * @param node 违规节点 */ private void rotate(Node node){ Node p = node.getParent(); Node g = p.getParent(); //当节点是外侧子孙节点的时候 if(this.isRR(node) || this.isLL(node)){ p.changeColor(); g.changeColor(); if(node.isRight()){ this.rotateLeft(g); }else{ this.rotateRight(g); } //当节点是内侧子孙节点的时候 }else{ g.changeColor(); node.changeColor(); if(node.isRight()){ this.rotateLeft(p); this.rotateRight(g); }else{ this.rotateRight(p); this.rotateLeft(g); } } } /** * 判断节点是否是父节点的右节点,并且父节点是否是祖父节点的右节点 * @return */ private boolean isRR(Node node){ return node.isRight() && node.getParent().isRight(); } /** * 判断节点是否是父节点的左节点,并且父节点是否是祖父节点的左节点 * @return */ private boolean isLL(Node node){ return node.isLeft() && node.getParent().isLeft(); } /** * 设置根节点 * @param node */ private void setRoot(Node node){ this.root = node; if(this.isEmpty()){ return; } this.root.setParent(null); if(this.root.isRed()){ this.root.changeColor(); } } }
node代码:
public class Node { private boolean color;//true是红,false是黑 private Node parent; private Node left; private Node right; private int data; private boolean valid; public Node(int data) { this.data = data; this.color = true; this.valid = true; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; if (left != null) { left.setParent(this); } } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; if (right != null) { right.setParent(this); } } public void setValid(boolean flag){ this.valid = flag; } public boolean isValid(){ return this.valid; } public boolean hasLeft() { return this.left != null; } public boolean hasRihgt() { return this.right != null; } public boolean isRed() { return this.color; } public boolean isBlack() { return !this.color; } public boolean isRoot() { return this.parent == null; } public boolean isLeft(){ if(this.isRoot()){ return false; } return this.parent.getLeft() == this; } public boolean isRight(){ if(this.isRoot()){ return false; } return this.parent.getRight() == this; } public void changeColor() { this.color = !this.color; } }
相关推荐
平衡二叉树-红黑树的实现
数据结构 树、二叉树、红黑树、堆、图等结构教程
数据结构 和算法分析 二叉树、红黑树、堆、图等数据结构
四、红黑树 本质:自平衡二叉树 在二叉查找树基础上,添加以下性质 节点是红色或黑色 根节点是黑色 每个为空的叶子节点是黑色的 每个红色节点的两个子节点都是黑色 从任一节点到其每个叶子节点的所有路径都包含...
c++容器list、vector、map、set区别 list 封装链表,以链表形式实现,不支持[]运算符。... 采用平衡检索二叉树:红黑树 存储结构为键值对 set 采用平衡检索二叉树:红黑树 set中不包含重复的数据 Hash
2,为什么索引结构默认使用B+Tree,而不是Hash,二叉树,红黑树? 3、MySQL里记录货币用什么字段类型好 4、数据库自增主键可能遇到什么问题。 5、从锁的类别角度讲,MySQL都有哪些锁呢? 6、索引失效情况? 7、优化...
高级数据结构代码 红黑树 二叉树 B树
talerbtree红黑树二叉树.zip
1. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别 二叉搜索树:也称二叉查找树,或二叉排序树。定义也比较简单,要么是一颗空 树,要么就是具有如下性质的二叉树:...
描述了红黑树的基本结构 以及与二叉树的性能比较
红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:...
红黑树&二叉树
主要实现有普通树的生成、查询方法,与继承于普通树的二叉树、红黑树的实现。
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27,...
红黑树的本质是二叉树,二叉树在插入元素的时候是根据关键字(可以理解为用来识别每个节点的id,一般是hash 来判断)的大小来判断插入到哪一个分支的,如下图所示: (备注:大写字母代表每个节点相当于每个节点的...
第一,散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序 第二,散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,
它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的...
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
这是一个关于二叉树的代码,演示了红黑树的数据结构。仅供大家学习和参考!
COMP2211Project1 二叉树和红黑树的 Java 代码