LR型违规：
LR型是指B节点的个数大于二叔节点的个数 ， 其调整策略和AVL树一样先对大叔进行一个左旋 ， 在对根进行一个右旋 。
经过旋转之后我们发现根 ， 大叔 ， 还B这三个节点的左右孩子发生了变化 ， 因此需要对其进行检查看是否满足SBT树的定义
RL型同理老铁们可以下去自己画一下 。
对应调整代码：
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;//返回调整后的头部}
3.BST树的插入
BST树的插入和搜索二叉树的插入基本一样只不过多了调整部分如果不太清楚的老铁可以去看我之前的博客
对应代码：
// 现在 ， 以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;}
4.SBT的删除
SBT的删除和AVL树删除的情况基本一样至少调整方式不一样 ， 如果不太清楚可以看一下我的哪篇文章 。
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;}}