Binärer Suchbaum (EN)

Binärer Suchbaum

A binary search tree is a hierarchical data structure in which each node has up to two successors and satisfies the property that all elements in the left subtree are smaller and all in the right subtree are larger than the root element. This structure enables efficient search, insertion, and deletion operations with an average time complexity of O(log n). In the worst case, when the tree degenerates into a list, the complexity drops to O(n). Binary search trees form the basis for many advanced data structures such as AVL trees and Red-Black trees.

Struktur

flowchart TD     A[Wurzel] --> B[Linker Teilbaum]     A --> C[Rechter Teilbaum]     B --> D[Knoten < Wurzel]     C --> E[Knoten > Wurzel]     D --> F[Linker Teilbaum]     D --> G[Rechter Teilbaum]     E --> H[Linker Teilbaum]     E --> I[Rechter Teilbaum] 

Im Kontext

• Typically used together with database indexes and search algorithms
• Related to: AVL trees, Red-Black trees, B-trees, Heap
• Example use: Implementation of dictionary structures in programming languages