new后,cur值发生改变,之后都不能使用地址进行比较

void RotateRL(Node* parent) {

//我是儿子(父的右孩子),但是主角是孙子

//记录下孙子(我的左孩子)

//记录下孙子的平衡因子(特征)

//对孙子进行右单旋,再左单旋

//更新平衡因子

Node* cur = parent->_right;

Node* grandson = cur->_left;

int bf = grandson->_bf;

RotateR(cur); //将孙子的爹,就是我,进行右单旋

RotateL(grandson ->_parent); //将进行左单旋

//三种情况

if (bf == 0) {

parent->_bf = 0;

cur->_bf = 0;

grandson->_bf = 0;

}

else if (bf == 1) {

parent->_bf = -1;

cur->_bf = 0;

grandson->_bf = 0;

}

else if (bf =www.laipuhuo.com= -1) {

parent->_bf = 0;

cur->_bf = 1;

grandson->_bf = 0;

}

else {

assert(false);

bool Insert(const std::pair<K,V> kv) {

//第一个结点做根

if (_root == nullptr) {

_root = new Node(kv);

_size++;

return true;

}

//搜索

Node* parent = _root;

Node* cur = _root;

while (cur) {

//大于往右走

if www.laipuhuo.com (kv.first > cur->_kv.first) {

parent = cur;

cur = cur->_right;

}

//小于往左走

else if (kv.first < cur->_kv.first) {

parent = cur;

cur = cur->_left;

}

//找到了,存在相同的key

else {

return false;

}

} //循环搜索...

//不存在,可以插入

cur = new Node(kv); //new后,cur值发生改变,之后都不能使用地址进行比较

if (cur->_kv.first < parent->_kv.first) {

parent->_left = cur;

}

else {

parent->_right = cur;

}

cur->_parent = parent; //三叉链链上父结点

_size++;

//调整平衡因子 : 最多到根,根的parent为nullptr

while www.laipuhuo.com (parent) {

//更新平衡因子

if (cur->_kv.first < parent->_kv.first) {

parent->_bf--;

}

else {

parent->_bf++;

}

//看是否需要调整

if (parent->_bf == 1 || parent->_bf == -1) {

cur = parent;

parent = parent->_parent;

}

else if(parent->_bf == 0){

break;

}

else if(parent->_www.laipuhuo.com bf == 2 || parent->_bf == -2){

if (parent->_bf == -2 && cur->_bf == -1) { //左左

RotateR(parent);

}

else if (parent->_bf == 2 && cur->_bf == 1) { //右右

RotateL(parent);

}

else if (parent->_bf == -2 && cur->_bf == 1) { //左右

RotateLR(parent);

}

else if(parent www.laipuhuo.com->_bf == 2 && cur->_bf == -1){ //右左

RotateRL(parent);

}

else { //错误检查

assert(false);

}

break;

}

else {

assert(false);

}

}

return true;

}