Tag: trees
-
Overview A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key. Core Concepts Root: The topmost node of…
-
Overview AVL and Red-Black trees are Self-Balancing Binary Search Trees (BSTs). In a standard BST, if elements are inserted in sorted order, the tree becomes a linked list (degenerate), leading to $O(n)$ search time. Self-balancing trees ensure the height remains $O(\log n)$ by rotating nodes during insertion and deletion. Core Concepts AVL Trees: Strict Balancing:…