Explanation
- A **Crit-bit Tree** is a binary search tree used for storing strings, especially strings of arbitrary length, in a compressed form.
-
- The **Crit-bit** refers to the bit position in the common prefix of two strings where they differ. The tree is a form of **binary trie** with a compressed path.
-
- The tree is used to efficiently handle string searches and updates, with each node storing a single bit representing the largest common prefix bit difference between the two strings.
-
-
Steps:
- Insertion: When inserting, the tree finds the position where the strings differ and creates a new node at the “crit-bit” position.
- Search: Searching in a Crit-bit Tree works by following the path based on the crit-bit values (common prefix bit position) and comparing the strings.
-
Time Complexity:
- Insertion: O(k), where k is the length of the string.
- Search: O(k), where k is the length of the string.