Hello @betamaster97156, that's a lot of code! Thank you very much for your submission I would like to give you few remarks regarding your code.
In the challenge, we asked you to build a tree from an array of values and create a function that inserts a whole array of values.
Self-balancing trees are great, they can save us a lot of time. The difference between
log n and
n is huge. But sometimes auto-balancing is not the best idea. Let's say that we use our
insert function to add few thousand elements. In production, this is sometimes handled by the single call to the
So we add elements to the tree normally, without auto-balancing. In result, we have (probably) unbalanced BST tree.
rebalance function will take this tree and will construct a balanced version of this tree in linear time.
We know that building BST from an array is an
O(n log n) operation. So how can we construct the balanced tree in
O(n)? This is possible because BST gives us direct access to all elements in a sorted manner (by a simple in-order traversal). And from sorted array, we can build balanced BST in
In production, these two methods are often combined. Single element insert? Rotations. Insertion of many (in regards to the current size of the tree) elements? Insertion without rotations and rebalancing after the last insert.
Your code uses a single class,
Node. In the case of AVL trees, this might be a bit confusing. For example, what is the height of the single node? This question does not make any sense, right? And yet, your code does answer it.
It was our suggestion to use a single class. But in BST you don't have to store root or height internally. From a single node - root (global variable) you can access every bit of information related to the tree.
In most implementations of the AVL (and of more complex tree structures) you will find two classes -
TreeMember) (which represents a single node, has
right properties) and
Your code is technically valid, but it does not make much sense in regard to OOP.
There is a
hmap variable in your code which is used only for printing out the tree. This is not the best use of memory. In trees, you only need a reference to the root element to be able to access all nodes level by level. There is a well-known graph algorithm named breadth-first search that traverses trees and graphs level by level.
On the other hand,
hmap might be useful for some sort of debugging. You can introduce a single global boolean variable called
True -> create
hmap and populate it.
Your code implements 8 rotation rules. You only need two of them - left and right. Please note that AVL tree is always balanced, this reduces the number of the possible situation that requires rotation. Sometimes you need to make two rotations, one after another. But there should be only two functions to handle rotations.
There are many resources that explain why only two types of rotations are needed, but I think that the best idea is to take pencil and simply try to crack this problem