数据结构--红黑树

一、为什么要发明红黑树。

（平衡二叉树要求任何一个左子树和右子树的高度差不超过一，很容易被插入或删除元素破坏，再次进行调整，会导致时间开销变大。）

  红黑树在插入删除时，不会破坏红黑树的特效，无需频繁调整树的形态，即便需要调整，一般可在常数级时间完成。

  平衡二叉树：适用于以查为主、很少插入/删除的场景。

  红黑树：适用于频繁插入、删除的场景，实用性更强。

二、红黑树的定义与性质

  红黑树是二叉排序树-------左子树结点值<=根结点值<=右子树结点值

   要求：（左根右，根叶黑，不红红，黑路同）

    ①每个结点或是红色，或是黑色的
    ②根节点是黑色的
    ③叶结点(外部结点、NULL结点、失败结点)均是黑色的

    ④不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)

    ⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

  性质：1:从根节点到叶结点的最长路径不大于最短路径的2倍性质

             2:有n个内部节点的红黑树高度h≤2log2^(n+1)

   红黑树查找操作时间复杂度=0(log2^n)-------------查找效率与AVL树同等数量级

三、红黑树查找

     与二叉排序树相同，从根节点查找，小于根节点向左，大于根节点向右。