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.
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}\) |
Bibliography
“Binary Search Tree.” 2022. Wikipedia, July. https://en.wikipedia.org/w/index.php?title=Binary_search_tree&oldid=1099579299.