二叉树(五)平衡二叉树(AVL树)
2020-02-05 16:00:51来源:博客园 阅读 ()
二叉树(五)平衡二叉树(AVL树)
平衡二叉树(AVL树)的自平衡(LL->R、RR->L、LR->LR、RL->RL)、增、删 等操作。
main.cpp:
#include <iostream> #include "AVLTree.h" using namespace std; int main() { AVLTree<int> avl; auto Add = [&avl](int _key) { cout << "Add " << _key << ":" << endl; avl.insert(_key); avl.levelTraversal(); cout << endl << "size: " << avl.size() << " level: " << avl.level() << endl << endl; }; auto il = { 0,1,4,2,5,3,6 }; for (auto& key : il) Add(key); auto Del = [&avl](int _key) { cout << "Del " << _key << ":" << endl; avl.erase(_key); avl.levelTraversal(); cout << endl << "size: " << avl.size() << " level: " << avl.level() << endl << endl; }; Del(4); Del(1); Del(5); Del(6); Del(2); return 0; }
AVLTree.h:
#pragma once #ifndef __AVLTREE_H__ #define __AVLTREE_H__ #include <queue> #include <initializer_list> template<typename _Ty> class AVLTree { private: struct Node { _Ty key; int bf = 0; Node* left = nullptr; Node* right = nullptr; Node* parent = nullptr; Node(const _Ty& _key) :key(_key) {} }; public: AVLTree() = default; template<typename _Iter> AVLTree(_Iter, _Iter); AVLTree(const std::initializer_list<_Ty>&); AVLTree(const AVLTree<_Ty>&); AVLTree(AVLTree<_Ty>&&) noexcept; ~AVLTree() { clear(root); } void clear() { clear(root); root = nullptr; } bool empty() const { return size_n == 0; } size_t size() const { return size_n; } Node* getRoot() const { return root; } void show() const { show(root); } void showPreorder() const { showPreorder(root); } void levelTraversal() const { levelTraversal(root); } size_t level() const; void swap(AVLTree<_Ty>&); void insert(const _Ty&); template<typename _Iter> void insert(_Iter, _Iter); size_t erase(const _Ty&); void erase(Node*); Node* find(const _Ty& _key) const { return find(root, _key); } Node* iterative_find(const _Ty& _key) const { return iterative_find(root, _key); } Node* maximum() const { return maximum(root); } Node* minimum() const { return minimum(root); } private: void copy(Node*); void clear(Node*&); void show(Node*) const; void showPreorder(Node*) const; void levelTraversal(Node*) const; Node* find(Node*, const _Ty&) const; Node* iterative_find(Node*, const _Ty&) const; Node* maximum(Node*) const; Node* minimum(Node*) const; void LL_R(Node*); void RR_L(Node*); void LR_LR(Node*); void RL_RL(Node*); private: size_t size_n = 0; Node* root = nullptr; }; template<typename _Ty> template<typename _Iter> AVLTree<_Ty>::AVLTree(_Iter _it1, _Iter _it2) { while (_it1 != _it2) { insert(*_it1); ++_it1; } } template<typename _Ty> AVLTree<_Ty>::AVLTree(const std::initializer_list<_Ty>& _il) { for (const auto& key : _il) insert(key); } template<typename _Ty> AVLTree<_Ty>::AVLTree(const AVLTree<_Ty>& _right) { copy(_right.getRoot()); } template<typename _Ty> AVLTree<_Ty>::AVLTree(AVLTree<_Ty>&& _right) noexcept { root = _right.root; size_n = _right.size_n; _right.root = nullptr; _right.size_n = 0; } template<typename _Ty> size_t AVLTree<_Ty>::level() const { if (root == nullptr) 0; size_t n = 0; std::queue<Node*> nodePointers; nodePointers.push(root); while (!nodePointers.empty()) { Node* levelBegin = nodePointers.front(); Node* levelEnd = nodePointers.back(); Node* cur = levelBegin; while (true) { if (cur->left != nullptr) nodePointers.push(cur->left); if (cur->right != nullptr) nodePointers.push(cur->right); if (cur == levelEnd) break; nodePointers.pop(); cur = nodePointers.front(); } nodePointers.pop(); ++n; } return n; } template<typename _Ty> void AVLTree<_Ty>::copy(Node* _node) { if (_node == nullptr) return; insert(_node->key); copy(_node->left); copy(_node->right); } template<typename _Ty> void AVLTree<_Ty>::clear(Node*& _node) { if (_node == nullptr) return; clear(_node->left); clear(_node->right); delete _node; _node = nullptr; --size_n; } template<typename _Ty> void AVLTree<_Ty>::show(Node* _node) const { if (_node == nullptr) return; show(_node->left); std::cout << _node->key << " "; show(_node->right); } template<typename _Ty> void AVLTree<_Ty>::showPreorder(Node* _node) const { if (_node == nullptr) return; std::cout << _node->key << " "; show(_node->left); show(_node->right); } template<typename _Ty> void AVLTree<_Ty>::levelTraversal(Node* _node) const { if (_node == nullptr) return; std::queue<Node*> nodePointers; nodePointers.push(_node); while (!nodePointers.empty()) { Node* cur = nodePointers.front(); std::cout << cur->key << " "; if (cur->left != nullptr) nodePointers.push(cur->left); if (cur->right != nullptr) nodePointers.push(cur->right); nodePointers.pop(); } } template<typename _Ty> void AVLTree<_Ty>::swap(AVLTree<_Ty>& _right) { std::swap(root, _right->root); std::swap(size_n, _right->size_n); } template<typename _Ty> void AVLTree<_Ty>::LL_R(Node* _root) { Node* leftNode = _root->left; if (_root->parent != nullptr) { if (_root->parent->left == _root) _root->parent->left = leftNode; else _root->parent->right = leftNode; } else root = leftNode; leftNode->parent = _root->parent; _root->left = leftNode->right; if (leftNode->right != nullptr) leftNode->right->parent = _root; _root->parent = leftNode; leftNode->right = _root; _root->bf = leftNode->bf = 0; } template<typename _Ty> void AVLTree<_Ty>::RR_L(Node* _root) { Node* rightNode = _root->right; if (_root->parent != nullptr) { if (_root->parent->right == _root) _root->parent->right = rightNode; else _root->parent->left = rightNode; } else root = rightNode; rightNode->parent = _root->parent; _root->right = rightNode->left; if (rightNode->left != nullptr) rightNode->left->parent = _root; _root->parent = rightNode; rightNode->left = _root; _root->bf = rightNode->bf = 0; } template<typename _Ty> void AVLTree<_Ty>::LR_LR(Node* _root) { RR_L(_root->left); LL_R(_root); if (_root->left == nullptr) _root->bf = 1; } template<typename _Ty> void AVLTree<_Ty>::RL_RL(Node* _root) { LL_R(_root->right); RR_L(_root); if (_root->right == nullptr) _root->bf = -1; } template<typename _Ty> void AVLTree<_Ty>::insert(const _Ty& _key) { ++size_n; if (root == nullptr) { root = new Node(_key); return; } Node* temp = root; while (true) { if (_key == temp->key) { --size_n; return; } else if (_key < temp->key && temp->left != nullptr) temp = temp->left; else if (_key < temp->key && temp->left == nullptr) break; else if (_key > temp->key&& temp->right != nullptr) temp = temp->right; else break; } Node* newNode = new Node(_key); newNode->parent = temp; if (_key < temp->key) { temp->left = newNode; temp->bf += -1; } else { temp->right = newNode; temp->bf += 1; } if (temp->left != nullptr && temp->right != nullptr) return; Node* pa = temp->parent; while (pa != nullptr) { if (temp == pa->left) pa->bf += -1; else pa->bf += 1; if (pa->bf == -2) { if (temp->bf == -1) LL_R(pa); else LR_LR(pa); break; } else if (pa->bf == 2) { if (temp->bf == -1) RL_RL(pa); else RR_L(pa); break; } temp = pa; pa = pa->parent; } } template<typename _Ty> template<typename _Iter> void AVLTree<_Ty>::insert(_Iter _it1, _Iter _it2) { while (_it1 != _it2) { insert(*_it1); ++_it1; } } template<typename _Ty> size_t AVLTree<_Ty>::erase(const _Ty& _key) { size_t n = 0; Node* del = find(_key); if (del != nullptr) { ++n; erase(del); } return n; } template<typename _Ty> void AVLTree<_Ty>::erase(Node* _node) { --size_n; Node* pa = nullptr; Node* temp = nullptr; if (_node->left == nullptr && _node->right == nullptr) { if (_node->parent == nullptr) { root = nullptr; delete _node; return; } if (_node == _node->parent->left) { _node->parent->left = nullptr; _node->parent->bf += 1; temp = _node->parent->right; } else { _node->parent->right = nullptr; _node->parent->bf += -1; temp = _node->parent->left; } pa = _node->parent; delete _node; } else if (!(_node->left != nullptr && _node->right != nullptr)) { if (_node->parent == nullptr) { if (_node->left != nullptr) root = _node->left; else root = _node->right; root->parent = nullptr; delete _node; return; } if (_node == _node->parent->left) { _node->parent->left = _node->left == nullptr ? _node->right : _node->left; if (_node->left != nullptr) _node->left->parent = _node->parent; else _node->right->parent = _node->parent; _node->parent->bf += 1; temp = _node->parent->right; } else { _node->parent->right = _node->left == nullptr ? _node->right : _node->left; if (_node->left != nullptr) _node->left->parent = _node->parent; else _node->right->parent = _node->parent; _node->parent->bf += -1; temp = _node->parent->left; } pa = _node->parent; delete _node; } else { ++size_n; if (_node->right != nullptr) { Node* de = minimum(_node->right); _node->key = de->key; erase(de); } else if (_node->left != nullptr) { Node* de = maximum(_node->left); _node->key = de->key; erase(de); } } if (pa != nullptr && pa->bf == 0) { temp = pa; pa = pa->parent; if (pa != nullptr) { if (temp == pa->left) { temp = pa->right; pa->bf += 1; } else { temp = pa->left; pa->bf += -1; } } } while (pa != nullptr) { if (pa->bf == -2) { if (temp->bf == -1 || temp->bf == 0) LL_R(pa); else LR_LR(pa); } else if (pa->bf == 2) { if (temp->bf == -1) RL_RL(pa); else RR_L(pa); } else break; bool isLeft = temp == pa->left ? 1 : 0; pa = temp->parent; if (pa != nullptr) { if (isLeft) { temp = pa->left; pa->bf += -1; } else { temp = pa->right; pa->bf += 1; } } } } template<typename _Ty> typename AVLTree<_Ty>::Node* AVLTree<_Ty>::find(Node* _node, const _Ty& _key) const { if (_node == nullptr || _node->key == _key) return _node; if (_key < _node->key) return find(_node->left, _key); else return find(_node->right, _key); } template<typename _Ty> typename AVLTree<_Ty>::Node* AVLTree<_Ty>::iterative_find(Node* _node, const _Ty& _key) const { while (_node != nullptr && _node->key != _key) { if (_key < _node->key) _node = _node->left; else _node = _node->right; } return _node; } template<typename _Ty> typename AVLTree<_Ty>::Node* AVLTree<_Ty>::maximum(Node* _node) const { if (_node == nullptr) return _node; while (_node->right != nullptr) _node = _node->right; return _node; } template<typename _Ty> typename AVLTree<_Ty>::Node* AVLTree<_Ty>::minimum(Node* _node) const { if (_node == nullptr) return _node; while (_node->left != nullptr) _node = _node->left; return _node; } #endif // !__AVLTREE_H__
原文链接:https://www.cnblogs.com/teternity/p/AVLTree.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:UOJ192 最强跳蚤
下一篇:关于C/C++的各种优化
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 二叉堆(3)SkewHeap 2020-02-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash