Self Balancing Tree
Self Balancing Tree
+ 35 comments Just want to let everyone know that in this question, the height of a "null" node is -1 INSTEAD OF 0, and the height of the leaf node is 0 INSTEAD OF 1. The latter will let you pass several cases, while the former will let you pass every case.
+ 1 comment Python 3 please
+ 3 comments JAVA Solution
static Node insert(Node root,int val) { if(root == null) { root = new Node(); root.val = val; root.ht = setHeight(root); return root; } if(val <= root.val) { root.left = insert(root.left, val); } else if (val > root.val) { root.right = insert(root.right, val); } int balance = height(root.left) - height(root.right); if(balance > 1) { if(height(root.left.left) >= height(root.left.right)) { root = rightRotation(root); } else { root.left = leftRotation(root.left); root = rightRotation(root); } } else if(balance < -1) { if(height(root.right.right) >= height(root.right.left)) { root = leftRotation(root); } else { root.right = rightRotation(root.right); root = leftRotation(root); } } else { root.ht = setHeight(root); } return root; } private static Node rightRotation(Node root) { Node newRoot = root.left; root.left = newRoot.right; newRoot.right = root; root.ht = setHeight(root); newRoot.ht = setHeight(newRoot); return newRoot; } private static Node leftRotation(Node root) { Node newRoot = root.right; root.right = newRoot.left; newRoot.left = root; root.ht = setHeight(root); newRoot.ht = setHeight(newRoot); return newRoot; } private static int height(Node root) { if(root == null) return -1; else return root.ht; } private static int setHeight(Node root) { if(root == null) { return -1; } else { return 1 + Math.max(height(root.left), height(root.right)); } }
+ 0 comments Why is there no Python editor for this problem ???????
+ 0 comments This challenge took me more than 2 days... unbelievable. I was trying to use recursion but I didn't have the option to write another function. 2 days later, I finally realize how to use the balance factor to determine how to rotate. I think my method is a little strange, but I am glad it works. I spend 4 hours debugging case 10 because I could not draw out the tree and had to keep guessing what was wrong with it. My problem with case 10 was, I did not properly update my height after rotating, resulting in my tree having 2 balance factor that was -2 and 2. After the first balance, the 2nd one should become 1 depth lower. Tips: definitely rotate base on balance factor. This method is very efficient in my opinion. 1 or 2 rotation and the insertion becomes perfectly balanced. The example tells you exactly how to rotate it Check for balanced insertion.
Sort 162 Discussions, By:
Please Login in order to post a comment