binaire zoekboom
Sign in to saveAlso known as BST, ordered binary tree, sorted binary tree
data structure in tree form with 0, 1, or 2 children per node, sorted for fast lookup
Key facts
- Type
- tree
- Invented by
- P.F. Windley, A.D. Booth , A.J.T. Colin , and T.N. Hibbard
- Operation
- Average
- Search
- Θ(log n )
- Insert
- Θ(log n )
- Delete
- Θ(log n )
- Space
- Θ( n )
via Wikipedia infobox
Wikidata facts
- Instance of
- data structure
- Subclass of
- binary tree
- Image
- Binary search tree.svg
Show 6 more facts
- Commons category
- Binary search trees
- time of discovery or invention
- 1960-00-00
- discoverer or inventor
- Andrew Donald Booth
- inception
- 1960-01-01
- Stack Exchange tag
- stackoverflow.com/tags/binary-search-tree
- studied by
- algorithmics
Sources (3)
via Wikidata · CC0
Article · Nederlands
Een binaire zoekboom is een binaire boom met eigenschappen die ervoor zorgen dat een waarde snel gevonden kan worden. In een binaire zoekboom verwijst elke knoop naar maximaal twee andere knopen. Verder heeft elke knoop in de boom de eigenschap dat alle waarden in de linker subboom kleiner of gelijk zijn dan de waarde in de knoop en alle waarden in de rechtersubboom groter of gelijk dan de waarde in de knoop. Om efficiënt te kunnen zoeken dient de boom ook gebalanceerd te zijn; dit wil zeggen dat de subbomen van een knoop zo veel mogelijk even diep zijn. Bij een scheefgegroeide boom (niet gebalanceerde boom) is de tijdwinst voor bewerkingen kleiner dan een gebalanceerde boom aangezien er (veel) meer waarden in knopen bekeken moet worden om te weten of een waarde in de boom te vinden is.
Abstract from DBpedia / Wikipedia · CC BY-SA