Now everybody knows good ole Binary Search Trees, right? No? Okay, for those of you who are new to that, I will probably write about it in another post soon (EDIT: That post is now UP!). In the meantime, you may get your arse out of my blog and go Google it or something. For the others who have already been introduced to that concept, I bring you another, simple, quite innocuous little topic: rotations.
Now rotations are used to shift two nodes in a BST relative to each other, while maintaining the Binary Search Tree Property: the left child of every node is smaller than it, while the right child is larger than it.
In other words, a node and its subtrees in a BST look something like this:
Here, 'L' is used to refer to the node at the root of the left subtree, and 'R' as the root of the right subtree. Note that L<P<R for all nodes P.
The whole point of rotations is to take two nodes (a parent and any one of its children) and change their relative vertical positions without changing their horizontal ones. In other words, you want to maintain the L<P<R property, but you want to change the parent from the current node to the other node (which is its immediate child: rotations only work on adjacent nodes).
In pictures, what you want to do is this:
Now look at the little dude at the bottom. If he looks upwards, what he sees is the nodes in the order c A d B e. This is basically the left-to-right order (the inorder traversal) of the subtree, with c<A<d<B<e (check it!). Notice how we managed to make B the parent and A the child without disturbing this left-to-right order.
Rotation works both ways, as shown in the above image. Converting to the left side is called the right rotate (as the child B is on the RIGHT) and converting to the right side is called left rotate.
Frankly, I think the word "rotation" is a misnomer. It looks nothing like a rotation! IMO, it looks more like the node B climbs vertically up while node A climbs down (look at the image: they are in the same horizontal position). But to each man his own.
Anyway, let's get down to the nitty-gritty. Here are the steps you have to follow to rotate:
Now rotations are used to shift two nodes in a BST relative to each other, while maintaining the Binary Search Tree Property: the left child of every node is smaller than it, while the right child is larger than it.
In other words, a node and its subtrees in a BST look something like this:
Here, 'L' is used to refer to the node at the root of the left subtree, and 'R' as the root of the right subtree. Note that L<P<R for all nodes P.
The whole point of rotations is to take two nodes (a parent and any one of its children) and change their relative vertical positions without changing their horizontal ones. In other words, you want to maintain the L<P<R property, but you want to change the parent from the current node to the other node (which is its immediate child: rotations only work on adjacent nodes).
In pictures, what you want to do is this:
Now look at the little dude at the bottom. If he looks upwards, what he sees is the nodes in the order c A d B e. This is basically the left-to-right order (the inorder traversal) of the subtree, with c<A<d<B<e (check it!). Notice how we managed to make B the parent and A the child without disturbing this left-to-right order.
Rotation works both ways, as shown in the above image. Converting to the left side is called the right rotate (as the child B is on the RIGHT) and converting to the right side is called left rotate.
Frankly, I think the word "rotation" is a misnomer. It looks nothing like a rotation! IMO, it looks more like the node B climbs vertically up while node A climbs down (look at the image: they are in the same horizontal position). But to each man his own.
Anyway, let's get down to the nitty-gritty. Here are the steps you have to follow to rotate:
Left Rotation
First, I'd like all of you to go through the below algorithm carefully and draw it, or if you can, try to visualize it. Drawing is better, less room for error.
- Initially, A is the parent and B is its RIGHT CHILD.
- Create a temporary node 'save' and give it A's value
- Set
save's left toparent.left - Set
save's right toparent.right.left - Copy B's value to
parent - Set
parent.righttoparent.right.right - Set
parent.lefttosave - And you're done
Note that all we are doing is constructing the new parent's left child, which is the A-subtree as seen in the right side of the diagram. Then we modify the children of the parent to the new children relative to their original positions (for example, the new
parent.right is now parent.right.right).Right Rotation
Right rotation can be done with some simple steps:
- Go to the left rotate section and copy the algorithm text
- Paste it somewhere, notepad or something
- Find all instances of 'left' and change them to 'right'
- Find all original instances of 'right' and change them to 'left'
- Read and understand
You didn't honestly expect me to do all the work for you, did you? You lazy ass! It's the same concept!
Usage
Hopefully, by now, you've got the essence of rotation. If not, go back up there and learn it.
Done? Good. Now rotation can be employed in several different uses. Most notable, however, is self-balancing binary search trees. With a simple rotation, you can shift the entire balance of the subtree from a left-bias to a right-bias, and vice versa. This technique will be employed in AVL Trees and Red-Black Trees, both of which I will be writing about ASAP.
Until then, keep learning
Ciao!
EDIT: Wikipedia has this brilliant image for rotation in BSTs.
By the way, for those who want to know, the first two images were created by me using this Chrome app called Gliffy. It's really, really handy. For all those using Chrome, I highly recommend it.
EDIT: Wikipedia has this brilliant image for rotation in BSTs.
By the way, for those who want to know, the first two images were created by me using this Chrome app called Gliffy. It's really, really handy. For all those using Chrome, I highly recommend it.
No comments:
Post a Comment