概述
红黑树(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:

