红黑树分析

红黑树性质

1.每个节点要么为黑色要么为红色 2.根节点是黑色 3.叶子节点均为黑色(nil) 4.如果一个节点是红色的那么它的叶子节点必须是黑色的 5.从一个节点到其子孙节点的路径中所包含的黑色节点相同(也就是所谓黑高相同)

               [黑]
              /    \
             /      \
            /        \
         [红]        [红]
        /    \      /    \
       /      \    /      \
    [黑]     [黑] [黑]    [黑]
   /    \   /   \/   \  /    \
  [nil][nil][nil]...
  //最底层无实际值的节点被称为叶子节点，其节点是黑色的

红黑树的插入

红黑树可以看成3阶段b树，也就是说其黑色节点可以提到其父节点的两边，在逻辑上三个节点看成一个b树节点 红黑树为了保持以上五条性质才能保证其nlogn的查找 红黑树被插入节点初始颜色是红色

1.插入情况1 "B树节点未满" 也就是说存在黑色非叶节点(有意义的节点)两个子节点至少有一个不存在的情况。那么直接插入即可。此时红黑树不需要调整 某子树: ...
黑(1) /
nil(2) nil(3) 1的左右子节点是空的，所以可以任意插入

2.插入情况2 插入节点的父节点是红色