红黑树深入剖析及 Java 实现

概述

红黑树（Red Black Tree）是一种自平衡二叉查找树，是计算机科学中常用的一种数据结构，典型用途是实现关联数组。它于 1972 年由 Rudolf Bayer 发明，当时被称为平衡二叉 B 树（symmetric binary B-trees）。红黑树和 AVL 树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

二叉查找树（BST）

二叉查找树（Binary Search Tree，简称 BST）是一棵二叉树，其左子节点的值比父节点小，右子节点的值比父节点大。它的高度决定了查找效率。 在理想情况下，二叉查找树增删查改的时间复杂度为 O(logN)（其中 N 为节点数），最坏的情况下为 O(N)。当它的高度为 logN+1 时，我们就说二叉查找树是平衡的。 常见的 BST: