红黑树，即R-B Tree，本文的主要内容包括：红黑树的特性、红黑树的时间复杂度和它的证明，红黑树的时间复杂度和它的证明，红黑树的左旋、右旋、插入、删除等操作

之前讨论了机器学习中的偏差-方差权衡。机器学习里的损失函数（代价函数）可以用来描述模型与真模型（ground truth）之间的差距，因此可以解决“偏差”的问题。但是仅有损失函数，我们无法解决方差的问题，因而会有过拟合风险。

本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

具体讲解之前，有一点，再次强调下：B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。特此说明。

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为$log_2n$，其各操作的时间复杂度$O(log_2n)$同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。于是就有了我们下边介绍的平衡二叉树。

一、定义

二叉排序树（Binary Sort Tree）又称为二叉查找树（Binary Search Tree）、二叉搜索树。它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的$key$值记为$key[x]$。如果y是x的左子树中的一个结点，则$key[y]<= key[x]$；如果y是x的右子树的一个结点，则$key[y] >= key[x]$。那么，这棵树就是二叉查找树。

数据结构中有很多树的结构，这里整理了二叉树、二叉查找树、AVL树、红黑树、B树、B+树、trie树的基本概念与操作。

一、栈

1.1 栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶（top），另一端称为栈底，不含任何数据元素的栈称为空栈。它有以下几个特点：

线性表是一种线性结构，它是具有相同类型的n个数据元素组成的优先序列。介绍线性表的几个基本组成部分：数组、单向链表、双向链表。

“An outlier is an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism.” — D. M. Hawkins, Identification of Outliers, Chapman and Hall, 1980.