C++基础之红黑树

 二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种二叉树，具有以下性质：

1. 左子树节点值小于根节点值：对于树中的每个节点 x，其左子树中所有节点的值都小于 x 的值。
2. 右子树节点值大于根节点值：对于树中的每个节点 x，其右子树中所有节点的值都大于 x 的值。
3. 子树也是二叉搜索树：每个子树也是二叉搜索树。

红黑树（Red-Black Tree）是一种自平衡的，它在插入和删除节点时通过特定的规则来保持树的平衡，从而保证了基本的查找、插入和删除操作的时间复杂度都是 O(log⁡n)O(\log n)O(logn)。

特性概述：

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点性质：根节点是黑色的。
3. 叶子节点性质：叶子节点（NIL节点，空节点）是黑色的。
4. 红色节点性质：红色节点的子节点必须是黑色的（即不存在两个连续的红色节点）。
5. 任意节点到其每个叶子的路径包含相同数量的黑色节点：这个特性保证了树的黑色高度是相同的，也就是树的平衡性。

红黑树的操作：

1. 插入操作：

   • 新节点插入时，首先按照二叉搜索树的方式找到插入位置，并将节点标记为红色。
   • 根据红黑树性质，需要进行颜色调整和旋转操作，以确保满足红黑树的所有性质。

2. 删除操作：

   • 删除节点后，为了保持红黑树的性质，可能需要进行颜色调整和旋转操作。

红黑树的应用：

红黑树常被用作基础数据结构，例如在C++的STL中，std::map 和 std::set 往往会基于红黑树实现，因为它能够高效支持插入、删除和查找操作，并且提供了有序性。