红黑树原理分析，hashmap源码分析前菜

红黑树

本篇文章看完，可以看hashmap源码分析，源码逐行解释
红黑树模拟网站cs.usfca.edu/~galles/visualization/RedBlack.html

定义

• 红黑树是一种含有红黑节点并能自平衡的二叉查找树(左节点小于父节点，右节点大于父节点)

性质

• 每个节点要么是红色，要么是黑色

• 根节点是黑色

• 每个叶子节点(NIL,虚拟节点,value为null)是黑色
  

• 每个红色节点的两个子节点一定都是黑色

• 任意一节点到每个叶子节(NIIL)点的路径都包含数量相同的黑节点

红黑树的平衡性

• 红黑树并非完美平衡的二叉查找树，是完美黑色平衡的二叉查找树
• 红黑树的自平衡每次只考虑CPGU三代即可，其余部分无需考虑
  • 祖父母G-Grandparents
  • 父母P-Parents
  • 叔叔U-Uncle
  • 兄弟B-Brother
  • 根R-Root
  • 当前新增节点C-Current
• 红黑树自平衡性的原子操作
  • 变色
  • 旋转，包括左旋和右旋

红黑树的查找操作

• 即二分查找

红黑色的新增操作

• 需要考虑的几种情况

  • 情况1：c == root
  • 情况2：c.parent.color == black
  • 情况3：c.parent.color == red && c.uncle == red
  • 情况4：c.parent.color == red && (c.uncle == black || c.uncle == null)
    

• 针对上满几种情况的处理办法
  

• 对上面4种情况举例分析
  

  • 情况1：c == root

    • 设置新增节点为红色
    • 修改新增节点颜色为黑色
      

  • 情况2：c.parent.color == black

    • 设置新增节点为红色
      

  • 情况3：c.parent.color == red && c.uncle == red

    • 设置新增节点为红色
    • 父节点变成黑色
    • 叔叔节点变成黑色
    • 祖父节点变成红色
    • 如果祖父借你单变红导致不满足红黑树的性质，将祖父及诶单作为新增节点，递归处理前4步
      

  • 情况4.1c.parent.color == red && (c.uncle == black || c.uncle == null)且新增节点、父亲节点、祖父节点三点一线

    • 以父节点为圆心，旋转祖父节点
    • 给父节点和祖父节点变色，使其满足性质
      

  • 情况4.2c.parent.color == red && (c.uncle == black || c.uncle == null)且新增节点、父亲节点、祖父节点三角关系

    • 以新增节点为圆心，旋转父亲节点，也就是将三角关系转换为三点一线关系
    • 按照情况4.1方法来处理

本篇文章看完，可以看hashmap源码分析，源码逐行解释