数据结构与算法分析3.树
点击进入我的博客
1 树与二叉树
1.1 树的概念
- 树是 n(n>=0) 个节点的有限集。
- n=0 时成为空树。
- 在任意一棵非空树中：
3.1 有且只有一个特定的成为根节点；
3.2 当n>1时，其余结点可分为m(m>0)个互不相交的有限集（T1、T2……Tm），其中每一个集合本身又是一棵树，并且称为根的子树；
3.3 并且子树是不相交的。
1.2 基本概念
度：节点拥有的子树的个数，度为0的节点为叶节点，度不为0的节点成为非终端节点或分支节点 。
树的度：是树内各节点度的最大值。
孩子：节点的子树的根称为该节点的孩子。
双亲：孩子结点的上层结点叫该结点的双亲。
兄弟：同一个双亲的孩子之间互称为兄弟。
祖先：节点的祖先是从根到该节点所经分支上的所有节点。
节点层次：从根结点算起，根为第一层，它的孩子为第二层…
深度：树中结点的最大层次数。
有序树（无序树）：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林：m(m>0)棵互不相交的树的集合
1.3 树的存储结构
树
双亲表示法
以一组连续空间存储数的节点，同时每个节点中，附设一个指示器指示其双亲节点在数组中的位置。找到双亲节点的时间复杂度：O(1)；找到节点的孩子的时间复杂度：O(n)。
| 下标 | data | parent |
|---|---|---|
| 0 | F | -1 |
| 1 | C | 0 |
| 2 | E | 0 |
| 3 | A | 1 |
| 4 | D | 1 |
| 5 | H | 2 |
| 6 | G | 2 |
| 7 | B | 4 |
| 8 | M | 6 |
增加长子域（该节点的最左边孩子的域）
在双亲表示法基础上增加该结点最左边孩子的指示器。
| 下标 | data | parent | firstchild |
|---|---|---|---|
| 0 | F | -1 | 1 |
| 1 | C | 0 | 3 |
| 2 | E | 0 | 5 |
| 3 | A | 1 | -1 |
| 4 | D | 1 | 7 |
| 5 | H | 2 | -1 |
| 6 | G | 2 | 8 |
| 7 | B | 4 | -1 |
| 8 | M | 6 | -1 |
增加右兄弟域
见名知意。
孩子表示法1
根据树的度来确定每个节点指针域的个数，缺点是当树中各节点的度相差很大时，浪费空间，因为很多节点的指针域是空的。
方式1
孩子表示法2
每个节点指针域的个数等于该节点的度，专门取一个节点的位置来存储节点指针域的个数。如某个结点有两个孩子，则有两个孩子领域，一个数字域。缺点是克服了空间上的浪费，但由于每个节点的链表是不相同的结构，还要维护节点的度的数值，在时间会有损耗。
方式2
孩子表示法3
把每个节点的孩子结点排列起来，用单链表作为存储结构，n 个节点 n 个链表，如果为叶子节点，该单链表为空。再将 n 个头指针组成一个线性表，采用顺序存储结构，存放到一维数组中。
方式3
孩子双亲表示法
孩子双亲表示法
孩子兄弟表示法
任意一棵树，它的节点的第一个孩子如果存在就是唯一的，它的右兄弟也是唯一的。因此设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟。
2 二叉树
2.1 二叉树的基本概念
image.png
二叉树
- 二叉树是每个结点最多有两个子树的树结构，且子树有左右之分，不能颠倒。
- 二叉树的第i层最多有
2^(i-1)个结点 - 深度为k的二叉树至多有
2^k-1个结点
满二叉树
- 深度为k，并且含有
2^k-1个结点的二叉树 - 对于编号为 i 的结点，如果有双亲，双亲为 i/2 向下取整；如果有左孩子，左孩子编号为 2i，如果有右孩子，右孩子编号为 (2i + 1)
完全二叉树
对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
2.2 二叉树的遍历
树
先序遍历：根节点—— 左子树——右子树
中序遍历：左子树——根结点——右子树
后序遍历：左子树——右子树——根结点
3 二叉查找树
又称为二叉排序树，其性质是：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 左、右子树也分别为二叉排序树；
- 没有键值相等的节点。
4 AVL树
AVL（Adelson-Velsky-Landis）二叉树，是自平衡的二叉查找树。AVL树本质上还是一棵二叉搜索树，它的特点是：
- 本身首先是一棵二叉搜索树。
- 每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
5 伸展树
伸展树（Splay Tree）也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。
6 2-3树
- 2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）。
- 一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子。
- 一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
- 并且2-3树中所有的叶子都在同一层次上。
7 B树
B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。B树为系统最优化大块数据的读和写操作。B树算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
结构
4阶B树
B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
8 B+树
B+树
B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中；
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录；
与B树的区别
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
9 红黑树
红黑树是具有下列着色性质的二叉查找树：
- 每一个节点或者着成红色，或者着成黑色。
- 根是黑色的。
- 如果一个节点是红色的，那么它的子节点必须是黑色的。
- 从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。
