1 bool Insert(const K& key, const V& value) 2 { 3 if (_root == NULL) 4 { 5 _root = new Node(key, value); 6 return true; 7 } 8 Node* pcur = _root; 9 Node* parent = NULL; 10 while (pcur) 11 { 12 if (pcur->_key == key) 13 return false; 14 else if (pcur->_key < key) 15 { 16 parent = pcur; 17 pcur = pcur->_right; 18 } 19 else 20 { 21 parent = pcur; 22 pcur = pcur->_left; 23 } 24 } 25 if (parent->_key < key) 26 { 27 pcur = parent->_right = new Node(key, value); 28 pcur->_parent = parent; 29 } 30 else 31 { 32 pcur = parent->_left = new Node(key, value); 33 pcur->_parent = parent; 34 } 35 36 while (parent) 37 { 38 //修正平衡因子 39 if (pcur == parent->_left) 40 { 41 parent->_bf--; 42 } 43 if (pcur == parent->_right) 44 { 45 parent->_bf++; 46 } 47 // 48 if (parent->_bf == 0) 49 break; 50 else if (parent->_bf == -1 || parent->_bf == 1) 51 { 52 pcur = parent; 53 parent = pcur->_parent; 54 } 55 else //parent->bf -2 || 2 56 { 57 58 if (parent->_bf == -2) 59 { 60 if (pcur->_bf == -1) //右单旋 61 RotateR(parent); 62 else //左右双旋 63 RotateLR(parent); 64 } 65 else 66 { 67 if (pcur->_bf == 1) //左单旋 68 RotateL(parent); 69 else //右左双旋 70 RotateRL(parent); 71 } 72 break; 73 } 74 } 75 return true; 76 }
>>旋转