degenerate tree
A search tree in which every node has only one child, so it is really a linked list with height n minus one.
In more detail
Inserting already sorted keys into a plain binary search tree produces one, and every operation becomes O(n). Shuffling the input or using a self-balancing tree avoids it.
Related terms
- binary search tree — A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
- balanced tree — A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
- height — The number of edges on the longest path from a tree's root down to a leaf; a node's depth is its number of edges from the root.
Taught in
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers