看了两天HashMap源码，终于把红黑树插入平衡规则搞懂了 _红黑树

絮叨学校短学期刚结束了，离学校开学还有很多天，一直呆在寝室玩游戏岂不是浪费了大好时光，于是心血来潮想看看HashMap的源码。虽然我没有经历过面试，但是JAVA程序员都知道，HashMap是面试官必问的知识点，而我现在只停留在对HashMap的基本使用层面，因此我觉得有必要深入了解一下HashMap的底层原理。在HashMap中，我觉得最难的应该是红黑树了吧，我结合代码和画图软件研究了两天，终于总结出规律，现在分享给大家
一、红黑树的特点下面是红黑树的5条性质，现在大家要对这些性质有印象，后面我会结合图解的形式，多次提到这些性质来帮助大家记忆

每个节点要么是红的，要么是黑色的
跟节点一定是黑色的
叶子节点一定是黑色的（叶节点一般不画，在末尾节点上，没有内容）
红节点下的两个子节点一定是黑色的
任意一条从根节点到叶子节点的路径中黑色节点的个数相等

红黑树插入节点后，若导致红黑树不平衡（整棵树不满足上面5条性质中的任意一条），就会进行变色、旋转操作，直到红黑树平衡，而学习红黑树的难点正是这些变色、旋转的规则
二、红黑树的优点谈到红黑树的优点，就不得不拿出AVL树来进行比较。
AVL树是完全平衡的树，根的最大深度和最小深度相差不大于1，查找效率比较高，而红黑树不是完全平衡树，查找效率略低于AVL树
红黑树的插入和删除操作比AVL树快很多，因为红黑树保证插入删除时最多需要旋转三次就可以达到平衡，而AVL树每次插入删除会进行大量的平衡度计算，开销很大
因此，红黑树牺牲了一点点查找效率，使它有更快的插入删除操作，综合来说，红黑树性能高于AVL树
三、红黑树插入如何平衡3.1 红黑树插入基本规则