小宅

V1

2023/03/12阅读:12主题:默认主题

数据结构 & 平衡二叉树

二叉树

普通二叉树 & 二分查找树

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

平衡二叉树

  • 二叉树左右两个字树的高度差不超过1
  • 任意节点的左右两个子树都是一颗平衡二叉树
  • 查找值的性能会更好

平衡二叉树-旋转

触发时机

  • 当添加一个节点之后, 该树不在是一棵平衡二叉树

左旋

  • 右节点的树比左节点的树要多, 则时则往左移
  • 就是将根节点的右侧向左拉, 原先的右子节点变成新的父节点,并把多余的左子节点让出,给寂静降级的根节点当右子节点

case1 原:

左移后:

case2 原:

左移后

右旋

  • 左树比右树要多, 则时则往右移
  • 将根节点的侧向右拉, 原先的左子节点变成新的父节点,并把多余的右子节点让出,给已经降级的根节点当左子节点

红黑树

红黑树是一种自平衡的二叉查找树,

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

添加节点总结

分类:

后端

标签:

后端

作者介绍

小宅
V1