#DataStructure#CS251#Computer-Science Search Trees are a subset of Tree’s used in, well, searching. We use them to store items and to find them quickly.
Binary Search Tree
A binary search tree is made using a Binary Tree. That means each node has two children, and only two children. In a binary search tree (often abbreviated BST), every left child node is less than it’s parent and every right child node is greater than it’s parent. This is true of all of a nodes descendants, not just its immediate children.
If we insert numbers in order, for example, 1, 2, 3, 4, 5, 6, 7, 8, then we will end up with a tree that’s really just made up of one branch. Having a binary search tree like this is basically equivalent to having a Linked List. Everything will be O(n), which isn’t what we’re going for. The ideal situation is instead to have a Balanced Search Tree somehow. This would keep the height logarithmic.