Tag: data-structures
-
Overview A Trie (derived from “retrieval”), also known as a prefix tree, is a specialized tree-based data structure used to store a dynamic set of strings. Unlike a binary search tree, no node in the trie stores the key associated with that node; instead, its position in the tree defines the key it is associated…
-
Overview A Heap is a specialized tree-based data structure that satisfies the heap property. It is most commonly implemented as a binary heap, which is a complete binary tree. Heaps are primarily used to implement priority queues and the heapsort algorithm. Core Concepts Heap Property: Max-Heap: The value of the root node must be the…
-
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:…