1 void RotateR(Node* parent) 2 { 3 Node* subL = parent->_left; 4 Node* subLR = subL->_right; 5 //换指向 6 parent->_left = subLR; 7 subL->_right = parent; 8 9 if (subLR) 10 { 11 subLR->_parent = parent; 12 } 13 14 Node* PParent = parent->_parent; //判断parent是否有父节点 15 if (PParent) 16 { 17 if (parent == PParent->_left) 18 { 19 PParent->_left = subL; 20 subL->_parent = PParent; 21 } 22 else 23 { 24 PParent->_right = subL; 25 subL->_parent = PParent; 26 } 27 } 28 else 29 { 30 _root = subL; 31 subL->_parent = NULL; 32 } 33 parent->_parent = subL; 34 //修改bf 35 subL->_bf = 0; 36 parent->_bf = 0; 37 } 38 39 // 40 void RotateL(Node* parent) 41 { 42 Node* subR = parent->_right; 43 Node* subRL = subR->_left; 44 //调整指向 45 subR->_left=parent; 46 parent->_right = subRL; 47 48 if (subRL) //如果subRL非空 49 { 50 subRL->_parent = parent; 51 } 52 53 Node* PPNode = parent->_parent; 54 if (PPNode) 55 { 56 if (PPNode->_left == parent) 57 PPNode->_left = subR; 58 else 59 PPNode->_right = subR; 60 61 //subR的父节点改变 62 subR->_parent = PPNode; 63 } 64 else 65 { 66 _root = subR; //根节点 67 subR->_parent = NULL; 68 } 69 parent->_parent = subR; 70 /*修改bf*/ 71 parent->_bf = subR->_bf = 0; 72 } 73 74 //双旋(左右、、右左) 75 void RotateRL(Node* parent) 76 { 77 Node* subR = parent->_right; 78 Node* subRL = subR->_left; 79 int bf = subRL->_bf; 80 81 RotateR(parent->_right); 82 RotateL(parent); 83 84 //调整subR和parent的平衡因子 85 if (bf == -1) 86 subR->_bf = 1; // subR的bf在左旋中已经置0了，这里就没有再写 87 else if (bf == 1) 88 parent->_bf = -1; 89 90 else 91 { 92 parent->_bf = 0; 93 subRL->_bf = 0; 94 } 95 } 96 97 void RotateLR(Node* parent) 98 { 99 Node* subL = parent->_left; 100 Node* subLR = subL->_right; 101 int bf = subLR->_bf; 102 RotateL(parent->_left); 103 RotateR(parent); 104 105 //调整parent和subL的平衡因子 106 if (bf == -1) 107 parent->_bf = 1; //subL的bf在左旋中已经置0了，这里就没有再写 108 else if (bf == 1) 109 subL->_bf = -1; //parent的bf在左旋中已经置0了 110 else 111 { 112 subL->_bf = 0; 113 parent = 0; 114 } 115 }