Binary Search Trees(BSTs)

A Problem with arrays is adding and deleting elements to an arrays is computationally expensive, particularly when the array needs to stay sorted. BSTs are similar to arrays in that the keys are in a sorted order but they are easier to perform insertions and deletions into. But BSTs require more space than arrays.
The key lookup, insert, and delete operations for BSTs take time proprotional to the height of the tree, which can in worst case be O(n), if inserts and deletes are naively implemented. However there are implementations of insert and delete which gurantee the tree has height O(logn). These requires sorting and updating additional data at the tree nodes. Red-black trees are an example of such balanced BSTs and they are used in the C++ STL library to implement sets.

BSTs are different from trees. Specifically, in a BST, there is positionality as well as order associated with the children of nodes. Furthermore, the values stored at nodes have to respect the BST property - key stored at a node is greater than or equal to the keys stored in the nodes of its left subchild and less than or equal to the values stored in the nodes of its right subchild.

Below is video lecture related to red-black tree.