Binärt sökträd
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
In the Vinony graph
Vinony's link graph records 213 inbound references to Binärt sökträd, and connects out to tree, tree traversal and B-tree.
It is catalogued under topics including Binary trees and Search trees.
Vinony links it to 37 Wikipedia language editions.
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 · Svenska
Ett binärt sökträd är ett binärträd (dvs varje nod har högst två barn) med följande egenskaper: * varje nod har ett värde. * det högra delträdet till en nod innehåller bara värden som är högre än värdet i noden. * det vänstra delträdet till en nod innehåller bara värden som är lägre än värdet i noden. Binära sökträd är användbara eftersom det finns effektiva sökalgoritmer som kan användas på dem. I genomsnitt är algoritmen av ordning Θ(log n) och i värsta fall Θ(n).
Abstract from DBpedia / Wikipedia · CC BY-SA