【笔记】树学习笔记
前言
数据结构之树的学习笔记
树的概念
结点的度
- 一个结点含有的子树的个数称为度
叶结点（终端结点）
- 度为0的结点称为叶结点
分支结点
- 度不为0的结点称为分支结
结点的层次
- 从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
结点的层序编号
- 将树中的结点，按照从上层到下层、同层从左到右的次序排成一个线性序列，把他们编成自然数
树的度
- 树中所有结点的度的最大值
树的高度（树的深度）
- 树中结点的最大层次
森林
- m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，数就变成了一个森林；给森林增加一个统一的根结点，森林就变成一棵树
孩子结点
- 一个结点的直接后继结点称为该结点的孩子结点
双亲结点（父结点）
- 一个结点的直接前驱称为该结点的双亲结点
兄弟结点
- 同一双亲结点的孩子结点之间互相称为兄弟结点
二叉树
- 二叉树就是度不超过2的树
满二叉树
- 一个二叉树，如果每一层的结点树都达到最大值，则这个二叉树就是满二叉树
- 每一层的结点数为
2^(k-1)
完全二叉树
- 叶结点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
2-3树
定义
2- 结点
- 含有一个键和两条链，左链接指向的子结点都小于父结点，右链接指向的子结点都大于父结点
3- 结点
- 含有两个键和三个链，左链接指向的子结点都小于父结点，中间链接指向的子结点大于父结点较小的子结点，小于父结点较大的子结点，右链接指向的子结点都大于父结点
2-3树的性质
任意空链接到跟结点的路径长度是相等的
4- 节电变换为3- 节点时，树的高度不会发生变化，只有当跟结点是临时的4- 结点，分解根结点时，树的高度加1
2-3数与普通二叉树的最大区别在于，普通二叉树是自顶向下生长，而2-3树是自底向上生长
红黑树
- 红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉树（完全由2- 结点组成）和颜色来表示2-3树
红链接
- 将两个2- 结点连起来，构成一个3-结点
黑链接
- 2-3树中的普通链接
红黑树的定义
红链接均为左链接
没有任何一个结点同时和两条红链接相连
红黑树是完美的黑色平衡，即任意空链接到跟结点的路径上黑链接数量相同（红链接的父子结点视为一个黑链接上的结点）
平衡化
左旋
- 当某个结点的左子结点为黑色，右子结点为红色，需要左旋使红黑树达到平衡
右旋
- 当某个结点的左子结点为红色，左子结点的左子结点也为红色，需要右旋使红黑树达到平衡
颜色反转
- 当某个结点的左子结点和右子结点都为红色，此时为了达到红黑树平衡，可以将父结点指向父结点的链接改为红色，将所有子结点指向父结点的链接都改为黑色
B树
- B树实质上是对2-3树的扩展，B树匀速一个结点中包含多组键值对
B树的特性
每个结点最多有m-1个key，并且以升序排列
m：当前结点键值对的总数每个结点最多能有m个子结点
根结点至少有两个子结点
在实际应用中，B数的阶数都比较大（通常大于100），所以即使存储大量的数据，B数的高度仍然比较小
阶数：每个结点的子结点的最大值
B+树
- B+树是一种B树的变形
B+数和B树的区别
非叶结点只具有索引作用，也就是说非叶结点只存储key，不存储value
树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据
并查集
并查集的结构
每个元素都唯一对应一个结点
每一组数据中的多个元素都在同一棵树中
一个组中的数据对应的树和另外一个组中的数据对应的树没有任何联系
元素在树中并没有子父级的硬性要求