Content deleted Content added
Citation bot (talk | contribs) Alter: title. | Use this bot. Report bugs. | #UCB_CommandLine 82/9214 |
No edit summary Tags: Reverted Mobile edit Mobile web edit |
||
Line 17:
[[File:Binary search tree.svg|right|upright=0.8|thumb|Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn.]]
In [[computer science]], a '''binary search tree''' ('''BST'''; 이진 탐색 트리), also called an '''ordered''' or '''sorted binary tree''', is a [[Rooted tree|rooted]] [[binary tree]] [[data structure]] with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The [[time complexity]] of operations on the binary search tree is [[directly proportional]] to the height of the tree.
Binary search trees allow [[Binary search algorithm|binary search]] for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of [[binary logarithm]]. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to [[Conway Berners-Lee]] and [[David_Wheeler_(computer_scientist)|David Wheeler]].
| |||