文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

基于红黑树插入操作原理及java实现的示例分析

2023-05-30 18:32

关注

这篇文章主要介绍基于红黑树插入操作原理及java实现的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

红黑树是一种二叉平衡查找树,每个结点上有一个存储位来表示结点的颜色,可以是RED或BLACK。

红黑树具有以下性质:

(1) 每个结点是红色或是黑色

(2) 根结点是黑色的

(3) 如果一个结点是红色的,则它的两个儿子都是黑色的

(4) 对于每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点

通过红黑树的性质,可以保证所有基于红黑树的实现都能保证操作的运行时间为对数级别(范围查找除外。它所需的额外时间和返回的键的数量成正比)。

Java的TreeMap就是通过红黑树实现的。

红黑树的操作如果不画图很容易搞糊涂,下面通过图示来说明红黑树的插入操作。

插入一个红色的节点到红黑树中之后,会有6种情况:图示中N表示插入的节点,P表示父节点,U表示叔叔节点,G表示祖父节点,X表示当前操作节点

基于红黑树插入操作原理及java实现的示例分析

 基于红黑树插入操作原理及java实现的示例分析

基于红黑树插入操作原理及java实现的示例分析

基于红黑树插入操作原理及java实现的示例分析

代码如下:

public class RedBlackBST<Key extends Comparable<Key>, Value> { private Node root; private static final boolean RED = true; private static final boolean BLACK = false; private class Node{  private Key key; //键  private Value val; //值  private Node left, right, parent; //左右子树和父节点  private boolean color; //由其父节点指向它的链接的颜色    public Node(Key key, Value val,Node parent, boolean color){   this.key = key;   this.val = val;   this.color = color;  } }  public Value get(Key key){  Node x = root;  while(x!=null){   int cmp = key.compareTo(x.key);   if(cmp < 0 ) x = x.left;   else if(cmp > 0) x = x.right;   else return x.val;  }  return null; }  public void put(Key key, Value val){  if(root==null) { //如果是根节点,就将节点新建为黑色   root = new Node(key,val,null,BLACK);   return;  }  //寻找合适的插入位置  Node parent = null;  Node cur = root;  while(cur!=null) {   parent = cur;   if(key.compareTo(cur.key)>0) cur=cur.right;   else cur = cur.left;  }  Node n = new Node(key,val,parent,RED); //普通的新建节点为红色  //将新节点插入parent下  if(key.compareTo(parent.key) > 0) parent.right = n;  else parent.left = n;  //插入新节点后要调整树中部分节点的颜色和属性来保证红黑树的特征不被破坏  fixAfterInsertion(n);  } private Node parentOf(Node x) {  return (x==null ? null : x.parent); } private boolean colorOf(Node x) {  return (x==null ? BLACK : x.color); } private Node leftOf(Node x) {  return (x==null ? null : x.left); } private Node rightOf(Node x) {  return(x==null ? null : x.right); } private void setColor(Node x, boolean color) {  if(x!=null)   x.color = color; }  private void fixAfterInsertion(Node x) {  while(x!=null && colorOf(parentOf(x)) == RED) {   Node grandPa = parentOf(parentOf(x));   Node parent = parentOf(x);   if(parent == leftOf(grandPa)) {//case 1 || case2 || case3    Node uncle = rightOf(grandPa);    if(colorOf(uncle) == RED) {//case1, uncle is red     setColor(parent,BLACK); //父节点置黑     setColor(uncle, BLACK); //叔叔节点置黑     setColor(grandPa,RED); //祖父节点置红     x = grandPa; //因为祖父节点由黑转红,故要重新调整父节点及其祖先的红黑属性    }else {//case2 || case3,uncle is black     if(x==rightOf(parent)) { //case2      x = parent;      rotateLeft(x);     }     //case3     setColor(parent,BLACK);     setColor(grandPa, RED);     rotateRight(grandPa);    }       }else {//case4 || case 5 || case6    Node uncle = leftOf(grandPa);    if(colorOf(uncle) == RED) { //case4 || case5 || case6     setColor(parent,BLACK);     setColor(uncle, BLACK);     setColor(grandPa,RED);     x = grandPa;    }else{ //case5 || case6, uncle is black     if(x==leftOf(parent)) { //case5      x = parent;      rotateRight(x);     }     //case6     setColor(parent,BLACK);     setColor(grandPa, RED);     rotateLeft(grandPa);    }   }  } } private void rotateLeft(Node x) {  if(x==null) return;  Node y = x.right;  x.right = y.left;  if(y.left!=null)   y.left.parent = x;  y.left = x;  y.parent = x.parent;  if(x.parent == null) {   root = y;  }  else if(x.parent.left == x) {   x.parent.left = y;  }else {   x.parent.right = y;  }  x.parent = y; } private void rotateRight(Node x) {  if(x==null) return;  Node y = x.left;  x.left = y.right;  if(y.right != null)   y.right.parent = x;  y.right = x;  y.parent = x.parent;  if(x.parent == null) {   root = y;  }else if(x.parent.left==x) {   x.parent.left = y;  }else {   x.parent.right=y;  }  x.parent = y; } }

上面的rotateLeft和rotateRight有必要画个图示:

基于红黑树插入操作原理及java实现的示例分析

以上是“基于红黑树插入操作原理及java实现的示例分析”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯