红黑树平衡原理

文档摘要

红黑树平衡原理红黑树是一种自平衡二叉搜索树，保证操作在最坏情况下O(log n)时间。定义规则节点红色或黑色根节点是黑色叶节点NIL是黑色红色节点的子节点必须是黑色任一节点到叶节点的路径包含相同数目的黑节点黑高度从节点到叶节点的黑节点数记为bh(x) 性质：bh(x) >= h(x)/2 平衡操作旋转左旋：右子节点上移，自己下沉右旋：左子节点上移，自己下沉 O(1)时间完成变色改变节点颜色配合旋转保持性质插入修复情况1：叔节点是红色父节点和叔节点变黑祖父节点变红继续向上修复情况2：叔节点是黑色旋转和变色组合最多两次旋转恢复删除修复更复杂，需要分类讨论最多三次旋转保证树的高度平衡时间复杂度查找：O(log n) 插入：O(log