balanced tree
A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
In more detail
Self-balancing trees such as AVL trees, red-black trees and B-trees restore balance automatically after every insert or delete. Python's standard library has no balanced binary search tree; sorted lists with bisect or third-party packages fill the gap.
Related terms
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
- B-tree — A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.
- 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.
- 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
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- 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
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers