<aside> 💡
Height-Balanced
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than on
</aside>
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class BST {
TreeNode root;
void insert(int val) {
root = insert(root, val);
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) return new TreeNode(val);
if (val < node.val) node.left = insert(node.left, val);
else node.right = insert(node.right, val);
return node;
}
boolean search(int val) {
return search(root, val);
}
private boolean search(TreeNode node, int val) {
if (node == null) return false;
if (val == node.val) return true;
return val < node.val ? search(node.left, val) : search(node.right, val);
}
}
class AVLNode {
int val, height;
AVLNode left, right;
AVLNode(int val) { this.val = val; height = 1; }
}
class AVLTree {
AVLNode root;
int height(AVLNode n) {
return n == null ? 0 : n.height;
}
int getBalance(AVLNode n) {
return n == null ? 0 : height(n.left) - height(n.right);
}
AVLNode rotateRight(AVLNode y) {
AVLNode x = y.left;
AVLNode T = x.right;
x.right = y;
y.left = T;
y.height = 1 + Math.max(height(y.left), height(y.right));
x.height = 1 + Math.max(height(x.left), height(x.right));
return x;
}
AVLNode rotateLeft(AVLNode x) {
AVLNode y = x.right;
AVLNode T = y.left;
y.left = x;
x.right = T;
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right));
return y;
}
AVLNode insert(AVLNode node, int val) {
if (node == null) return new AVLNode(val);
if (val < node.val) node.left = insert(node.left, val);
else if (val > node.val) node.right = insert(node.right, val);
else return node;
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
// 4 Rotations
if (balance > 1 && val < node.left.val) return rotateRight(node);
if (balance < -1 && val > node.right.val) return rotateLeft(node);
if (balance > 1 && val > node.left.val) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balance < -1 && val < node.right.val) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
}
📌 Use TreeMap / TreeSet in Java — internally implemented as Red-Black Tree.
TreeMap<Integer, String> map = new TreeMap<>();
TreeSet<Integer> set = new TreeSet<>();