AVLtree（C++实现）有统一的旋转操作
在学习完AVLtree之后，我发现，左旋，右旋均可以采用统一的旋转方式来实现，所以把代码贴在下面
代码是完整的AVLTree实现
C++标准为C++11
在ubuntu 18.04下通过编译和调试
1 /* 2 * BinarySearchTree.h 3 * 1. 添加元素时需自己做判断元素是否合法 4 * 2. 除层序遍历外，本源代码均采用递归遍历，若要减少栈的消耗，应该实现递归遍历 5 * 3. 本代码实现的AVL树有统一旋转操作，不用分情况讨论LL,LR,RR,RL来进行树的平衡 6 * 统一旋转操作有特殊优化版本和统一接口版本，本代码保留了统一接口的源码，但是采用的是特殊优化版本 7 * Created on: 2020年1月29日 8 * Author: LuYonglei 9 */ 10 11 #ifndef SRC_BINARYSEARCHTREE_H_ 12 #define SRC_BINARYSEARCHTREE_H_ 13 #include <queue> 14 15 template<typename Element> 16 class BinarySearchTree { 17 public: 18 19 BinarySearchTree(int (*cmp)(Element e1, Element e2)); //比较函数指针 20 21 virtual ~BinarySearchTree(); 22 23 int size(); //元素的数量 24 25 bool isEmpty(); //是否为空 26 27 void clear() { 28 //清空所有元素 29 NODE *node = root_; 30 root_ = nullptr; 31 using namespace std; 32 queue<NODE*> q; 33 q.push(node); 34 while (!q.empty()) { 35 NODE *tmp = q.front(); 36 if (tmp->left != nullptr) 37 q.push(tmp->left); 38 if (tmp->right != nullptr) 39 q.push(tmp->right); 40 delete tmp; 41 q.pop(); 42 } 43 } 44 45 void add(Element e) { 46 //添加元素 47 add(e, cmp_); 48 } 49 50 void remove(Element e) { 51 //删除元素 52 remove(Node(e, cmp_)); 53 } 54 55 bool contains(Element e) { 56 //是否包含某元素 57 return Node(e, cmp_) != nullptr; 58 } 59 60 void preorderTraversal(bool (*visitor)(Element &e)) { 61 //前序遍历 62 if (visitor == nullptr) 63 return; 64 bool stop = false; //停止标志，若stop为true，则停止遍历 65 preorderTraversal(root_, stop, visitor); 66 } 67 68 void inorderTraversal(bool (*visitor)(Element &e)) { 69 //中序遍历 70 if (visitor == nullptr) 71 return; 72 bool stop = false; //停止标志，若stop为true，则停止遍历 73 inorderTraversal(root_, stop, visitor); 74 } 75 76 void postorderTraversal(bool (*visitor)(Element &e)) { 77 //后序遍历 78 if (visitor == nullptr) 79 return; 80 bool stop = false; //停止标志，若stop为true，则停止遍历 81 postorderTraversal(root_, stop, visitor); 82 } 83 84 void levelOrderTraversal(bool (*visitor)(Element &e)) { 85 //层序遍历，迭代实现 86 if (visitor == nullptr) 87 return; 88 levelOrderTraversal(root_, visitor); 89 } 90 91 int height() { 92 //树的高度 93 return height(root_); 94 } 95 96 bool isComplete() { 97 //判断是否是完全二叉树 98 return isComplete(root_); 99 } 100 101 private: 102 103 int size_; 104 105 typedef struct _Node { 106 Element e; 107 _Node *parent; 108 _Node *left; 109 _Node *right; 110 int height; //节点的高度 111 _Node(Element e_, _Node *parent_) : 112 e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) { 113 //节点构造函数 114 } 115 116 inline bool isLeaf() { 117 return (left == nullptr && right == nullptr); 118 } 119 120 inline bool hasTwoChildren() { 121 return (left != nullptr && right != nullptr); 122 } 123 124 inline int balanceFactor() { 125 //获得节点的平衡因子 126 int leftHeight = left == nullptr ? 0 : left->height; //获得左子树的高度 127 int rightHeight = right == nullptr ? 0 : right->height; //获得右子树的高度 128 return leftHeight - rightHeight; 129 } 130 131 inline bool isBalanced() { 132 //判断node是否平衡 133 int balanceFactor_ = balanceFactor(); 134 return balanceFactor_ >= -1 && balanceFactor_ <= 1; //平衡因子为-1,0,1则返回true 135 } 136 137 inline void updateHeight() { 138 //更新节点的高度 139 int leftHeight = left == nullptr ? 0 : left->height; //获得左子树的高度 140 int rightHeight = right == nullptr ? 0 : right->height; //获得右子树的高度 141 height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); //把节点高度更新为左右子树最大的高度+1 142 } 143 144 inline bool isLeftChild() { 145 //判断节点是否是父亲节点的左子结点 146 return parent != nullptr && parent->left == this; 147 } 148 149 inline bool isRightChild() { 150 //判断节点是否是父亲节点的右子结点 151 return parent != nullptr && parent->right == this; 152 } 153 154 inline _Node* tallerChild() { 155 //获得高度更高的子树 156 int leftHeight = left == nullptr ? 0 : left->height; //获得左子树的高度 157 int rightHeight = right == nullptr ? 0 : right->height; //获得右子树的高度 158 if (leftHeight > rightHeight) 159 return left; 160 if (leftHeight < rightHeight) 161 return right; 162 return isLeftChild() ? left : right; 163 } 164 165 } NODE; 166 167 NODE *root_; 168 169 int (*cmp_)(Element e1, Element e2); //为实现树的排序的个性化配置，私有成员保存一个比较函数指针 170 171 NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) { 172 //返回e元素所在的节点 173 NODE *node = root_; 174 while (node != nullptr) { 175 int cmp = cmp_(e, node->e); 176 if (cmp == 0) //找到了元素 177 return node; 178 if (cmp > 0) { //待寻找元素大于节点存储的元素 179 node = node->right; 180 } else { //待寻找元素小于节点存储的元素 181 node = node->left; 182 } 183 } 184 return nullptr; 185 } 186 187 NODE* predecessor(NODE *node) { 188 //返回node的前驱节点 189 if (node == nullptr) 190 return nullptr; 191 //前驱节点在左子树 192 NODE *tmp = node->left; 193 if (tmp != nullptr) { 194 while (tmp->right != nullptr) 195 tmp = tmp->right; 196 return tmp; 197 } 198 //从父节点，祖父节点中寻找前驱节点 199 while (node->parent != nullptr && node == node->parent->left) { 200 node = node->parent; 201 } 202 return node->parent; 203 } 204 205 NODE* successor(NODE *node) { 206 //返回node的后继节点 207 if (node == nullptr) 208 return nullptr; 209 //后继节点在右子树 210 NODE *tmp = node->right; 211 if (tmp != nullptr) { 212 while (tmp->left != nullptr) 213 tmp = tmp->left; 214 return tmp; 215 } 216 //从父节点，祖父节点中寻找后继节点 217 while (node->parent != nullptr && node == node->parent->right) { 218 node = node->parent; 219 } 220 return node->parent; 221 } 222 223 #if 0 224 //统一接口版本(未优化) 225 void rotate(NODE *r, NODE *a, NODE *b, NODE *c, NODE *d, NODE *e, NODE *f, 226 NODE *g) { 227 //统一的旋转操作 228 /* r是变换前高度最低的不平衡节点 229 * 传入的参数a,b,c,d,e,f,g是经过变换后节点应该在的位置 230 * d 231 * / \ 232 * b f 233 * / \ / \ 234 * a c e g 235 * a,c,e,g均有可能为空，所以要对它们做判空处理 236 * b,d,f绝不为空 237 * d的parent可能为null，则d就为根节点，所以就要改变树中root_的指向 238 */ 239 //对d节点做处理 240 d->parent = r->parent; 241 if (r->isLeftChild()) 242 r->parent->left = d; 243 else if (r->isRightChild()) 244 r->parent->right = d; 245 else 246 root_ = d; 247 //a-b-c 248 b->left = a; 249 b->right = c; 250 if (a != nullptr) 251 a->parent = b; 252 if (c != nullptr) 253 c->parent = b; 254 b->updateHeight(); 255 //e-f-g 256 f->left = e; 257 f->right = g; 258 if (e != nullptr) 259 e->parent = f; 260 if (g != nullptr) 261 g->parent = f; 262 f->updateHeight(); 263 //b-d-f 264 d->left = b; 265 d->right = f; 266 b->parent = d; 267 f->parent = d; 268 d->updateHeight(); 269 } 270 271 void rebalance(NODE *gNode) { 272 //恢复平衡,grand为高度最低的不平衡节点 273 NODE *pNode = gNode->tallerChild(); 274 NODE *nNode = pNode->tallerChild(); 275 if (pNode->isLeftChild()) { 276 if (nNode->isLeftChild()) { 277 //LL 278 /* 279 * gNode(f) 280 * / \ 变换后 281 * pNode(d) g ====> pNode(d) 282 * / \ / \ 283 * nNode(b) e nNode(b) gNode(f) 284 * / \ / \ / \ 285 * a c a c e g 286 */ 287 rotate(gNode, nNode->left, nNode, nNode->right, pNode, 288 pNode->right, gNode, gNode->right); 289 } else { 290 //LR 291 /* 292 * gNode(f) 293 * / \ 变换后 294 * pNode(b) g ====> nNode(d) 295 * / \ / \ 296 * a nNode(d) pNode(b) gNode(f) 297 * / \ / \ / \ 298 * c e a c e g 299 */ 300 rotate(gNode, pNode->left, pNode, nNode->left, nNode, 301 nNode->right, gNode, gNode->right); 302 } 303 } else { 304 if (nNode->isLeftChild()) { 305 //RL 306 /* 307 * gNode(b) 308 * / \ 变换后 309 * a pNode(f) ====> nNode(d) 310 * / \ / \ 311 * nNode(d) g gNode(b) pNode(f) 312 * / \ / \ / \ 313 * c e a c e g 314 */ 315 rotate(gNode, gNode->left, gNode, nNode->left, nNode, 316 nNode->right, pNode, pNode->right); 317 } else { 318 //RR 319 /* 320 * gNode(b) 321 * / \ 变换后 322 * a pNode(d) ====> pNode(d) 323 * / \ / \ 324 * c nNode(f) gNode(b) nNode(f) 325 * / \ / \ / \ 326 * e g a c e g 327 */ 328 rotate(gNode, gNode->left, gNode, pNode->left, pNode, 329 nNode->left, nNode, nNode->right); 330 } 331 } 332 } 333 334 #endif 335 336 void rotate(NODE *r, NODE *b, NODE *c, NODE *d, NODE *e, NODE *f) { 337 //统一的旋转操作 338 /* r是变换前高度最低的不平衡节点 339 * 传入的参数b,c,d,e,f是经过变换后节点应该在的位置 340 * d 341 * / \ 342 * b f 343 * / \ / \ 344 * a c e g 345 * c,e均有可能为空，所以要对它们做判空处理 346 * b,d,f绝不为空 347 * d的parent可能为null，则d就为根节点，所以就要改变树中root_的指向 348 */ 349 //对d节点做处理 350 d->parent = r->parent; 351 if (r->isLeftChild()) 352 r->parent->left = d; 353 else if (r->isRightChild()) 354 r->parent->right = d; 355 else 356 root_ = d; 357 //b-c 358 b->right = c; 359 if (c != nullptr) 360 c->parent = b; 361 b->updateHeight(); 362 //e-f 363 f->left = e; 364 if (e != nullptr) 365 e->parent = f; 366 f->updateHeight(); 367 //b-d-f 368 d->left = b; 369 d->right = f; 370 b->parent = d; 371 f->parent = d; 372 d->updateHeight(); 373 } 374 375 void rebalance(NODE *gNode) { 376 //恢复平衡,grand为高度最低的不平衡节点 377 NODE *pNode = gNode->tallerChild(); 378 NODE *nNode = pNode->tallerChild(); 379 if (pNode->isLeftChild()) { 380 if (nNode->isLeftChild()) { 381 //LL 382 /* 383 * gNode(f) 384 * / \ 变换后 385 * pNode(d) g ====> pNode(d) 386 * / \ / \ 387 * nNode(b) e nNode(b) gNode(f) 388 * / \ / \ / \ 389 * a c a c e g 390 */ 391 rotate(gNode, nNode, nNode->right, pNode, pNode->right, gNode); 392 } else { 393 //LR 394 /* 395 * gNode(f) 396 * / \ 变换后 397 * pNode(b) g ====> nNode(d) 398 * / \ / \ 399 * a nNode(d) pNode(b) gNode(f) 400 * / \ / \ / \ 401 * c e a c e g 402 */ 403 rotate(gNode, pNode, nNode->left, nNode, nNode->right, gNode); 404 } 405 } else { 406 if (nNode->isLeftChild()) { 407 //RL 408 /* 409 * gNode(b) 410 * / \ 变换后 411 * a pNode(f) ====> nNode(d) 412 * / \ / \ 413 * nNode(d) g gNode(b) pNode(f) 414 * / \ / \ / \ 415 * c e a c e g 416 */ 417 rotate(gNode, gNode, nNode->left, nNode, nNode->right, pNode); 418 } else { 419 //RR 420 /* 421 * gNode(b) 422 * / \ 变换后 423 * a pNode(d) ====> pNode(d) 424 * / \ / \ 425 * c nNode(f) gNode(b) nNode(f) 426 * / \ / \ / \ 427 * e g a c e g 428 */ 429 rotate(gNode, gNode, pNode->left, pNode, nNode->left, nNode); 430 } 431 } 432 } 433 434 void afterAdd(NODE *node) { 435 //添加node之后的调整 436 if (node == nullptr) 437 return; 438 node = node->parent; 439 while (node != nullptr) { 440 if (node->isBalanced()) { 441 //如果节点平衡，则对其更新高度 442 node->updateHeight(); 443 } else { 444 //此时对第一个不平衡节点操作，使其平衡 445 rebalance(node); 446 //整棵树恢复平衡后,跳出循环 447 break; 448 } 449 node = node->parent; 450 } 451 } 452 453 void add(Element e, int (*cmp_)(Element e1, Element e2)) { 454 //当树为空时，添加的节点作为树的根节点 455 if (root_ == nullptr) { 456 root_ = new NODE(e, nullptr); 457 size_++; 458 //插入一个根节点之后进行调整 459 afterAdd(root_); 460 return; 461 } 462 //当添加的节点不是第一个节点 463 NODE *parent = root_; 464 NODE *node = root_; 465 int cmp = 0; //比较结果 466 while (node != nullptr) { 467 parent = node; //保存父节点 468 cmp = cmp_(e, node->e); //由函数指针来比较 469 if (cmp > 0) { 470 node = node->right; //添加的元素大于节点中的元素 471 } else if (cmp < 0) { 472 node = node->left; //添加的元素小于节点中的元素 473 } else { 474 node->e = e; //相等时就覆盖 475 return; //添加的元素等于节点中的元素,直接返回 476 } 477 } 478 //判断要插入父节点的哪个位置 479 NODE *newNode = new NODE(e, parent); //为新元素创建节点 480 if (cmp > 0) { 481 parent->right = newNode; //添加的元素大于节点中的元素 482 } else { 483 parent->left = newNode; //添加的元素小于节点中的元素 484 } 485 size_++; 486 //添加一个新节点之后进行调整 487 afterAdd(newNode); 488 } 489 490 void afterRemove(NODE *node) { 491 //删除node之后的调整 492 if (node == nullptr) 493 return; 494 node = node->parent; 495 while (node != nullptr) { 496 if (node->isBalanced()) { 497 //如果节点平衡，则对其更新高度 498 node->updateHeight(); 499 } else { 500 //此时对不平衡节点操作，使其平衡 501 rebalance(node); 502 } 503 node = node->parent; 504 } 505 } 506 507 void remove(NODE *node_) { 508 //删除某一节点 509 if (node_ == nullptr) 510 return; 511 size_--; 512 //优先删除度为2的节点 513 if (node_->hasTwoChildren()) { 514 NODE *pre = successor(node_); //找到node_的后继节点 515 node_->e = pre->e; //用后继节点的值覆盖度为2的节点的值 516 //删除后继节点(后继节点的度只能为1或0) 517 node_ = pre; 518 } 519 //此时node_的度必然为0或1 520 NODE *replacement = node_->left != nullptr ? node_->left : node_->right; 521 if (replacement != nullptr) { //node_的度为1 522 replacement->parent = node_->parent; 523 if (node_->parent == nullptr) //度为1的根节点 524 root_ = replacement; 525 else if (node_->parent->left == node_) 526 node_->parent->left = replacement; 527 else 528 node_->parent->right = replacement; 529 //所有删除操作准备完成，准备释放节点内存前进行平衡操作 530 afterRemove(node_); 531 delete node_; 532 } else if (node_->parent == nullptr) { //node_是叶子节点，也是根节点 533 root_ = nullptr; 534 //所有删除操作准备完成，准备释放节点内存前进行平衡操作 535 afterRemove(node_); 536 delete node_; 537 } else { //node_是叶子节点，但不是根节点 538 if (node_->parent->left == node_) 539 node_->parent->left = nullptr; 540 else 541 node_->parent->right = nullptr; 542 //所有删除操作准备完成，准备释放节点内存前进行平衡操作 543 afterRemove(node_); 544 delete node_; 545 } 546 } 547 548 void preorderTraversal(NODE *node, bool &stop, 549 bool (*visitor)(Element &e)) { 550 //递归实现前序遍历 551 if (node == nullptr || stop == true) 552 return; 553 stop = visitor(node->e); 554 preorderTraversal(node->left, stop, visitor); 555 preorderTraversal(node->right, stop, visitor); 556 } 557 558 void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) { 559 //递归实现中序遍历 560 if (node == nullptr || stop == true) 561 return; 562 inorderTraversal(node->left, stop, visitor); 563 if (stop == true) 564 return; 565 stop = visitor(node->e); 566 inorderTraversal(node->right, stop, visitor); 567 } 568 569 void postorderTraversal(NODE *node, bool &stop, 570 bool (*visitor)(Element &e)) { 571 //递归实现后序遍历 572 if (node == nullptr || stop == true) 573 return; 574 postorderTraversal(node->left, stop, visitor); 575 postorderTraversal(node->right, stop, visitor); 576 if (stop == true) 577 return; 578 stop = visitor(node->e); 579 } 580 581 void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) { 582 if (node == nullptr) 583 return; 584 using namespace std; 585 queue<NODE*> q; 586 q.push(node); 587 while (!q.empty()) { 588 NODE *node = q.front(); 589 if (visitor(node->e) == true) 590 return; 591 if (node->left != nullptr) 592 q.push(node->left); 593 if (node->right != nullptr) 594 q.push(node->right); 595 q.pop(); 596 } 597 } 598 599 int height(NODE *node) { 600 //某一节点的高度 601 return node->height; 602 } 603 604 bool isComplete(NODE *node) { 605 if (node == nullptr) 606 return false; 607 using namespace std; 608 queue<NODE*> q; 609 q.push(node); 610 bool leaf = false; //判断接下来的节点是否为叶子节点 611 while (!q.empty()) { 612 NODE *node = q.front(); 613 if (leaf && !node->isLeaf()) //判断叶子节点 614 return false; 615 if (node->left != nullptr) { 616 q.push(node->left); 617 } else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr 618 return false; 619 } 620 if (node->right != nullptr) { 621 q.push(node->right); 622 } else { //node->right==nullptr 623 leaf = true; 624 } 625 q.pop(); 626 } 627 return true; 628 } 629 630 }; 631 632 template<typename Element> 633 BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) : 634 size_(0), root_(nullptr), cmp_(cmp) { 635 //树的构造函数 636 } 637 638 template<typename Element> 639 BinarySearchTree<Element>::~BinarySearchTree() { 640 // 析构函数 641 clear(); 642 } 643 644 template<typename Element> 645 inline int BinarySearchTree<Element>::size() { 646 //返回元素个数 647 return size_; 648 } 649 650 template<typename Element> 651 inline bool BinarySearchTree<Element>::isEmpty() { 652 //判断是否为空树 653 return size_ == 0; 654 } 655 656 #endif /* SRC_BINARYSEARCHTREE_H_ */
main方法
1 /* 2 * main.cpp 3 * 4 * Created on: 2020年1月29日 5 * Author: LuYonglei 6 */ 7 8 #include "BinarySearchTree.h" 9 #include <iostream> 10 #include <time.h> 11 12 using namespace std; 13 14 template<typename Element> 15 int compare(Element e1, Element e2) { 16 //比较函数,相同返回0,e1<e2返回-1,e1>e2返回1 17 return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1); 18 } 19 20 template<typename Elemnet> 21 bool visitor(Elemnet &e) { 22 cout << e << " "; 23 cout << endl; 24 return false; //若返回true，则在遍历时会退出 25 } 26 27 int main(int argc, char **argv) { 28 BinarySearchTree<double> a(compare); 29 // a.add(85); 30 // a.add(19); 31 // a.add(69); 32 // a.add(3); 33 // a.add(7); 34 // a.add(99); 35 // a.add(95); 36 // a.add(2); 37 // a.add(1); 38 // a.add(70); 39 // a.add(44); 40 // a.add(58); 41 // a.add(11); 42 // a.add(21); 43 // a.add(14); 44 // a.add(93); 45 // a.add(57); 46 // a.add(4); 47 // a.add(56); 48 clock_t start = clock(); 49 for (int i = 0; i < 1000000; i++) { 50 a.add(i); 51 } 52 for (int i = 0; i < 1000000; i++) { 53 a.remove(i); 54 } 55 // a.inorderTraversal(visitor); 56 clock_t end = clock(); 57 cout << end - start << endl; 58 // cout <<a.height()<< endl; 59 // cout << a.isComplete() << endl; 60 // a.remove(7); 61 // a.clear(); 62 // a.levelOrderTraversal(visitor); 63 // cout << endl; 64 // cout<<a.contains(0)<<endl; 65 }
版权声明：本文为luyl原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。