5.代码汇总
【含代码实现SizeBalanceTree详解】#pragma once #include#include#includeusing namespace std;templatestruct SBTNode{SBTNode(const pairkv = pair()):_kv(kv),_left(nullptr),_right(nullptr),_size(1){}pair_kv;SBTNode* _left;SBTNode* _right;int _size;//节点的个数};templateclass SizeBalancedTreeMap {typedef SBTNode Node;public:Node* rightRotate(Node* cur) {Node* leftNode = cur->_left;cur->_left = leftNode->_right;leftNode->_right = cur;leftNode->_size = cur->_size;//重新调整节点个数cur->_size = (cur->_left ? cur->_left->_size : 0) + (cur->_right ? cur->_right->_size : 0)+1;//重新计算节点个数return leftNode;//返回调整后的新头部}Node* leftRotate(Node* cur) {Node* rightNode = cur->_right;cur->_right = rightNode->_left;rightNode->_left = cur;rightNode->_size = cur->_size;//重新调整节点个数cur->_size = (cur->_left ? cur->_left->_size : 0) + (cur->_right ? cur->_right->_size : 0) + 1;//重新计算节点的个数return rightNode;//返回新的头部}Node* maintain(Node* cur) {if (cur == nullptr) {return nullptr;}//将节点的个数拿出来int leftSize = cur->_left != nullptr ? cur->_left->_size : 0;int leftLeftSize = cur->_left && cur->_left->_left ? cur->_left->_left->_size : 0;int leftRightSize = cur->_left && cur->_left->_right ? cur->_left->_right->_size : 0;int rightSize = cur->_right? cur->_right->_size : 0;int rightLeftSize = cur->_right && cur->_right->_left ? cur->_right->_left->_size : 0;int rightRightSize = cur->_right && cur->_right->_right ? cur->_right->_right->_size : 0;if (leftLeftSize > rightSize) {//LL型cur = rightRotate(cur);//右旋cur->_right = maintain(cur->_right);//递归检查cur = maintain(cur);}else if (leftRightSize > rightSize) {//LR型 ， 调整完成之后递归检查cur->_left = leftRotate(cur->_left);cur = rightRotate(cur);cur->_left = maintain(cur->_left);cur->_right = maintain(cur->_right);cur = maintain(cur);}else if (rightRightSize > leftSize) {//RR型 ， 调整后并且检查cur = leftRotate(cur);cur->_left = maintain(cur->_left);cur = maintain(cur);}else if (rightLeftSize > leftSize) {//RL型 ， 调整后并检查cur->_right = rightRotate(cur->_right);cur = leftRotate(cur);cur->_left = maintain(cur->_left);cur->_right = maintain(cur->_right);cur = maintain(cur);}return cur;//返回调整后的头部}// 现在 ， 以cur为头的树上 ， 新增 ， 加(key, value)这样的记录// 加完之后 ， 会对cur做检查 ， 该调整调整// 返回 ， 调整完之后 ， 整棵树的新头部Node* add(Node* cur, const pair& kv) {if (cur == nullptr) {return new Node(kv);}else {cur->_size++;if (cur->_kv.first > kv.first) {cur->_left = add(cur->_left, kv);//去左边插入}else {cur->_right = add(cur->_right, kv);//去右边插入}}return maintain(cur);//返回插入好的新头部}bool Insert(const pair& kv) {Node* lastNode = findLastIndex(kv.first);if (lastNode && lastNode->_kv.first == kv.first) {//已经存在return false;}_root = add(_root, kv);return true;}Node* Delete(Node* cur, K key) {cur->_size--;if (cur->_kv.first > key) {cur->_left = Delete(cur->_left, key);}else if (cur->_kv.first < key) {cur->_right = Delete(cur->_right, key);//左边删并将新的头部返回}else {if (!cur->_left && !cur->_right) {//左为空并且右为空delete cur;cur = nullptr;}else if (!cur->_left && cur->_right) {//左为空但右不为空Node* subR = cur->_right;delete cur;cur = subR;}else if (cur->_left && !cur->_right) {//左不为空但右为空Node* subL = cur->_left;delete cur;cur = subL;}else {//左右都不为空找后继节点Node* pre = nullptr;Node* des = cur->_right;des->_size--;while (des->_left) {pre = des;des = des->_left;des->_size--;}if (pre) {//链接cur的左右孩子pre->_left = des->_right;des->_right = cur->_right;}des->_left = cur->_left;des->_size = des->_left->_size + (des->_right ? des->_right->_size:0) + 1;//更新sizedelete cur;cur = des;}}cur = maintain(cur);//平衡return cur;//返回新头部}void Erase(K key) {Node* lastNode = findLastIndex(key);if(lastNode)_root = Delete(_root,key);else {return;}}Node* findLastIndex(K key) {Node* pre = _root;Node* cur = _root;while (cur != nullptr) {pre = cur;if (cur->_kv.first==key) {break;}else if (cur->_kv.first>key) {cur = cur->_left;}else {cur = cur->_right;}}return pre;}Node* findLastNoSmallIndex(K key) {Node* ans = nullptr;Node* cur = _root;while (cur != nullptr) {if (cur->_kv.first==key) {ans = cur;break;}else if (cur->_kv.first>key) {ans = cur;cur = cur->_left;}else {cur = cur->_right;}}return ans;}Node* findLastNoBigIndex(K key) {SBTNode