AVLTree
- 规定平衡因子 = 右子树高度 - 左子树高度
- 更新平衡因子
- 平衡因子>1或<-1，需要旋转调整
bool insert(const K& key) {
if (_root == nullptr) {
_root->_data = key;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (cur->_data > key) {
cur = cur->_left;
parent = cur;
}
else if(cur->_data<key){
cur = cur->_right;
parent = cur;
}
else {
return false;
}
}
cur = new Node(key);
//把cur链接上，判断是左还是右孩子
if (parent->_date > key) {
parent->_left = cur;
cur->_parent = parent;
}
else {
parent->_right = cur;
cur->_parent = parent;
}
//更新父亲平衡因子，需要向上检测父亲平衡因子是否符合规则
while (parent) {
//平衡因子只能从下往上更新
if (parent->_left = cur) {
parent->_bf--;
}
else {
parent->_bf++;
}
if (parent->_bf == 0) {
break;
}
else if(parent->_bf==1||parent->_bf==-1){
//说明父亲结点之前平衡因子是0，需要向上更新
cur = parent;
parent = cur->_parent;
}
else if(parent->_bf==2||parent->_bf==-2){
//说明父亲结点平衡因子是2或-2违反平衡性
if (parent->_bf == 2) {
if (cur->_bf == 1) {
_RotateL(parent);
}
else if (cur->_bf == -1) {
_RotateRL(parent);
}
}
else if(parent->_bf == -2) {
if (cur->_bf == -1) {
_RotateR(parent);
}
else if (cur->_bf == 1) {
_RotateLR(parent);
}
}
}
break;
}
return true;
}
AVL树旋转
左单旋
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) {
subRL->_parent = parent;
}
subR->_left = parent;
//父亲结点可能是子树，记录祖父
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_parent = pparent;
//如果parent是根节点
if (pparent == NULL) {
_root = subR;
}
else {
if (pparent->_left == parent) {
pparent->_left = subR;
}
else {
pparent->_right = subR;
}
}
//subR和parent的平衡因子变为0
subR->_bf = parent->_bf = 0;
}
右单旋
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) {
subLR->_parent = parent;
}
subL->_right = parent;
//因为parent可能是子树,记录parent的父亲
Node* pparent = parent->_parent;
parent->_parent = subL;
subL->_parent = pparent;
//panrent是根节点
if (pparent == NULL) {
_root = subL;
}
else
{
if (pparent->_left == parent) {
pparent->_left = subL;
}
else {
pparent->_right = subL;
}
}
//subL和parent的平衡因子变为0
subL->_bf = parent->_bf = 0;
}
左右双旋
void _RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
//旋转之前记录subLR的平衡因子，用来修改旋转后subL和parent平衡因子
int bf = subLR->_bf;
_RotateL(subL);
_RotateR(parent);
if (bf == 1) {
subL->_bf = -1;
}
else {
parent->_bf = 1;
}
}
右左双旋
void _RotateRL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
//旋转之前记录subRL的平衡因子，用来修改旋转后subR和parent平衡因子
int bf = subRL->_bf;
_RotateR(subR);
_RotateL(parent);
if (bf == 1) {
subR->_bf = 0;
parent->_bf = -1;
}
else {
subR->_bf = 1;
parent->_bf = 0;
}
}
