Balanced binary search tree rotations

Key Takeaways

hello and welcome back today I'm going to introduce probably one of the most important types of trees in computer science which are balanced binary search trees balanced binary search trees are very different from the traditional binary search tree because they not only conform to the binary search tree invariant but they are also balanced what I mean by balanced is that there is self adjusting to maintain a logarithmic height in proportion to the number of nodes they hold this is very important because it keeps operations such as insertion and deletion extremely fast because the tree is much more squashed in terms of complexity a binary search tree has average logarithmic operations which is quite good however the worst case still remains linear because the tree could degrade into a chain for some inputs one such input is a sequence of increasing numbers to avoid this linear complexity we've invented balanced and higher search trees in which the worst case is logarithmic for all operations which makes them very appealing central to how nearly all balanced binary search tree implementations keep themselves balanced is the concept of tree rotations which is going to be the main topic of this video later we'll actually look at some specific types of balanced binary search trees to see how these rotations come into play so the secret ingredient to most on steiner search tree implementations is a combination of two things one a clever tree invariant and tree rotations a tree invariant is simply a property or a rule that you impose on your tree such that it must be met at the end of every operation to ensure that the invariant is always satisfied a series of tree rotations are norm applied we'll get back to this concept of invariance in the later video so don't worry about them so much for now right now we're going to look at how tree rotations work suppose our invariant is not satisfied and to fix it we need to do a right rotation about node a assuming node a has a left child B we can perform a right rotation to put B where note a was and push node a down to become B's right child when I first learned about this in my undergrad I was mind blown literally I thought it was absurd or even to the point of being illegal that we should be allowed to do this and just move around nodes and a tree but what I realized since is that a transformation like this is totally legitimate since we're not breaking the binary search tree invariant in any way if you inspect the left tree you'll discover that in terms of ordering and placement node D is less than node B is less than E is less than a is less than C then you inspect the right tree and remark that well this is also true a bit more detail on why performing tree rotations is a valid operation first you have to remember that all balanced binary search trees are binary search trees meaning that the binary search tree invariant holds so for every node n the values in the left subtree are less than the value of n and the values and the right subtree are all greater than the value of n so in this sense it doesn't matter what the tree structure itself looks like all that fundamentally matters is that the binary search tree invariant holds this means we are free to shuffle transform or even rotate the values and nodes in our tree as we please as long as the binary search tree environment remains satisfied now let's look at how these rotations are done in great detail for simplicity since the rotations are symmetric our will only do the right rotation and you should be able to figure out the left rotation on your own first have a look at the tree on the right notice that there are directed edges pointing downwards and another node P above a which may or may not exist this is why there is a dotted line on that edge if a node a does have a parent node P then it is important that we take it into account when doing the rotation in either case we start with a pointer reference to note a this is the orange arrow then we'll want a pointer to node B after that set a x' left a pointer to point to B's right child then change B's right pointer to point to node a and we've successfully done a right rotation if we rearrange the nodes this is what we would end up with however notice that there's a slight problem if node a had a parent node then either the parents left or right pointer would still be referencing a this is problematic since B is A's successor after the rotation so we change the link to now point to B this step is usually done on the recursive call back using the return value of the right rotate function we just finished looking at the case where each node has a reference the left and the right child nodes but in some balanced binary search tree implementations it's more convenient for nodes to also have a reference to the parent node this complicates tree rotations because now instead of updating three pointers we need to update six pointers let's have a look in this case where we also have a parent link every node is in a sense doubly-linked we start off with a pointer referencing a and the first thing we'll want to do is also reference node B and node P so we don't lose them as we shuffle around pointers next we'll adjust the left subtree of a to make a x' left pointer reference B's right subtree of course throughout this example assume B is not null if you're paranoid you can add an extra if statement to check for this condition however it would be a mistake to assume B's right subtree is not null we actually have to check against this before setting B's right child's parent to reference a next let's make a the right subtree of be so set B's right pointer to reference a now make a parent pointer a reference be the last thing we need to do is adjust the reference to the parent node P so make B's parent pointer reference P and now the very last thing I promise is to make peas left or right pointer reference the successor node B notice that we need to check if P is not null because it might not exist this would be the case for the root node if we readjust the tree you will see that we correctly did a right rotation there are a lot of steps in doing this right rotation and it's a very error-prone process which is why I wanted to do it in such detail in the next video we'll look at how we can use these three rotations we just learned about to insert nodes into an AVL tree thank you for watching if you learn something please like this video and subscribe for more mathematics and computer science videos thank you