In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a 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 Tree” 2022)

Complexity

Worst-case Best-case
Space \(\bigo{n}\) \(\bigo{n}\)
Search \(\bigo{\log n}\) \(\bigo{n}\)
Insert \(\bigo{\log n}\) \(\bigo{n}\)
Delete \(\bigo{\log n}\) \(\bigo{n}\)

:ANKI_NOTE_TYPE: Cloze with Source

References

“Binary Search Tree.” 2022. Wikipedia, July. https://en.wikipedia.org/w/index.php?title=Binary_search_tree&oldid=1099579299.