红黑树介绍

红黑树的定义

红黑树是一种特殊的二叉搜索树，主要有以下几个规则：

1. 节点有颜色，分为红色和黑色两种颜色
2. 根节点是黑色的
3. 每个叶子结点都是黑色的空结点（NIL结点）
4. 红色节点的子节点都是黑色的，即任何相邻的节点都不能同时为红色
5. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
   

红黑树节点的添加

当向红黑树中添加节点时，要根据节点值大小确定节点插入的位置，插入节点默认颜色为红色，但插入新节点后可能导致破坏红黑树的五个规则，因此要进行一些操作来更新红黑树结构：

• 变色：就是将节点颜色从红色变成黑色，或者从黑色变成红色
  
  左图中添加节点Y后，导致出现红色节点X的孩子节点仍然是红色，违反了规则4，应该将X或者Y其中一个变为黑色，或者全变为黑色。但是由于避免违反规则5，故只能选择将X节点变为黑色
• 左旋
  逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为新的父节点的左孩子。
  
• 右旋
  顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为新的父节点的右孩子。
  

红黑树与平衡二叉树(AVL树)

不同点：

• AVL树要求每个节点的左右子树高度差不超过1，而红黑树并不要求
• AVL树需要经常经过反转保证平衡，而红黑树可经过变色，旋转来保证红黑树的性质，而旋转操作相对简单

相同点：

查找效率都是O(logN),但是相对来说AVL的查找效率更高

总结

当搜索的次数远远大于插入或者删除操作次数时，选择AVL树；反之，当搜索、插入、删除次数几乎差不多，则应该选择红黑树
红黑树牺牲了部分平衡性以换取插入/删除操作时更少量的旋转操作，整体来说性能要优于AVL树，实际应用中被更多的应用