数据结构--红黑树
一、为什么要发明红黑树。
（平衡二叉树要求任何一个左子树和右子树的高度差不超过一，很容易被插入或删除元素破坏，再次进行调整，会导致时间开销变大。）
红黑树在插入删除时，不会破坏红黑树的特效，无需频繁调整树的形态，即便需要调整，一般可在常数级时间完成。
平衡二叉树：适用于以查为主、很少插入/删除的场景。
红黑树：适用于频繁插入、删除的场景，实用性更强。
二、红黑树的定义与性质
红黑树是二叉排序树-------左子树结点值<=根结点值<=右子树结点值
要求：（左根右，根叶黑，不红红，黑路同）
①每个结点或是红色，或是黑色的
②根节点是黑色的
③叶结点(外部结点、NULL结点、失败结点)均是黑色的
④不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)
⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
性质：1:从根节点到叶结点的最长路径不大于最短路径的2倍性质
2:有n个内部节点的红黑树高度h≤2log2^(n+1)
红黑树查找操作时间复杂度=0(log2^n)-------------查找效率与AVL树同等数量级
三、红黑树查找
与二叉排序树相同，从根节点查找，小于根节点向左，大于根节点向右。