目录

ThasBlog

学无止境

标签: 数据结构 (1)

红黑树 有更新!

红黑树是特殊的二叉平衡搜索树。 特点: 所有节点均为黑色或红色节点。 根节点一定为黑色节点。 叶子节点均使用 NIL 黑色节点填充。 不能出现连续的红色节点。 根节点到叶子节点的所有路径具有相同数量的黑色节点。 红黑树保证平衡的重要手段是左旋/右旋以及变色。 模拟器:https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 二叉搜索树左子节点 < 根节点 < 右子节点, 无论左旋还是右旋始终满足这个大小关系。 左旋/右旋这两种手段适用于全部的二叉搜索树, 而不仅仅是平衡树。 红黑树保持平衡的方式: 大前提: 新插入的节点永远是红色. (如果是黑色, 那就没有红色了, 全靠黑色节点来保障平衡, 那就退化成严格平衡二叉树了) 1 新插入节点的父节点是黑色节点, 红黑树依然保持平衡, 无需操作。 2 新插入节点的父节点是红色节点, 叔叔节点为黑色节点或 NIL(直接忽略叔叔节点或者将其看成一个 NIL 整体): 分为 LL/RR 和 LR/RL 两大类型。 核心思想一样, 围绕新插入节点 + 父节点 + 祖父节....