Revision as of 23:01, 16 August 2023 edit 2001:2d8:e143:cfb2::6f0:d0a0 (talk) No edit summary Tags: Reverted Mobile edit Mobile web edit ← Previous edit		Revision as of 23:02, 16 August 2023 edit undo Always forever (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 5,372 edits Undid revision 1170742233 by 2001:2D8:E143:CFB2:0:0:6F0:D0A0 (talk): unnecessary non-english inclusion (text appears to just mean "binary search tree" in Korean) Tag: Undo Next 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]].

Binary search tree: Difference between revisions