Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //solution = chainLength is 3
- std::string backtrack(Node * x, std::string state){
- if(x->left){
- backtrack(x->left, state + 'L');
- }
- if(state.length() == 3){
- return state.substr(0, 2);
- }
- if(x->right){
- backtrack(x->right, state + 'R');
- }
- }
- //
- // Check if node x is unbalanced (i.e., the heights of its
- // two children differ by more than one). If it is, rebalance
- // at x using one of rotateLeft, rotateRight, doubleRotateLeft,
- // or doubleRotateRight, whichever is appropriate.
- //
- void balance( Node *& x ) {
- int balance = -1;
- if(x){
- int leftHeight = ( x->left ? x->left->height : -1 );
- int rightHeight = ( x->right ? x->right->height : -1 );
- balance = leftHeight - rightHeight;
- }
- bool isBalanced = abs(balance) <= 1;
- if(isBalanced){
- return;
- }
- std::string myCase = backtrack(x, "");
- if(myCase == "LL"){
- rotateRight(x);
- }
- if(myCase == "LR"){
- doubleRotateRight(x);
- }
- if(myCase == "RL"){
- doubleRotateLeft(x);
- }
- if(myCase == "RR"){
- rotateLeft(x);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement