WikiGalaxy
Balanced Binary Tree
Definition
A balanced binary tree is a type of binary tree in which the height of the left and right subtrees of any node differ by at most one. This ensures that the tree remains approximately balanced, preventing the worst-case time complexity of operations like insertions, deletions, and lookups from degrading.
Importance
Balanced binary trees, such as AVL trees and Red-Black trees, are crucial in maintaining efficient data structures. They ensure that operations can be performed in O(log n) time, making them suitable for applications requiring frequent insertions and deletions.
Example 1: AVL Tree
AVL trees maintain balance by performing rotations during insertions and deletions to ensure the height difference between subtrees remains within one.
class AVLTree {
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
}
Example 2: Red-Black Tree
Characteristics
Red-Black trees are a type of self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black. This helps maintain the balance of the tree.
class RedBlackTree {
private Node root;
private Node TNULL;
private void fixInsert(Node k) {
Node u;
while (k.parent.color == RED) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
if (u.color == RED) {
u.color = BLACK;
k.parent.color = BLACK;
k.parent.parent.color = RED;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
k.parent.color = BLACK;
k.parent.parent.color = RED;
leftRotate(k.parent.parent);
}
}
}
}
}
Example 3: Splay Tree
Concept
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs splay operations to move accessed elements closer to the root.
class SplayTree {
private Node root;
private void splay(Node n) {
while (n.parent != null) {
if (n.parent.parent == null) {
if (n == n.parent.left) {
rightRotate(n.parent);
} else {
leftRotate(n.parent);
}
} else if (n == n.parent.left && n.parent == n.parent.parent.left) {
rightRotate(n.parent.parent);
rightRotate(n.parent);
} else if (n == n.parent.right && n.parent == n.parent.parent.right) {
leftRotate(n.parent.parent);
leftRotate(n.parent);
}
}
}
}
Example 4: Treap
Definition
A treap is a binary search tree that maintains a heap property. Each node has a priority, and the tree is ordered both by the keys and the priorities. This structure ensures that the tree remains balanced probabilistically.
class Treap {
private Node root;
private Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
return x;
}
private Node rotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
return y;
}
}
Example 5: Scapegoat Tree
Overview
Scapegoat trees are binary search trees that use partial rebuilding to maintain balance. They do not require additional information in each node, unlike AVL or Red-Black trees, and are based on the concept of weight-balanced trees.
class ScapegoatTree {
private Node root;
private Node rebuild(Node node) {
List nodes = new ArrayList<>();
storeBSTNodes(node, nodes);
return buildTreeUtil(nodes, 0, nodes.size() - 1);
}
private void storeBSTNodes(Node root, List nodes) {
if (root == null)
return;
storeBSTNodes(root.left, nodes);
nodes.add(root);
storeBSTNodes(root.right, nodes);
}
private Node buildTreeUtil(List nodes, int start, int end) {
if (start > end)
return null;
int mid = (start + end) / 2;
Node node = nodes.get(mid);
node.left = buildTreeUtil(nodes, start, mid - 1);
node.right = buildTreeUtil(nodes, mid + 1, end);
return node;
}
}
