What is the difference between a binary search tree and a red-black tree in data structures?

A Binary Search Tree (BST) is a data structure where 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. BSTs are simple but do not guarantee balance, which can cause search, insertion, and deletion operations to degrade to O(n) in the worst case (e.g., in a degenerate tree).

A Red-Black Tree is a type of self-balancing binary search tree. It maintains balance using color labels (red or black) on nodes and rules that limit the height of the tree. As a result, search, insertion, and deletion operations are guaranteed to run in O(log n).

Summary:

• BST — a simple structure without balance guarantees.
• Red-Black Tree — a balanced BST with additional rules and node colors to maintain logarithmic height.