How do binary search trees and red-black trees differ, and what are the features of each?

A Binary Search Tree (BST) is a data structure where each node has at most two children: the left contains values less than the current node, and the right contains values greater. BST allows for quick search, insertion, and deletion of elements, but if the insertion order is unfavorable, the tree can become unbalanced, which degrades performance to O(n).

A Red-Black Tree is a type of balanced binary search tree where each node is colored red or black, and certain rules are followed (for example, the root is always black, red nodes cannot be consecutive, etc.). These rules ensure the tree remains balanced, guaranteeing that the height of the tree is always O(log n).

Features:

• BSTs are simpler to implement but can degrade in performance.
• Red-Black Trees are more complex but provide guaranteed efficient search, insertion, and deletion operations.

Example in Java (simplified):

class Node {
    int key;
    Node left, right;
    boolean color; // true - red, false - black
    // Constructor and methods...
}
// In Red-Black Trees, balancing operations are maintained during insertion