TRAKLA2 - Single rotation

Single rotation

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions The AVL-tree below is out of balance after the last insertion (in the model solution you can see the state before and after the insertion). Balance the tree by making a rotation. Rotations can be made by modifying edges, ie. by drag&dropping the edges to point to a new node. The tree is updated when the Update References button is pressed. Do the update after you have moved all the edges that should change in the rotation. The number beside each node tells the height of the subtree. Each node is represented as a circle containing a letter (key field). If (by a mistake) triangle appears on the screen, it means that there is a cycle in the data structure, and it cannot be represented as a tree anymore. The notation used is common in C language in which records a defined in terms of structs (i.e., "->" refers to a field). You can assume that the tree is defined as follows: struct node { char key; struct node left; struct node right; }; struct node p, f;
Single Rotations // p is unbalanced, f is p's father if (f->left == p) { if (height(p.left) > height(p.right)) { f->left = p->left; // single rotation right p->left = f->left->right; f->left->right = p; } else { // height(p.left) < height(p.right) f->left = p->right; // single rotation left p->right = f->left->left; f->left->left = p; } } else { // f->right == p if (height(p.left) < height(p.right)) { f->right = p->right; // single rotation left p->right = f->right->left; f->right->left = p; } else { // height(p.left) > height(p.right) f->right = p->left; // single rotation right p->left = f->right->right; f->right->right = p; } }