首页 > 代码库 > 【C++】 红黑树实现
【C++】 红黑树实现
【本文原创于Paul的博客园技术博客。】
【本文欢迎转载,转载请以链接形式注明出处。】
【本博客所有文章都经博主精心整理,请尊重我的劳动成果。】
【C++】红黑树实现
红黑树的定义:
一棵二叉查找树如果满足下面的红黑性质,则为一棵红黑树。
1)每个节点或是红的,或是黑的。
2)根节点是黑的。
3)每个叶节点(NIL)是黑节点。
4)如果一个节点是红的,则它的两个儿子都是黑的。
5)对每个节点,从该节点到其子孙节点的所有路径上包含相同节点数目的黑节点。
关于更多红黑树的知识请参见百度百科:红黑树
C++:BRTreeNode.h
1 #ifndef BRTREENODE_H_INCLUDED 2 #define BRTREENODE_H_INCLUDED 3 #include<iostream> 4 using namespace std; 5 class BRTree; 6 class BRTreeNode 7 { 8 private: 9 friend class BRTree; 10 int key; 11 bool color; 12 BRTreeNode* left; 13 BRTreeNode* right; 14 BRTreeNode* parent; 15 public: 16 BRTreeNode():key(-1),color(0),left(NULL),right(NULL),parent(NULL){} 17 BRTreeNode(BRTreeNode* node):key(node->key),color(node->color),left(node->left),right(node->right),parent(node->parent) 18 {} 19 BRTreeNode(int num,bool flag):key(num),color(flag),left(NULL),right(NULL),parent(NULL){} 20 ~BRTreeNode() 21 { 22 23 } 24 int Getkey() 25 { 26 return key; 27 } 28 bool Getcolor() 29 { 30 return this->color; 31 } 32 BRTreeNode* GetLeft() 33 { 34 return this->left; 35 } 36 BRTreeNode* Getright() 37 { 38 return this->right; 39 } 40 BRTreeNode* Getparent() 41 { 42 return this->parent; 43 } 44 void Inorder() 45 { 46 if(this!=NULL) 47 { 48 this->left->Inorder(); 49 cout<<this->key<<" "; 50 this->right->Inorder(); 51 } 52 } 53 void Preorder() 54 { 55 if(this!=NULL) 56 { 57 cout<<this->key<<" "; 58 this->left->Preorder(); 59 this->right->Preorder(); 60 } 61 } 62 void Postorder() 63 { 64 if(this!=NULL) 65 { 66 this->left->Postorder(); 67 this->right->Postorder(); 68 cout<<this->key<<" "; 69 } 70 } 71 72 void MakeEmpty() 73 { 74 if(this!=NULL) 75 { 76 this->left->MakeEmpty(); 77 this->right->MakeEmpty(); 78 delete this; 79 } 80 } 81 int GetHeight() 82 { 83 int L,R; 84 if(this==NULL) 85 { 86 return 0; 87 } 88 L=this->left->GetHeight(); 89 R=this->right->GetHeight(); 90 return 1+(L>R? L:R); 91 } 92 }; 93 94 95 #endif // BRTREENODE_H_INCLUDED
BRTree.h
1 #ifndef BRTREE_H_INCLUDED 2 #define BRTREE_H_INCLUDED 3 #define maxSize 30 4 #define maxWidth 30 5 #include"BRTreeNode.h" 6 class BRTree 7 { 8 private: 9 BRTreeNode* root; 10 BRTreeNode* nil; 11 public: 12 BRTree():nil(new BRTreeNode()) 13 { 14 nil->color=0; 15 nil->key=-1; 16 nil->left=nil->right=nil->parent=NULL; 17 root=nil; 18 } 19 ~BRTree() 20 { 21 MakeEmpty(root); 22 delete nil; 23 } 24 //清空以node为根节点的树 25 void MakeEmpty(BRTreeNode*node) 26 { 27 if(node!=nil) 28 { 29 MakeEmpty(node->left); 30 MakeEmpty(node->right); 31 delete node; 32 } 33 } 34 int Getkey(BRTreeNode* node) 35 { 36 return node->Getkey(); 37 } 38 bool Getcolor(BRTreeNode* node) 39 { 40 return node->Getcolor(); 41 } 42 BRTreeNode* Getroot() 43 { 44 return root; 45 } 46 BRTreeNode* GetParent(BRTreeNode*node) 47 { 48 return node->parent; 49 } 50 int GetHeight(BRTreeNode* node) 51 { 52 int L,R; 53 if(node==nil) 54 return 0; 55 L=GetHeight(node->left); 56 R=GetHeight(node->right); 57 return 1+(L>R? L:R); 58 } 59 int GetBlackHeight(BRTreeNode* node) 60 { 61 int L,R; 62 if(node==nil) return 0; 63 L=GetHeight(node->left); 64 R=GetHeight(node->right); 65 if(node->Getcolor()) return(L>R? L:R); 66 else return 1+(L>R? L:R); 67 } 68 void Inorder(BRTreeNode*node) 69 { 70 if(node!=nil) 71 { 72 Inorder(node->left); 73 cout<<node->key<<" "; 74 Inorder(node->right); 75 } 76 } 77 void Preorder(BRTreeNode*node) 78 { 79 if(node!=nil) 80 { 81 cout<<node->key<<" "; 82 Preorder(node->left); 83 Preorder(node->right); 84 } 85 } 86 void Posetorder(BRTreeNode*node) 87 { 88 if(node!=nil) 89 { 90 Posetorder(node->left); 91 Posetorder(node->right); 92 cout<<node->key<<" "; 93 } 94 } 95 //层次法打印树 96 void DispTree(BRTreeNode*BT) 97 { 98 BRTreeNode stack[maxSize],p; 99 int level[maxSize][2],top,n,i,width=4; 100 if(BT!=NULL) 101 { 102 cout<<"Display a tree by hollow means."<<endl; 103 top=1; 104 stack[top]=BT;//push root point to stack. 105 level[top][0]=width; 106 while(top>0) 107 { 108 p=stack[top]; 109 n=level[top][0]; 110 for(i=1;i<=n;i++) 111 cout<<" "; 112 //输出信息 113 if(p.key==0) 114 { 115 cout<<")"; 116 } 117 else{ 118 if(p.key==-1) cout<<"Nil"; 119 else if(p.left&&p.right) cout<<"("<<p.key; 120 else cout<<p.key; 121 if(p.Getcolor()) cout<<"R,"; 122 else cout<<"B,"; 123 } 124 for(i=n+1;i<maxWidth;i+=2) 125 cout<<"--"; 126 cout<<endl; 127 top--; 128 if(p.right!=NULL) 129 { 130 //插入一个括号节点,key值为0 131 top++; 132 BRTreeNode* tmp=new BRTreeNode(); 133 tmp->key=0; 134 stack[top]=tmp; 135 level[top][0]=n+width; 136 level[top][1]=2; 137 top++; 138 stack[top]=p.right; 139 level[top][0]=n+width; 140 level[top][1]=2; 141 142 } 143 if(p.left!=NULL) 144 { 145 top++; 146 stack[top]=p.left; 147 level[top][0]=n+width; 148 level[top][1]=1; 149 } 150 } 151 } 152 } 153 //左旋节点node 154 bool LeftRotate(BRTreeNode* node) 155 { 156 BRTreeNode*y; 157 if(node->right==nil) 158 { 159 cout<<"can‘t left rotate!"<<endl; 160 return 0; 161 } 162 y=node->right; 163 node->right=y->left; 164 if(y->left!=nil) 165 { 166 y->left->parent=node; 167 } 168 y->parent=node->parent; 169 if(node->parent==nil) 170 { 171 root=y; 172 } 173 else if(node->parent->left==node) 174 { 175 node->parent->left=y; 176 } 177 else 178 { 179 node->parent->right=y; 180 } 181 y->left=node; 182 node->parent=y; 183 return 1; 184 } 185 //右旋节点 186 bool RightRotate(BRTreeNode* node) 187 { 188 if(node->left==nil) 189 { 190 cout<<"can‘t rightrotate!"<<endl; 191 return 0; 192 } 193 BRTreeNode* x; 194 x=node->left; 195 node->left=x->right; 196 if(x->right!=nil) 197 { 198 x->right->parent=node; 199 } 200 x->parent=node->parent; 201 if(node->parent==nil) 202 { 203 root=x; 204 } 205 else if(node->parent->left==node) 206 { 207 node->parent->left=x; 208 } 209 else 210 { 211 node->parent->right=x; 212 } 213 node->parent=x; 214 x->right=node; 215 return 1; 216 } 217 void Insert(int num) 218 { 219 BRTreeNode* node=new BRTreeNode(num,1); 220 node->left=nil; 221 node->right=nil; 222 node->parent=nil; 223 BRTreeNode* p=root,*q=nil; 224 if(root==nil) 225 { 226 node->color=0; 227 root=node; 228 root->left=root->right=root->parent=nil; 229 return ; 230 } 231 while(p!=nil) 232 { 233 if(p->key==num) 234 { 235 cout<<num<<" has exist!"<<endl; 236 return ; 237 } 238 else if(p->key>num) 239 { 240 q=p; 241 p=p->left; 242 } 243 else 244 { 245 q=p; 246 p=p->right; 247 } 248 } 249 if(q->key>num) 250 { 251 q->left=node; 252 node->parent=q; 253 } 254 else 255 { 256 q->right=node; 257 node->parent=q; 258 } 259 RBInsertAdjust(node); 260 } 261 void RBInsertAdjust(BRTreeNode* node) 262 { 263 BRTreeNode* y; 264 while(node->parent->color==1) 265 { 266 if(node->parent==node->parent->parent->left) 267 { 268 y=node->parent->parent->right; 269 if(y->color==1) 270 { 271 node->parent->color=0; 272 y->color=0; 273 y->parent->color=1; 274 node=node->parent->parent; 275 } 276 //此时y的颜色是黑色 277 else 278 { 279 //第二种情况 280 if(node==node->parent->right) 281 { 282 node=node->parent; 283 LeftRotate(node); 284 } 285 //第三种情况 286 node->parent->color=0; 287 node->parent->parent->color=1; 288 RightRotate(node->parent->parent); 289 } 290 } 291 else 292 { 293 y=node->parent->parent->left; 294 if(y->color==1) 295 { 296 node->parent->color=0; 297 y->color=0; 298 y->parent->color=1; 299 node=node->parent->parent; 300 } 301 else 302 { 303 if(node==node->parent->left) 304 { 305 node=node->parent; 306 RightRotate(node); 307 } 308 node->parent->color=0; 309 node->parent->parent->color=1; 310 LeftRotate(node->parent->parent); 311 } 312 } 313 } 314 root->color=0; 315 } 316 BRTreeNode* Search(int num) 317 { 318 BRTreeNode* p=root; 319 while(p!=nil) 320 { 321 if(p->key==num) 322 { 323 return p; 324 } 325 else if(p->key>num) 326 { 327 p=p->left; 328 } 329 else 330 { 331 p=p->right; 332 } 333 } 334 cout<<"there is no "<<num<<" in this tree!"<<endl; 335 return nil; 336 } 337 //获取以node节点为根节点的树的最小元素,并返回该最小值 338 int Minnum(BRTreeNode*node) 339 { 340 BRTreeNode*p=node; 341 while(p->left!=nil) 342 { 343 p=p->left; 344 } 345 return p->key; 346 } 347 //获取以node节点为根节点的树的最da元素,并返回该最da值 348 int Maxnum(BRTreeNode*node) 349 { 350 BRTreeNode*p=node; 351 while(p->right!=nil) 352 { 353 p=p->right; 354 } 355 return p->key; 356 } 357 //获取以node节点为根节点的树的最小元素,并返回该节点 358 BRTreeNode* MinNum(BRTreeNode*node) 359 { 360 BRTreeNode*p=node; 361 while(p->left!=nil) 362 { 363 p=p->left; 364 } 365 return p; 366 } 367 //获取以node节点为根节点的树的最大元素 368 BRTreeNode* MaxNum(BRTreeNode*node) 369 { 370 BRTreeNode*p=node; 371 while(p->right!=nil) 372 { 373 p=p->right; 374 } 375 return p; 376 } 377 BRTreeNode*InorderSuccessor(BRTreeNode*node) 378 { 379 if(node->right!=nil) 380 { 381 return MinNum(node->right); 382 } 383 else 384 { 385 BRTreeNode*p=GetParent(node); 386 while(p&&node==p->right) 387 { 388 node=p; 389 p=GetParent(node); 390 } 391 return p; 392 } 393 } 394 //中序遍历的前趋 395 BRTreeNode*InordePredecessor(BRTreeNode*node) 396 { 397 if(node->left!=nil) 398 { 399 return MaxNum(node->left); 400 } 401 else 402 { 403 BRTreeNode*p=GetParent(node); 404 while(p&&node==p->left) 405 { 406 node=p; 407 p=GetParent(node); 408 } 409 return p; 410 } 411 } 412 bool Delete(int num) 413 { 414 BRTreeNode*z,*y,*x; 415 //寻找key值为num的节点p 416 z=Search(num); 417 //如果没有该节点则返回0 418 if(z==nil) 419 { 420 return 0; 421 } 422 if(z->left==nil||z->right==nil) 423 { 424 y=z; 425 } 426 else 427 y=InorderSuccessor(z); 428 if(y->left!=nil) 429 x=y->left; 430 else 431 x=y->right; 432 x->parent=y->parent; 433 if(x->parent==nil) 434 root=x; 435 else if(y=y->parent->left) 436 y->parent->left=x; 437 else 438 y->parent->right=x; 439 if(y!=z) 440 { 441 z->key=y->key; 442 } 443 if(y->color==0) 444 { 445 RBTreeFixup(x); 446 } 447 return 1; 448 } 449 void RBTreeFixup(BRTreeNode* x) 450 { 451 BRTreeNode*w; 452 while(x!=root&&x->color==0) 453 { 454 if(x==x->parent->left) 455 { 456 w=x->parent->right; 457 if(w->color==1) 458 { 459 w->color=0; 460 x->parent->color=1; 461 LeftRotate(x->parent); 462 w=x->parent->right; 463 } 464 if(w->left->color==0&&w->right->color==0) 465 { 466 w->color=1; 467 x=x->parent; 468 } 469 else 470 { 471 if(w->right->color==0) 472 { 473 w->color=1; 474 RightRotate(w); 475 w=x->parent->right; 476 } 477 w->color=x->parent->color; 478 x->parent->color=0; 479 w->right->color=0; 480 LeftRotate(x->parent); 481 x=root; 482 } 483 } 484 else 485 { 486 w=x->parent->left; 487 if(w->color==1) 488 { 489 w->color=0; 490 x->parent->color=1; 491 RightRotate(x->parent); 492 w=x->parent->left; 493 } 494 if(w->right->color==0&&w->left->color==0) 495 { 496 w->color=1; 497 x=x->parent; 498 } 499 else 500 { 501 if(w->left->color==0) 502 { 503 w->color=1; 504 LeftRotate(w); 505 w=x->parent->left; 506 } 507 w->color=x->parent->color; 508 x->parent->color=0; 509 w->left->color=0; 510 RightRotate(x->parent); 511 x=root; 512 } 513 } 514 } 515 x->color=0; 516 } 517 }; 518 519 #endif // BRTREE_H_INCLUDED
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。