个人中心
gpt4 book ai didi

基于红黑树插入操作原理及java实现方法(分享)

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 28 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章基于红黑树插入操作原理及java实现方法(分享)由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

红黑树是一种二叉平衡查找树，每个结点上有一个存储位来表示结点的颜色，可以是red或black.

红黑树具有以下性质:

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

(2) 根结点是黑色的 。

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

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

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

java的treemap就是通过红黑树实现的.

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

插入一个红色的节点到红黑树中之后，会有6种情况：图示中n表示插入的节点，p表示父节点，u表示叔叔节点，g表示祖父节点，x表示当前操作节点 。

基于红黑树插入操作原理及java实现方法(分享)

  。

基于红黑树插入操作原理及java实现方法(分享)

基于红黑树插入操作原理及java实现方法(分享)

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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实现方法(分享)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我.

原文链接：http://www.cnblogs.com/evasean/p/7998933.html 。

最后此篇关于基于红黑树插入操作原理及java实现方法(分享)的文章就讲到这里了,如果你想了解更多关于基于红黑树插入操作原理及java实现方法(分享)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

28 4 0
文章推荐： JAVA通过HttpClient发送HTTP请求的方法示例
文章推荐： JDBC连接mysql乱码异常问题处理总结
文章推荐： Java日期处理工具类DateUtils详解
文章推荐： IntelliJ IDEA创建maven多模块项目(图文教程)
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com