记录算法中,与树相关的内容
包括树,二叉树,红黑树,b+树等概念以及图中最小生成树算法。
二叉树:满足左子节点小于中间节点,中间节点小于右子节点。
同样数据不同的插入顺序形成的二叉树也不同。
插入:按树索引至合适的位置,直接插入
删除:
- 删除的节点 x 为叶节点:直接删除
- 删除的节点 x 存在一个子树:将子树直接接入父节点
- 删除的节点 x 存在两个子树:找到删除节点的后继节点 ( y = successor(x))。交换两个节点的值,并删除y。
后继节点(successor):
- 存在右子树,找到右子树中的最小值
- 不存在右子树,向上循环找父节点,直至找到前一个父节点不是当前父节点的右子节点的父节点。此节点为后继节点。
红黑树:
在满足二叉搜索树的基础上,满足:
- 每个节点都是红色或黑色
- 如果一个节点是红色的,那么它是叶子节点,或者他有两个黑色子节点
- 从任意一个节点 x 开始,任意一条从 x 到叶节点的路径的长度是一样的。这个长度称为 x 的黑长。b(x)。
- 根节点是黑色的。
插入:
两次旋转
删除:
删除的节点是红色的:不发生变化
删除的节点是黑色的: