10.红黑树
# 01. 二叉查找树
# 1.1 二叉查找树(BST)
- 要想了解二叉查找树,我们首先看下二叉查找树有哪些特性呢?
- 1, 左子树上所有的节点的值均小于或等于他的根节点的值
- 2, 右子数上所有的节点的值均大于或等于他的根节点的值
- 3, 左右子树也一定分别为二叉排序树
# 1.2 二叉树中查找
- 正常的二叉树查找(log(n))
- 二叉查找树有时候也会退化成链表这种形式(时间复杂度:
O( N )
)
# 02.红黑树
# 2.1 红黑树定义和性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:
- 性质1:每个节点要么是黑色,要么是红色。
- 性质2:根节点是黑色。
- 性质3:每个叶子节点(NIL)是黑色。
- 性质4:每个红色结点的两个子结点一定都是黑色。
- 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
- 性质5.1:如果一个结点存在黑子结点,那么该结点肯定有两个子结点
# 2.2 左旋、右旋和变色
# 2.2.1 左旋
- 以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点
- 右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变
# 2.2.2 右旋
- 以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点
- 左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变
# 2.2.3 变色
- 结点的颜色由红变黑或由黑变红
# 2.2 变化规则
旋转和演示变换规则:
左右插入的点默认为红色
1.变色情况:
- 当前节点的父节点是红色,且它的祖父节点的另一子节点也是红色(叔叔节点)
- 1)把父节点设为黑色
- 2)把叔叔也设为黑色
- 3)把祖父也就是父亲的父亲设为红色(爷爷)
- 4)把指针定义到祖父节点设为当前要操作的(爷爷)
2.左旋
- 当前父节点是红色,叔叔节点时黑色时,且当前节点是右子树
- 左旋:以父节点作为左旋转节点
3.右旋
- 当前父节点是红色,叔叔是黑色,且当前的节点时左子树,右旋
- 1)
把父节点变成黑色
- 2)把祖父节点变成红色(爷爷)
- 3)以祖父节点旋转(爷爷)
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10