数据结构(7.3_4)——红黑树的定义和性质
红黑树和平衡排序二叉树的查插删时间
平衡二叉树的适用场景：适用以查为主、很少插入/删除vd场景
红黑树：适用于频繁插入、删除的场景，实用性更强
红黑树的考点
红黑树的定义：
红黑树的二叉排序树：左子树结点值<=根结点值<=右子树结点值
与普通BST相比，有什么要求：
- 每个结点或是红色，或是黑色的
- 根结点是黑色的
- 叶结点(外部结点，NULL结点失败结点)均是黑色的
- 不存在两个相邻的红结点(即红结点的父结点和孩子结点均是黑色的)
- 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
口诀：左根右，根叶黑，不红红，黑路同
struct RBnode {//红黑树的结点定义int key;//关键字的指针RBnode* parent;//父节点指针RBnode* lchild, * rchild;//左、右孩子指针int color;//结点颜色}实例：
练习：
答案：不是红黑树，因为不存在两个相邻的红结点的红黑树
答案：不是，因为根结点是黑色的
答案：不是，因为 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
答案：不是，因为红黑树首先必须是棵二叉排序树，违法“左根右”的特性
结点的“黑高”
结点的黑高bh--从某结点出发(不含该结点)到达任一空叶结点的路径上黑结点总数
红黑树的性质
- 从根结点到叶结点的最长路径不大于最短路径的2倍
- 有n个内部结点的红黑树高度
- 红黑树查找操作时间复杂度=
红黑树的查找
与BST、AVL相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败
红黑树的插入
