A BST (Binary Search Tree) is a binary search tree where each node has at most two children, and for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This allows efficient search, insertion, and removal operations.
Remember: A binary tree is, by definition, a set of nodes that is either empty or consists of a root and two disjoint binary subtrees, called the left and right subtrees of the root.
The main properties of a BST tree include: the ordering of elements, efficiency in search, insertion, and removal operations (on average O(log n)), and the hierarchical structure that facilitates data organization. However, performance can degrade to O(n) in cases of degenerate trees, trees where nodes all fall to one side.
Searching in a BST tree starts at the root and traverses the tree by comparing the searched value with the current node's value, moving left or right as needed. The algorithm is very simple and efficient, being O(log n) on average.
Inserting a new value in the BST tree follows a process similar to searching, locating the correct position for the new node and always inserting it as a leaf.
Removing a node in a BST tree can be more complex, depending on the number of children the node to be removed has. Nodes without children can be removed directly, nodes with one child can be replaced by their child, and nodes with two children require replacement by the in-order successor or predecessor.