小
小宅
V1
2023/03/12阅读:12主题:默认主题
数据结构 & 平衡二叉树
二叉树

普通二叉树 & 二分查找树

-
二叉查找树, 子左节点比根节点要小, 右子节点比根节点要大
平衡二叉树

-
二叉树左右两个字树的高度差不超过1 -
任意节点的左右两个子树都是一颗平衡二叉树 -
查找值的性能会更好
平衡二叉树-旋转
触发时机
-
当添加一个节点之后, 该树不在是一棵平衡二叉树
左旋
-
右节点的树比左节点的树要多, 则时则往左移 -
就是将根节点的右侧向左拉, 原先的右子节点变成新的父节点,并把多余的左子节点让出,给寂静降级的根节点当右子节点
case1 原:

左移后:

case2 原:

左移后

右旋
-
左树比右树要多, 则时则往右移 -
将根节点的侧向右拉, 原先的左子节点变成新的父节点,并把多余的右子节点让出,给已经降级的根节点当左子节点
红黑树
红黑树是一种自平衡的二叉查找树,

-
平衡二叉B -
每一个节点可以是红或者黑 -
红黑树不是高度平衡的,它的平衡是通过“自己的红黑规则“进行实现的 -
根节点必须是黑色的 -
如果一个节点没有子节点或者父节点,该节点相应的指针属性为nil这些nil 视为叶节点,每个叶节点(Nil)是黑色的 -
如果某一个节点是红色的, 那么它的子节点必须是黑色的(不能存在两个红色节点的相连的情况) -
每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点

添加节点总结


作者介绍
小
小宅
V1