A self-balancing binary search tree (BST) is a type of binary search tree that automatically keeps its height balanced in order to guarantee that operations such as searching, inserting, and deleting elements in the tree take less time on average.
How do self-balancing BSTs maintain height balance?
Self-balancing binary search trees (BSTs) maintain height balance by automatically reorganising the tree after every insertion or deletion operation. To balance a BST, we can use two common operations: right rotation and left rotation. These operations adjust the positions of nodes in the tree to ensure that the tree remains balanced.
Right Rotation: Right rotation is used to balance a tree when its left subtree is longer than its right subtree.
In a right rotation, we move the left child of the unbalanced node to the position of the unbalanced node, while making the unbalanced node the right child of its former left child.
For example, let’s say we have a tree where node B is the root, and its left child A is taller than its right child C. In this case, we can perform a right rotation on node B as follows:
Example of right rotation
Left Rotation: Left rotation is used to balance a tree when its right subtree is longer than its left subtree.
In a left rotation, we move the right child of the unbalanced node to the position of the unbalanced node, while making the unbalanced node the left child of its former right child.
For example, let’s say we have a tree where node B is the root, and its right child C is taller than its left child A. In this case, we can perform a left rotation on node B as follows:
Example of left rotation
Some examples of self-balancing BST:
Some examples of self-balancing BSTs are:
Below we will check their implementation in Javascript language.
Implementation of AVL Tree in Javascript:
This implementation includes methods for inserting, searching, and deleting nodes from the AVL tree.
- The `height` method calculates the height of a given node, and
- the `balanceFactor` method calculates the difference in height between the left and right subtrees of a given node.
- The `rotateRight` and `rotateLeft` methods perform right and left rotations, respectively, to balance the tree.
- The `insertNode` method inserts a new node into the tree, and
- The `deleteNode` method removes a node from the tree.
- The `findMinNode` method finds the minimum node in a given subtree,
- The `searchNode` method searches for a node with a given value in the tree.
Below is the implementation of AVL Tree in Javascript.
Javascript
class Node { constructor(value) { this.value = value; this.left = null; this.right = null; this.height = 1; } } class AVLTree { constructor() { this.root = null; } // get the height of a node height(node) { if (!node) return 0; return node.height; } // get the balance factor of a node balanceFactor(node) { if (!node) return 0; return this.height(node.left) - this.height(node.right); } // perform a right rotation rotateRight(node) { const leftNode = node.left; const rightOfLeftNode = leftNode.right; leftNode.right = node; node.left = rightOfLeftNode; node.height = Math.max(this.height(node.left), this.height(node.right)) + 1; leftNode.height = Math.max(this.height(leftNode.left), this.height(leftNode.right)) + 1; return leftNode; } // perform a left rotation rotateLeft(node) { const rightNode = node.right; const leftOfRightNode = rightNode.left; rightNode.left = node; node.right = leftOfRightNode; node.height = Math.max(this.height(node.left), this.height(node.right)) + 1; rightNode.height = Math.max(this.height(rightNode.left), this.height(rightNode.right)) + 1; return rightNode; } // insert a new node insert(value) { this.root = this.insertNode(this.root, value); } insertNode(node, value) { if (!node) { return new Node(value); } if (value < node.value) { node.left = this.insertNode(node.left, value); } else if (value > node.value) { node.right = this.insertNode(node.right, value); } else { return node; // duplicate values are not allowed } node.height = Math.max(this.height(node.left), this.height(node.right)) + 1; const balance = this.balanceFactor(node); if (balance > 1 && value < node.left.value) { return this.rotateRight(node); } if (balance > 1 && value > node.left.value) { node.left = this.rotateLeft(node.left); return this.rotateRight(node); } if (balance < -1 && value > node.right.value) { return this.rotateLeft(node); } if (balance < -1 && value < node.right.value) { node.right = this.rotateRight(node.right); return this.rotateLeft(node); } return node; } // search for a node search(value) { return this.searchNode(this.root, value); } searchNode(node, value) { if (!node) return null; if (value < node.value) { return this.searchNode(node.left, value); } else if (value > node.value) { return this.searchNode(node.right, value); } else { return node; } } // delete a node delete(value) { this.root = this.deleteNode(this.root, value); } deleteNode(node, value) { if (!node) { return null; } if (value < node.value) { node.left = this.deleteNode(node.left, value); } else if (value > node.value) { node.right = this.deleteNode(node.right, value); } else { // node to be deleted has no children if (!node.left && !node.right) { node = null; } // node to be deleted has one child else if (!node.left) { node = node.right; } else if (!node.right) { node = node.left; } // node to be deleted has two children else { const minNode = this.findMinNode(node.right); node.value = minNode.value; node.right = this.deleteNode(node.right, minNode.value); } } if (!node) return null; node.height = Math.max(this.height(node.left), this.height(node.right)) + 1; const balance = this.balanceFactor(node); if (balance > 1 && this.balanceFactor(node.left) >= 0) { return this.rotateRight(node); } if (balance > 1 && this.balanceFactor(node.left) < 0) { node.left = this.rotateLeft(node.left); return this.rotateRight(node); } if (balance < -1 && this.balanceFactor(node.right) <= 0) { return this.rotateLeft(node); } if (balance < -1 && this.balanceFactor(node.right) > 0) { node.right = this.rotateRight(node.right); return this.rotateLeft(node); } return node; } // find the minimum node in a subtree findMinNode(node) { while (node && node.left) { node = node.left; } return node; } } // example usage const tree = new AVLTree(); tree.insert(4); tree.insert(2); tree.insert(7); tree.insert(1); tree.insert(3); tree.insert(5); tree.insert(8); tree.insert(6); console.log(tree.search(5)); tree.delete(7); console.log(tree.search(7)); |
Output:
Output of the above code
Implementation of Red-Black Tree in Javascript:
- The `insert()` method first inserts a new node using the `insertNode()` method (which is the same as in a regular binary search tree).
- Ihe `fixupInsert()` method fix any violations of the red-black properties that may have been introduced by the insertion.
- The `fixupInsert()` method checks three cases to determine how to fix the violation. In each case, it performs a rotation (either left or right) to re-balance the tree.
- The `rotateLeft()` and `rotateRight()` methods perform the actual rotations, and
- The `search()` method searches for a value in the tree.
- Finally, the `inOrderTraversal()` method traverses the tree in order and calls a callback function on each node.
Below is the implementation of Red-Black Tree.
Javascript
// Define the color constants const RED = "red"; const BLACK = "black"; class RBNode { constructor(value) { this.value = value; this.color = RED; this.left = null; this.right = null; this.parent = null; } isRed() { return this.color === RED; } } class RBTree { constructor() { this.root = null; } insert(value) { const node = new RBNode(value); // insert node like in a regular BST this.root = this.insertNode(this.root, node); // fix any violations of the red-black properties this.fixupInsert(node); } insertNode(root, node) { if (!root) { return node; } if (node.value < root.value) { root.left = this.insertNode(root.left, node); root.left.parent = root; } else { root.right = this.insertNode(root.right, node); root.right.parent = root; } return root; } fixupInsert(node) { while (node.parent && node.parent.isRed()) { if (node.parent === node.parent.parent.left) { const uncle = node.parent.parent.right; if (uncle && uncle.isRed()) { // case 1: uncle is red node.parent.color = BLACK; uncle.color = BLACK; node.parent.parent.color = RED; node = node.parent.parent; } else { if (node === node.parent.right) { // case 2: uncle is black and node is a right child node = node.parent; this.rotateLeft(node); } // case 3: uncle is black and node is a left child node.parent.color = BLACK; node.parent.parent.color = RED; this.rotateRight(node.parent.parent); } } else { const uncle = node.parent.parent.left; if (uncle && uncle.isRed()) { // case 1: uncle is red node.parent.color = BLACK; uncle.color = BLACK; node.parent.parent.color = RED; node = node.parent.parent; } else { if (node === node.parent.left) { // case 2: uncle is black and node is a left child node = node.parent; this.rotateRight(node); } // case 3: uncle is black and node is a right child node.parent.color = BLACK; node.parent.parent.color = RED; this.rotateLeft(node.parent.parent); } } } this.root.color = BLACK; } rotateLeft(node) { const right = node.right; node.right = right.left; if (right.left) { right.left.parent = node; } right.parent = node.parent; if (!node.parent) { this.root = right; } else if (node === node.parent.left) { node.parent.left = right; } else { node.parent.right = right; } right.left = node; node.parent = right; } rotateRight(node) { const left = node.left; node.left = left.right; if (left.right) { left.right.parent = node; } left.parent = node.parent; if (!node.parent) { this.root = left; } else if (node === node.parent.left) { node.parent.left = left; } else { node.parent.right = left; } left.right = node; node.parent = left; } // search for a value in the tree search(value) { let current = this.root; while (current) { if (value === current.value) { return current; } else if (value < current.value) { current = current.left; } else { current = current.right; } } return null; } // traverse the tree in order inOrderTraversal(callback) { this.inOrderTraversalNode(this.root, callback); } inOrderTraversalNode(node, callback) { if (node) { this.inOrderTraversalNode(node.left, callback); callback(node); this.inOrderTraversalNode(node.right, callback); } } } const tree = new RBTree(); tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(15); tree.insert(5); console.log("Inorder Traversal of the Red Black Tree: "); tree.inOrderTraversal((node) => console.log(node.value)); |
Output
Inorder Traversal of the Red Black Tree: 5 10 15 20 30
Implementation of Splay Tree in Javascript:
The splay tree is constructed in the same way as a binary search tree, but it is different in the way it is manipulated. Whenever an element is accessed, it is moved to the root of the tree by performing a series of rotations. This process is called splaying, and it helps to ensure that frequently accessed elements are located near the root of the tree, making them easier to access in future operations.
Here are the steps to implement a splay tree:
- Define a Node class to represent nodes in the tree. Each node should have a key, a value, a left child, and a right child.
- Define a SplayTree class to represent the tree itself. The tree should have a root property that points to the root node.
- Implement the basic operations of a binary search tree, such as insert, delete, and search. These operations should follow the standard algorithms for binary search trees, with the additional step of performing a splaying operation after the insertion, deletion, or search.
- Implement the splaying operation. The splaying operation should take a key as input and move the corresponding node to the root of the tree using a series of rotations. The rotations should be performed in a way that balances the tree and reduces its height.
Below is the implementation of the Splay Tree.
Javascript
class Node { constructor(key, value) { this.key = key; this.value = value; this.left = null; this.right = null; } } class SplayTree { constructor() { this.root = null; } splay(key) { if (this.root == null) { return; } let dummy = new Node(null, null); let left = dummy; let right = dummy; let current = this.root; while (true) { if (key < current.key) { if (current.left == null) { break; } if (key < current.left.key) { let temp = current.left; current.left = temp.right; temp.right = current; current = temp; if (current.left == null) { break; } } right.left = current; right = current; current = current.left; } else if (key > current.key) { if (current.right == null) { break; } if (key > current.right.key) { let temp = current.right; current.right = temp.left; temp.left = current; current = temp; if (current.right == null) { break; } } left.right = current; left = current; current = current.right; } else { break; } } left.right = current.left; right.left = current.right; current.left = dummy.right; current.right = dummy.left; this.root = current; } insert(key, value) { if (this.root == null) { this.root = new Node(key, value); return; } this.splay(key); if (key < this.root.key) { let node = new Node(key, value); node.left = this.root.left; node.right = this.root; this.root.left = null; this.root = node; } else if (key > this.root.key) { let node = new Node(key, value); node.right = this.root.right; node.left = this.root; this.root.right = null; this.root = node; } else { this.root.value = value; } } search(key) { if (this.root == null) { return null; } this.splay(key); if (this.root.key == key) { return this.root.value; } else { return null; } } delete(key) { if (this.root == null) { return; } this.splay(key); if (this.root.key != key) { return; } if (this.root.left == null) { this.root = this.root.right; } else { let right = this.root.right; this.root = this.root.left; this.splay(key); this.root.right = right; } } } const tree = new SplayTree(); // Insert some nodes tree.insert(10, 'A'); tree.insert(20, 'B'); tree.insert(30, 'C'); tree.insert(15, 'D'); tree.insert(25, 'E'); // Search for a node // Output: "B" console.log(tree.search(20)); // Delete a node tree.delete(15); // Search for a deleted node // Output: null console.log(tree.search(15)); |
Output:
Output of the above code
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
