AVL

红黑树也是一种二叉搜索树通过在每个结点中增加一个位置来存储红色或黑色并对结点的着色进行限制使得该二叉搜索树的最长路径不超过最短路径的两倍即红黑树是一颗近似平衡的二叉搜索树他不像

AVL

树的平衡那么严格所以红黑树在插入和删除时也不需要大量的旋转并且搜索效率差不了

AVL

每个节点不是红色就是黑色根结点是黑色的每个红结点的左右孩子一定是黑色从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点叶结点都是黑色的(这里的叶结点指的是空节点)

根据上述规则可以得到最短路径全黑结点的路径最长路径一黑一红的路径所以红黑树可以保证最长路径不超过最短路径的一半

enum

首先按照二叉搜索树的方式插入结点保证插入结点之后还是二叉搜索树为了方便树的结构调整插入结点默认为为红色当插入结点完成之后可能会违反红黑树的性质此时有三种情况

插入结点的父节点是红色叔节点存在且为红违反了红黑树的性质此时需要对父节点和爷爷结点进行变色

结点变为黑色否则将

插入结点的父节点是红色叔节点不存在或存在且为黑违反了红黑树的性质此时需要对爷爷结点所在的子树进行旋转然后再对结点进行变色

由于父节点是红色的所以爷爷结点一定存在且为黑变色完之后子树的根结点是黑色的不用继续向上调整

void

按照二叉搜索树的方式插入结点保证该树插入结点之后还是二叉搜索树if

(_root

cur){RotateR(grandfather);grandfather-_color

RED;parent-_color

BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather-_color

RED;cur-_color

cur){RotateL(grandfather);grandfather-_color

RED;parent-_color

BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather-_color

RED;cur-_color