在二叉搜索树的讨论中可以得出各种查询以及插入、删除操作的时间复杂度上界为$O(h)$，其中$h$为树的高度，即树的叶子节点的最大深度。
因此树的高度很大程度上决定了动态集合操作的时间复杂度。对于一个包含确定数量元素的二叉搜索树，我们希望得到一棵较为“平衡”的二叉树，即后代结点能够较均匀分布在一个祖先结点的两颗子树中，这样相对于元素总量，其高度是一个较小的值。因此，可以将平衡的度量认为是树高h与结点总量n的比率$\frac{h}{n}$，即结点对树高的平均贡献率。
考察树的第i层的$k_i$个结点，有：
$$ n = \sum\limits_{i=0}^h k_i, \space k_i \leq 2^i $$
如果树中有大量不平衡的结点，那么每个第i层的结点越少，会导致树高$h$越大。
红黑树及其性质
红黑树是平衡二叉搜索树的一种，可以保证最坏情况下动态集合操作的时间复杂度为$O(\lg n)$，它在每个结点上增加一个存储位来表示结点颜色，可以是RED或BLACK，通过对任一条从根到叶子结点的路径上各个结点的颜色进行约束，可以确保没有一条路径会比其它路径长出2倍，因而是近似于平衡的。
一棵红黑树中的每个结点包含5个属性，color，key，left，right和p，如果一个结点没有子结点或父结点，这改结点相应指针属性的值为NIL，可以把这些NIL视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。
一棵红黑树是满足下面红黑性质的二叉搜索树：
- 每个结点是红色的或黑色的
- 根结点是黑色的
- 每个叶结点（NIL）是黑色的
- 如果一个结点是红色的，则它的两个子结点都是黑色的
- 对每个结点，从该结点到所有后代叶结点的简单路径上，均包含相同数目的黑色结点
从某个结点x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black height)，定义红黑树的黑高为其根结点的黑高。
红黑树动态集合操作
对不修改树的数据结构的操作，如遍历、查询、最大、最小、前驱、后继一类操作对红黑树和普通二叉搜索树都是一样的，对于插入与删除操作，红黑树需要进行额外的变换，不仅改变数据结构，也需要改变结点的颜色以保证红黑树的性质。
旋转
对于数据结构的修改，可以通过旋转来完成，它是能保持二叉搜索树的性质的局部操作。主要有两种旋转方式，分别为左旋和右旋。
插入
首先采用稍作修改的普通二叉搜索树插入方法将新的结点插入到树中，为了保证红黑树的性质，还需要对结点进行着色和旋转操作。
删除
首先采用进行了一定修改的普通的二叉搜索树删除方法将给定结点z从树T中删除，其中需要维持一个结点y为从树中删除的结点或移至树内的结点，并记录y的初始颜色，如果y的初始颜色为黑色，那么需要进行着色和旋转操作来恢复红黑性质。此外还要跟踪移动到结点y原来位置的x结点，因为它也有可能破坏红黑树性质。