正文
从二叉搜索树到AVL树再到红黑树 B树
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
这几种树都属于数据结构中较为复杂的，在平时面试中，经常会问理解用法，但一般不会问具体的实现，所以今天来梳理一下这几种树之间的区别与联系，感谢知乎用户@Cailiang，这篇文章参考了他的专栏。
二叉查找树
是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
插入数据：
1 如果根节点为空，则将插入的节点作为根节点
2 否则和根节点比较（我们是通过key来比较，所以 K 必须是实现了Comparable接口的对象）如果比根节点小，则新节点会插入到左子树中，如果比根节点大，则新节点会插入到右子树中，如果和根节点相等，则更新根节点的值
通过key查询：
1 如果根节点为空，返回 null
2 如果，key 和根节点的key相同，则返回根节点
3 如果，key比根节点的key小，则递归查找根节点的左节点
4 如果，key比根节点的key大，则递归查找根节点的右节点
删除节点：
1 将要删除的节点没有子节点 ----> 直接删除
2 将要删除的节点下有一个子节点 -----> 将要被删除的节点的子节点挂靠到将要被删除的节点的父节点上即可
3 将要删除的节点下有两个子节点 ----> 在将要被删除的节点的右子树中找到一个最小节点，然后用找到的最小节点与需要删除的节点替换。最后再将最小节点进行删除。（这里你可能有其它的方案，我们这里这么做的原因是一，右子树的最小节点一定没有左节点，处理起来会简单一些，二，这样可以保持树的高度不变，甚至是降低树的高度，树的高度越低意味着操作的时间复杂度越低。所以实现删除一个节点的原则是，用最小的代价实现删除的功能，并且保持树的高度不变甚至降低树的高度）
搜索二叉树的增删改查的性能都不错，但是在一些特殊情况下， 搜索二叉树的性能可能由对数型变成线性 ，性能大大降低，比如插入的一组数据是有序的，那么二叉搜索树的结构将变成一个链表时间复杂度变为 O(N)，也就是说插入一组有序或局部有序的数据将会导致二叉搜索树不平衡，树的高度会很大，时间复杂度会趋近于 O(N)。
为了解决这个问题，引出了平衡二叉树(AVL)。
平衡二叉树，首先是一棵二叉查找树 ，但是它满足一点重要的特性：每一个结点的左子树和右子树的高度差最多为1。这个高度差限制就完全规避了上述的最坏情况，因此查找、插入和删除的时间复杂度都变成了O(lg n)。
AVL树虽然是一个完美平衡的二叉排序树，并且保证插入，删除，查找的时间复杂度为 lg n, 但是AVL树的应用却不广泛，原因就是 维护一颗AVL树操作太复杂，成本太高 。当我们对一颗AVL树进行插入或删除的操作时，我们需要不断的回朔来修改平衡因子（左子树的高度减去右字树的高度），需要通过左旋转，右旋转来保证每个节点的左右子树的高度差不超过1。这些复杂的操作甚至抵消了AVL树给我们带来的性能上的提升，所以我们一般不会使用AVL树。
红黑树
吸取了AVL树和2-3树的思想，但放弃了AVL树完美平衡的特性，改为局部平衡或完美黑色平衡；放弃了2-3树3节点，改为通过颜色（红色和黑色）来区分不同的节点类型，这样就降低了维护平衡的成本和实现的复杂度，可以直接使用二叉排序树的查询方法来查询无需任何修改。
恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。插入和删除为 O(log n) 次，但是这导致了非常复杂的操作。
红黑树的性质：
1 所有节点都是红色或者黑色
2 根节点为黑色
3 所有的 NULL 叶子节点都是黑色
4 如果该节点是红色的，那么该节点的子节点一定都是黑色
5 所有的 NULL 节点到根节点的路径上的黑色节点数量一定是相同的
B-Tree
前面介绍了AVL树，红黑树，它们都属于二叉树，即每个节点最多只能拥有2个子节点，而B-tree（B树）的每个节点可以拥有2个以上的子节点，所以简单概括一下：B-tree就是一颗多路平衡查找树，它广泛应用于数据库索引和文件系统中。
首先我们介绍下 m 阶B-tree的特性，那么这个 m 阶是怎么定义的呢？这里我们以一个节点能拥有的最大子节点数来表示这颗树的阶数。举个例子，如果一个节点最多有 n 个key，那么这个节点最多就会有 n+1 个子节点，这棵树就叫做 n+1（m=n+1）阶树。一颗 m 阶B-tree包括以下5条特性：
1 每个节点最多有 m 个子节点
2 除根节点和叶子节点，其它每个节点至少有 [m/2] （向上取整的意思）个子节点
3 若根节点不是叶子节点，则其至少有2个子节点
4 所有NULL节点到根节点的高度都一样
5 除根节点外，其它节点都包含 n 个key，其中 [m/2] -1 <= n <= m-1
B+ Tree是B Tree的一个变种，不同之处在于：
第一：在 B-Tree中一个含有n个子树的节点有n-1个关键字(key)。而在 B+Tree中一个含有n个子树的节点有n个关键字(key)。
为什么在拥有同样子树的情况下B+Tree的节点多需要一个key呢？那是因为 B+Tree的节点会存储该节点的子树中最小的key。
第二：B-Tree的每个节点都包含了关键字(key)以及指向包含这些关键字记录的指针。而 B+Tree非叶子节点仅用来索引，数据都保存在叶子节点中。
在叶子节点中存储了所有的关键字信息，以及指向包含这些关键字记录的指针。而且这些叶子节点构成一个有序链表，即每个叶子节点会有一个指针指向其兄弟节点。在非叶子节点中只存储了关键字信息。
下面这张图画的非常好：
在数据库索引的实现中，大部分采用的是B+Tree而不是B-Tree，这又是为什么呢？
原因有二，其一是由于B+Tree 在非叶子节点中只存储了关键字信息，而没有存储指向包含这些关键字记录的指针，所以在树的高度相同时，B+Tree往往能比B-Tree存储更多的关键字信息。更最要的原因是因为 B+Tree在叶子节点中存储了所有的关键字信息，以及指向包含这些关键字记录的指针。而且这些叶子节点构成一个有序链表，这样B+Tree在实现范围查询的时候就比较容易，只需要遍历这个有序链表就行。而B-tree要实现范围查询则比较困难，但范围查询又是数据库中比较常用的功能，所以数据库中大部分采用的是B+Tree而不是B-Tree。当然B-Tree也有强于B+tree的地方，例如在随机查询中，由于B-Tree的每个节点都包含了关键字(key)以及指向包含这些关键字记录的指针，所以B-Tree可能中途就查询到需要的数据，不需要遍历到叶子节点。而B+Tree由于只在叶子节点中存储了所有的关键字信息，以及指向包含这些关键字记录的指针。在非叶子节点中只存储了关键字信息，没有存储指向包含这些关键字记录的指针，所以B+Tree一定要遍历到叶子节点才能获取到包含这些关键字记录的指针。所以B-Tree的随机查询性能会高于B+Tree。
在B+树的基础上又演变出B*树，B*Tree在非叶子结点中也增加了指向兄弟节点的指针，并且它将非叶子节点上存储的关键字个数的最小值提高到 (2/3) * m，这样的话就提高了空间利用率。
public class BinarySerachTree<K extends Comparable<K>, V> {
private class Node {
private K key; // 存储的key
private V value; // 存储的值
private Node leftNode; // 左节点
private Node rightNode; // 右节点
public Node(K key, V value, Node leftNode, Node rightNode) {
super();
this.key = key;
this.value = value;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
@Override
public String toString() {
return "{\"key\":" + this.key + ", \"value\":" + "\"" + this.value + "\"" + ", \"leftNode\":"
+ this.leftNode + ", \"rightNode\":" + this.rightNode + "}";
}
}
private Node root; // 根节点
public void put(K key, V value) {
Node newNode = new Node(key, value, null, null);
if (null == root) {
root = newNode;
} else {
upsert(null, root, newNode);
}
}
private void upsert(Node parent, Node current, Node newNode) {
if (null == current) {
if (newNode.key.compareTo(parent.key) > 0) {
parent.rightNode = newNode;
} else {
parent.leftNode = newNode;
}
} else {
int result = newNode.key.compareTo(current.key);
if (result == 0) {
current.value = newNode.value;
}
parent = current;
if (result > 0) {
upsert(parent, parent.rightNode, newNode);
}
if (result < 0) {
upsert(parent, parent.leftNode, newNode);
}
}
}
public Node get(K key) {
if (null != key) {
return find(key, root); // 从根节点开始找
}
return null;
}
private Node find(K key, Node root) {
if (null != root) {
int result = key.compareTo(root.key);
if (result == 0) {
return root;
}
if (result > 0) {
return find(key, root.rightNode);
}
if (result < 0) {
return find(key, root.leftNode);
}
}
return null;
}
public boolean delete(K key) {
if (null != key) {
if (null != root) {
return deleteNode(key, root, null);
}
}
return false;
}
private boolean deleteNode(K key, Node current, Node parent) {
if (null != current) {
if (key.compareTo(current.key) > 0) {
return deleteNode(key, current.rightNode, current);
}
if (key.compareTo(current.key) < 0) {
return deleteNode(key, current.leftNode, current);
}
if (key.compareTo(current.key) == 0) {
if ((null != current.leftNode) && (null != current.rightNode)) { // 将要删除的节点下有两个子节点
dleTwoChildrenNode(current);
return true;
} else {
if ((null == current.leftNode) && (null == current.rightNode)) { // 将要删除的节点没有子节点
if (current.key.compareTo(parent.key) > 0) {
parent.rightNode = null;
} else {
parent.leftNode = null;
}
return true;
} else { // 将要被删除的节点的子节点挂靠到将要被删除的节点的父节点上即可
Node childNode = (null == current.leftNode) ? current.rightNode : current.leftNode;
if (current.key.compareTo(parent.key) > 0) {
parent.rightNode = childNode;
} else {
parent.leftNode = childNode;
}
return true;
}
}
}
}
return false;
}
/**
* 处理被删除节点有两个子节点的情况
* @param parent
* 将要被删除的节点
*/
private void dleTwoChildrenNode(Node parent) {
Node parentRight = parent.rightNode;
Node tmp = parentRight.leftNode;
if (null == tmp) {
parent.value = parentRight.value;
parent.key = parentRight.key;
parent.rightNode = parentRight.rightNode;
} else {
Node tmpParent = parentRight;
while (null != tmp.leftNode) {
tmpParent = tmp;
tmp = tmp.leftNode;
}
parent.value = tmp.value;
parent.key = tmp.key;
tmpParent.leftNode = tmp.rightNode;
}
}
public static void main(String[] args) {
BinarySerachTree<Integer, String> bst = new BinarySerachTree<Integer, String>();
bst.put(100, "v100");
bst.put(50, "v50");
bst.put(150, "v150");
bst.put(20, "v20");
bst.put(85, "v85");
bst.put(10, "v10");
bst.put(15, "a15");
bst.put(75, "v75");
bst.put(95, "v95");
bst.put(65, "v65");
bst.put(76, "v76");
bst.put(60, "v60");
bst.put(66, "v66");
bst.put(61, "v61");
System.out.println(bst.get(100));// 打印根节点
}
}
BinarySerachTree
public class RedBlackTree<K extends Comparable<K>, V> {
private static final byte RED = 1;
private static final byte BLACK = 0;
private class Node {
private byte color;
private K key; // 存储的key
private V value; // 存储的值
private Node leftNode; // 左节点
private Node rightNode; // 右节点
private Node parentNode; // 父节点
public Node(K key, V value, Node leftNode, Node rightNode, byte color, Node parentNode) {
super();
this.key = key;
this.value = value;
this.leftNode = leftNode;
this.rightNode = rightNode;
this.color = color;
this.parentNode = parentNode;
}
@Override
public String toString() {
return "{" + "\"key\":" + this.key + ", " + "\"value\":" + "\"" + this.value + "\"" + ", " + "\"color\":"
+ this.color + ", " + "\"leftNode\":" + this.leftNode + "," + "\"rightNode\":" + this.rightNode
+ "}";
}
}
private Node root; // 根节点
public Node getRoot() {
return this.root;
}
private void leftRotation(Node h) {
Node m = h.rightNode;
// 1. 将 k 节点设置为 h 的右节点
h.rightNode = m.leftNode;
if (null != m.leftNode) {
m.leftNode.parentNode = h;
}
// 2. 将 h 的父节点 赋给 m 的父节点，之后分 3 种情况讨论
m.parentNode = h.parentNode;
if (null == m.parentNode) { // I: 说明 h 原来是根节点，现在将 m 设置为新的根节点
root = m;
} else {
if (h.key.compareTo(h.parentNode.key) < 0) { // II: 说明 h 原来是它父节点的左孩子，现在将 m 设置为新的左孩子
h.parentNode.leftNode = m;
} else {
h.parentNode.rightNode = m; // III: 说明 h 原来是它父节点的右孩子，现在将 m 设置为新的右孩子
}
}
// 3. 将 h 挂靠在 m 的左孩子上
m.leftNode = h;
h.parentNode = m;
}
private void rightRotation(Node m) {
Node h = m.leftNode;
// 1. 将 k 设置为 m 的左节点
m.leftNode = h.rightNode;
if (null != h.rightNode) {
h.rightNode.parentNode = m;
}
// 2. 将 m 的父节点 赋给 h 的父节点，之后分 3 种情况讨论
h.parentNode = m.parentNode;
if (null == m.parentNode) { // I: 说明 m 原来是根节点，现在将 h 设置为新的根节点
root = h;
} else {
if (m.key.compareTo(m.parentNode.key) < 0) { // II: 说明 m 原来是它父节点的左孩子，现在将 h 设置为新的左孩子
m.parentNode.leftNode = h;
} else {
m.parentNode.rightNode = h; // III: 说明 m 原来是它父节点的右孩子，现在将 h 设置为新的右孩子
}
}
// 3. 将 m 挂靠在 h 的右孩子上
h.rightNode = m;
m.parentNode = h;
}
/**
* 插入新的节点，如果指定的key已经存在，则更新原来的值
*
* @param key
* @param value
*/
public void put(K key, V value) {
Node newNode = new Node(key, value, null, null, RED, null);
if (null == root) {
root = newNode;
root.color = BLACK;
} else {
upsert(null, root, newNode);
}
}
private void upsert(Node parent, Node current, Node newNode) {
if (null == current) {
if (newNode.key.compareTo(parent.key) > 0) {
parent.rightNode = newNode;
} else {
parent.leftNode = newNode;
}
newNode.parentNode = parent;
upsertFix(newNode); // 插入新节点后 对红黑树进行修复
} else {
int result = newNode.key.compareTo(current.key);
if (result == 0) {
current.value = newNode.value;
}
parent = current;
if (result > 0) {
upsert(parent, parent.rightNode, newNode);
}
if (result < 0) {
upsert(parent, parent.leftNode, newNode);
}
}
}
private void upsertFix(Node newNode) {
Node parent = newNode.parentNode;
if (RED == parent.color) { // 父节点如果是黑节点 则不需要处理
Node grandfather = parent.parentNode;
if (parent == grandfather.leftNode) { // 1. 父节点原来是 左节点
Node uncle = grandfather.rightNode;
if ((null != uncle) && (RED == uncle.color)) { // case 3: 叔叔节点是红色
uncleRedFix(newNode);
} else { // 叔叔节点为 NULL 或者 是黑色节点
if (newNode.key.compareTo(parent.key) < 0) { // case 1: 叔叔节点是黑色，插入到左子树中
leftNodeFix(grandfather, parent);
} else { // case 2: 叔叔节点是黑色，插入到右子树中
leftRotation(parent);
leftNodeFix(grandfather, newNode); // 我们将 parent 节点作为“新插入的节点”，这样 真正新插入的节点 newNode 就是父节点
}
}
} else { // 1. 父节点原来是 右节点
Node uncle = grandfather.leftNode;
if ((null != uncle) && (RED == uncle.color)) { // case 3: 叔叔节点是红色
uncleRedFix(newNode);
} else { // 叔叔节点为 NULL 或者 是黑色节点
if (newNode.key.compareTo(parent.key) > 0) { // case 1: 叔叔节点是黑色，插入到右子树中
rightNodeFix(grandfather, parent);
} else { // case 2: 叔叔节点是黑色，插入到左子树中
rightRotation(parent);
rightNodeFix(grandfather, newNode); // 我们将 parent 节点作为“新插入的节点”，这样 真正新插入的节点 newNode 就是父节点
}
}
}
}
}
/**
* 处理 父节点原来是 左节点 的 case 1 的情况: 叔叔节点是黑色，插入到左子树中
*
* @param grandfather
* @param parent
*/
private void leftNodeFix(Node grandfather, Node parent) {
parent.color = BLACK;
grandfather.color = RED;
rightRotation(grandfather);
}
/**
* 处理 父节点原来是 右节点 的 case 1 的情况: 叔叔节点是黑色，插入到右子树中
*
* @param grandfather
* @param parent
*/
private void rightNodeFix(Node grandfather, Node parent) {
parent.color = BLACK;
grandfather.color = RED;
leftRotation(grandfather);
}
/**
* 处理 case 3: 叔叔节点是红色
*
* @param newNode
*/
private void uncleRedFix(Node newNode) {
Node parent = newNode.parentNode;
if ((null != parent) && (RED == parent.color)) {
Node grandfather = parent.parentNode;
Node uncle = grandfather.leftNode;
if (parent == grandfather.leftNode) {
uncle = grandfather.rightNode;
}
parent.color = BLACK;
uncle.color = BLACK;
if (root != grandfather) {
grandfather.color = RED;
upsertFix(grandfather);
}
}
}
/**
* 删除 叶子节点 后的修复过程
*
* @param deletedNode
* 被删除的节点
* @param deletedNodeParent
* 被删除节点的父节点
*/
private void deleteLeafFix(Node deletedNode) {
while ((deletedNode != root) && (BLACK == deletedNode.color)) {
Node parent = deletedNode.parentNode;
Node brother = getBrother(deletedNode);
if (deletedNode.key.compareTo(parent.key) > 0) { // 删除的是右叶子节点
if (RED == brother.color) { // case5: 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
brother.color = BLACK;
brother.rightNode.color = RED;
rightRotation(parent);
break;
} else {
if ((null == brother.leftNode) && (null == brother.rightNode)) { // case4: 兄弟节点是黑色的，且没有子节点
brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
deletedNode = parent;
} else {
if ((null != brother.leftNode) && (RED == brother.leftNode.color)) {// case1:
// 兄弟节点是黑色的，且有一个左节点（可以断定
// 左节点是红色的）
// case3: 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
brother.color = parent.color;
parent.color = BLACK;
brother.leftNode.color = BLACK;
rightRotation(parent);
break;
} else {// case2: 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
brother.rightNode.color = BLACK;
brother.color = RED;
leftRotation(brother);
}
}
}
} else {// 删除的是左叶子节点
if (RED == brother.color) { // case5 : 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
brother.color = BLACK;
brother.leftNode.color = RED;
leftRotation(parent);
break;
} else {
if ((null == brother.leftNode) && (null == brother.rightNode)) { // case4: 兄弟节点是黑色的，且没有子节点
brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
deletedNode = parent;
} else {
if ((null != brother.rightNode) && (RED == brother.rightNode.color)) { // case1 :
// 兄弟节点是黑色的，且有一个右节点（可以断定
// 右节点是红色的）
// case3 : 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
brother.color = parent.color;
parent.color = BLACK;
brother.rightNode.color = BLACK;
leftRotation(parent);
break;
} else { // case2: 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的）
brother.leftNode.color = BLACK;
brother.color = RED;
rightRotation(brother);
}
}
}
}
}
deletedNode.color = BLACK;
}
private Node getBrother(Node node) {
if (null == node) {
return null;
}
Node parent = node.parentNode;
if (null == parent) {
return null;
}
if (node.key.compareTo(parent.key) > 0) {
return parent.leftNode;
} else {
return parent.rightNode;
}
}
public boolean delete(K key) {
if (null != key) {
if (null != root) {
return deleteNode(key, root, null);
}
}
return false;
}
private boolean deleteNode(K key, Node current, Node parent) {
if (null != current) {
if (key.compareTo(current.key) > 0) {
return deleteNode(key, current.rightNode, current);
}
if (key.compareTo(current.key) < 0) {
return deleteNode(key, current.leftNode, current);
}
if (key.compareTo(current.key) == 0) {
if ((null != current.leftNode) && (null != current.rightNode)) { // 将要删除的节点下有两个子节点
dleTwoChildrenNode(current);
return true;
} else {
if ((null == current.leftNode) && (null == current.rightNode)) { // 将要删除的节点没有子节点
deleteLeafFix(current);
if (current.key.compareTo(parent.key) > 0) {
parent.rightNode = null;
} else {
parent.leftNode = null;
}
return true;
} else { // 将要删除的节点下有一个子节点,
dleOneChildNode(current);
return true;
}
}
}
}
return false;
}
private void dleOneChildNode(Node delNode) {
Node replaceNode = (null == delNode.leftNode) ? delNode.rightNode : delNode.leftNode;
deltetLeafNode(delNode, replaceNode);
}
/**
* 处理被删除节点有两个子节点的情况
*
* @param target
* 将要被删除的节点
*/
private void dleTwoChildrenNode(Node target) {
Node replaceNode = successor(target);
if ((null == replaceNode.rightNode) && (null == replaceNode.leftNode)) {
deltetLeafNode(target, replaceNode);
} else {
target.key = replaceNode.key;
target.value = replaceNode.value;
dleOneChildNode(replaceNode);
}
}
private void deltetLeafNode(Node target, Node replaceNode) {
target.key = replaceNode.key;
target.value = replaceNode.value;
deleteLeafFix(replaceNode);
if (replaceNode == replaceNode.parentNode.rightNode) {
replaceNode.parentNode.rightNode = null;
} else {
replaceNode.parentNode.leftNode = null;
}
}
// 找后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"
private Node successor(Node node) {
if (node == null) {
return null;
}
if (null != node.rightNode) { // 获取 后继节点
Node p = node.rightNode;
while (null != p.leftNode) {
p = p.leftNode;
}
return p;
} else {
Node p = node.parentNode;
Node ch = node;
while (p != null && ch == p.rightNode) {
ch = p;
p = p.parentNode;
}
return p;
}
}
public static void main(String[] args) {
RedBlackTree<Integer, String> bst = new RedBlackTree<Integer, String>();
bst.put(100, "v100");
bst.put(50, "v50");
bst.put(150, "v150");
bst.put(20, "v20");
bst.put(85, "v85");
bst.put(10, "v10");
bst.put(15, "a15");
bst.put(75, "v75");
bst.put(95, "v95");
bst.put(65, "v65");
bst.put(76, "v76");
bst.put(60, "v60");
bst.put(66, "v66");
bst.put(61, "v61");
// 当前节点是左节点 的 5中情况
// bst.delete(15); // 1. 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
// 2. 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的
// bst.put(140, "v140");
// bst.delete(95);
// 4. 兄弟节点是黑色的，且没有子节点
// bst.delete(66);
// 5. 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
// bst.delete(95);
// bst.delete(15);
System.out.println(bst.getRoot());
}
}
RedBlackTree
