1、在学习红黑树之前有必要先来了解一下二叉查找树。二叉查找树是基于二分查找的思想，查找所需的次数为二叉查找树的高度；在插入节点时也是通过一层一层的比较来找到合适插入的位置。但它仍然存在缺陷，就是当插入的数据是依次递增时，它会不断地插在节点的右子树上(或者是当插入的数据是依次递减时，它会不断地插在节点的左子树)。此时的二叉查找树的查找性能几乎变成了线性。那么如何解决二叉查找树多次插入新节点而导致的不平衡呢？红黑树也就应运而生了。
二叉查找树的性质：
a、左子树上所有结点的值均小于或等于它的根结点的值。
b、右子树上所有结点的值均大于或等于它的根结点的值。
c、左、右子树也分别为二叉排序树。
2、红黑树(Red Black Tree)是一种平衡的二叉查找树(但不是一个完美的平衡二叉树)。它的应用有很多，Java中的TreeSet和TreeMap数据结构，Java8中的HashMap也用到了红黑树；在C++ STL中，很多部分(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
(1)性质a、节点是红色或黑色。
b、根节点是黑色。
c、每个叶子节点都是黑色的空节点（NIL节点）。
d、每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
e、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
以上这些限制强化了红黑树的关键属性：从根节点到最远叶节点的路径不超过从根到最近叶节点的路径的两倍(最短的路径是:全部都是黑色节点，最长的路径是:在红色和黑色节点之间交替)。这也是红黑树和二叉查找树之间最大的不同。
(2)左旋转和右旋转a、左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右子树取代，而父节点自己成为自己右子树(现在已经是父节点了)的左子树。现在已经是父节点的的左子树成为曾经的父节点的右子树。
b、右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左子树取代，而父节点自己成为自己左子树(现在已经是父节点了)的右子树。现在已经是父节点的的右子树成为曾经的父节点的左子树。
(3)插入节点a、当前节点位于树的根部。为了满足（根节点是黑色），将其颜色变成黑色。由于这会向每条路径都添加一个黑色节点，所以（从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点）不会被违反。
b、当前节点的父节点是黑色的。所以（每个红色节点的两个子节点都是黑色）不会失效。（从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点）没有受到威胁，因为当前节点有两个黑色节点，但由于当前节点是红色，所以到达其每个叶子节点路径上的黑色节点的数量与它所替换的叶子节点路径上的黑色节点的数量是相同的。
c、如果父节点和父节点的兄弟节点都是红色的，那么可以将他们的颜色都变成黑色，并且将祖父母节点的颜色变成红色以维持（从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点）。由于通过父节点和父节点的兄弟节点的任何路径必须经过祖父母节点，所以这些路径上的黑色节点的数目并没有改变。然而，祖父母节点现在可能违反了（根节点是黑色），如果它是根或（每个红色节点的两个子节点都是黑色），如果它具有红色的父母节点。为了解决这个问题，树上的红黑修复程序在祖父母节点上重新运行。
d、父节点是红色的，但是父节点的兄弟节点是黑色的。最终目标是将当前节点旋转到祖父母节点的位置，但如果当前节点位于祖父母节点下子树的“内部” （即，如果当前节点是祖父母节点的右子节点的左子节点或者是祖父母节点的左子节点的右子节点）。在这种情况下，可以在父节点上执行左旋转以切换当前节点及其父节点的位置。由于父节点和当前的插入节点都是红色的，所以旋转这两个节点不会使（从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点）受到旋转的影响。这一步完成后（每个红色节点的两个子节点都是黑色）仍然被违反。此时，当前节点现在肯定位于祖父母节点的子树的外部（左子节点或右子节点）。在这种情况下，执行祖父母节点上的右旋转;其中前父母节点现在是当前节点和前祖父母节点的父母节点。此时前父母节点和前祖父母节点的颜色互换，结果树满足（每个红色节点的两个子节点都是黑色）。（从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点）也依然不满足，再将前祖父母节点和其右子节点的颜色互换即可。
*具体的红黑树中插入和删除出现的有关旋转和变色的情况，请自行跳转至维基百科查看：维基百科红黑树
