红黑树是比较常见的数据结构之一，在Linux内核中的完全公平调度器、高精度计时器、多种语言的函数库(如,Java的TreeMap)等都有使用。
在学习红黑树之前，先来熟悉一下二叉查找树。
二叉查找树(Binary Search Tree)二叉查找树，它有一个根节点，且每个节点下最多有只能有两个子节点，左子节点的值小于其父节点，右子节点的值大于其父节点。
从根节点向下查找，当新插入节点大于比较的节点时，新节点插入到比较节点的右侧，当小于比较的节点时，插入到比较节点的左侧，一直向下比较大小，找到要插入元素的位置并插入元素。
如图: 依次插入节点[100,50,200,80,300,10]
伪代码(来源Java TreeMap，有省略和修改):
void put(K key, V value) { if (root == null) { root = new Node<>(key, value, null); return; } Node<K,V> t = root; int cmp; // 比较结果 Node<K,V> parent; Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return; // 节点存在直接返回 } while (t != null); Node<K,V> e = new Node<>(key, value, parent); if (cmp < 0){ parent.left = e; }else{ parent.right = e; } } 查找节点从根节点开始向下查找，当查找节点大于比较的节点时，向右查找，当小于当前比较节点时，就向左查找。一直向下查找，直到找到对应的节点或到终点查找结束。
如图: 查找节点[80]
伪代码(来源Java TreeMap，有省略和修改):
Node<K,V> getNode(Object key) { Comparable<? super K> k = (Comparable<? super K>) key; Node<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; } 删除节点删除节点首先要查找要删除的节点，找到后执行删除操作。
删除节点的节点有如下几种情况：
删除的节点有两个子节点
删除的节点有一个子节点
删除的节点没有子节点
Case 1：该种情况下，涉及到节点的“位置变换”，用右子树中的最小节点替换当前节点。从右子树一直 left 到 NULL。最后会被转换为 Case 2 或 Case 3 的情况。
所以对于删除有两个孩子的节点，删除的是其右子树的最小节点，最小节点的内容会替换要删除节点的内容。
如图:删除节点[50]
有一个子节点的情况下，将其父节点指向其子节点，然后删除该节点。
如图:删除节点[200]
在没有子节点的情况，其父节点指向空，然后删除该节点。
如图:删除节点[70]
伪代码(来源Java TreeMap，有省略和修改):
Node remove(Object key) { // 查找节点(参考上面查找代码) Node<K,V> p = getNode(key); // 节点变换。 p 有两个子节点，将其转换为删除后继节点 if (p.left != null && p.right != null) { Entry<K,V> s = t.right; while (s.left != null){ s = s.left; } p.key = s.key; p.value = s.value; p = s; } Entry<K,V> replacement = (p.left != null ? p.left : p.right); // p 有一个子节点 if (replacement != null) { replacement.parent = p.parent; if (p.parent == null){ root = replacement; } else if (p == p.parent.left){ p.parent.left = replacement; } else{ p.parent.right = replacement; } p.left = p.right = p.parent = null; } else if (p.parent == null) { // 根节点 root = null; } else { // p 没有子节点 if (p == p.parent.left){ p.parent.left = null; } else if (p == p.parent.right){ p.parent.right = null; } p.parent = null; } return p; } 树的优势