树(数据结构), since 2020.02.07

作者: Mc杰夫 | 来源:发表于2020-02-09 13:57 被阅读0次

树结构在数据库设计中扮演重要作用。

基本概念：

树叶和分支节点：没有子节点的节点称为树叶，其余都是分支节点。

(节点的)度数degree: 一个节点的子节点个数。

层: 根的层数为0，位于k层的节点，其子节点是k+1层的元素。

高度(or深度): 树中节点的最大层数，只有根节点的树，其高度为0.

满二叉树：二叉树中所有分支节点的度数为2. (性质：树叶比分支节点多一个。)

扩充二叉树：对已有二叉树T加入足够多的新叶节点，使T的原有节点都变为度数为2的节点，形成的新二叉树. 分为内部节点和外部节点。空树的扩充二叉树规定为空树。

扩充二叉树都是满二叉树(?)

完全二叉树：共h层，0- h-1层的节点数是2^(h-1).如果最下一层的节点不满，则所有节点在左边连续排列，空位都在右边。此为完全二叉树。(除最下两层外，其余都是度数为2的节点。节点数为n的完全二叉树，其高度是不大于log2(n)的最大整数。)完全二叉树可自然的存入一个连续表。

遍历(traverse): 深度优先、宽度优先

深度优先：根节点P左子节点L右子节点R，先根遍历顺序PLR，后根遍历顺序LRP，中序遍历LPR。

宽度优先：按路径长度由近及远的访问节点，亦即按层次访问树的各层节点。用队列(Queue)实现宽度遍历。

二叉树的list实现：

atree = [root, lleaf, rleaf] 其中的lleaf和rleaf都可以是一个子树

用二叉树实现表达式求值。

堆(heap)及性质：用树形结构实现的优先队列，完全二叉树。任意节点保存的数据，在优先级上优于或等于其子节点的数据。从根到任意叶的路径，优先级(非严格)递减。堆中最优先数据在根节点，检索复杂度O(1)。

插入元素：向堆(完全二叉树)的结尾加入一个元素，此时二叉树不是堆。新加入元素和父节点做对比，如果新的优先级高就与父节点交换，并重复该过程；否则结束插入元素的过程。复杂度O(log2(n)).该过程称为向上筛选。

弹出元素：弹出优先级最高的元素，即堆顶的元素。弹出后堆顶空缺，从堆的尾部取出最后一个元素放在堆顶，并比较堆顶和两个子节点，将优先级最高的放在顶点，此时原来处在堆尾的点就下移，重复这个过程直到堆形成。称为向下筛选。复杂度O(log2(n)).

堆的应用：数组排序。

*非递归的遍历方法(没看)

*用生成器函数遍历(没看)

2020.02.08 skip

2020.02.09
Huffman tree

路径长途：根节点到叶节点的路径长度之和，i.e., 沿途节点个数(含根节点，不含终点节点)

用E = { $l_{i}$ }表示。

W = { $w_{i}$ } 是n个叶节点的值(or权重).

带权扩充外部二叉树的外部路径长度WPL = $\sum\nolimits_{a}^b w_{i} l_{i}$

当扩充二叉树T以W为权，而T的WPL在所有这样的扩充二叉树中达到最小，T被称为最优二叉树/Huffman二叉树。

构造Huffman二叉树：

1 从W中找出最小的两个 $w_{i}$ 形成一棵二叉树，叶节点是两个 $w_{i}$ ，根节点是他们的权重之和。

2 用1生成的根节点权重代替生成这个根节点的两个叶节点放回W

3 重复1/2，直到生成一棵树。

实现：优先队列。

算法分析：略。

Huffman编码：略

树(二叉树的扩展)：分为有序树和无序树。两棵树按无序树观点来看相同，但按照有序树的观点看可能不同。

树的结点度数是连接子树的个数。一棵树的度数定义为该树中度数最大的结点的度数。

树的性质：

1 度数为k的树，第i层至多有 $k^i$ 个结点

2 度数为k，高度为h的树，至多有...个结点(计算方法: 等比数列求和)

3 n个结点的树里n-1条边。(除了根节点，每个点都有一条边连接父节点，并且这些边不重合.)

4 n个结点的k度完全树，高度h是不大于 $\log_k n$ 的最大整数。

二叉排序树：

一种结点存储数据的二叉树，有如下性质：

1 根节点保存一个数据项和其关键码(value & key)

2 如果有左子树，则左子树保存的所有关键码，都小于(或不大于)根节点的关键码；

3 如果有右子树，则右子树保存的所有关键码，都大于根节点的关键码；

4 非空左子树/右子树也是二叉排序树；

5 中序排列这棵二叉树得到的关键码序列是递增序列。

检索：从上到下依次比较结点的关键码，如果比结点关键码大，则向右，小则向左。

插入：(假设与树中key重合，则新值代替旧值)从根节点开始，与结点的key比较，当应该向左走而左子树为空时，则添加成左子树；当应该向右走而右子树为空时，则添加为右子树；当与结点key重合，则更新结点的key-value。

删除：设删除的点是c，其父节点为p，设c是p的左子树(右子树情况以此类推)

1 如果c没有结点，则直接删除c，p的左子树更新为None；

2 如果c没有左子树，则删除c，c的右子树作为p的左子树；

3 如果c有左子树(有无右子树操作相同)，则删除c，找出c的左子树中的最右结点r(从c开始往右下走，第一个没有右子树的结点?)。[用c的左子结点代替c称为p的左子结点，c的右子树作为r的右子树](该表述不太明白).给出我的思路: c的最右结点r取代c，原r的位置空出，对r的左子树(如果有)，从步骤1开始迭代执行。

复杂度分析：

2020.02.10

如果树形非畸形，即链条从上到下的没有分支，则检索的复杂度是O(n)；而如果树形良好，即高度与结点数目成对数关系，则检索的复杂度是 $O(\log_2 n)$ .

数据更新、插入和删除的操作都是在检索的基础上做常数时间操作，复杂度与检索相同。

最佳二叉排序树：

最佳的标准应该基于检索效率。平均检索长度的概念。

设计最佳二叉排序树依据：检索关键码(key)的频度(次数，也称分布?).

假设二叉树排序树由n个内部节点和n+1个叶节点构成，其中不管内部节点构成的二叉树为何形状，加入外部节点扩展后，形成扩充二叉树。

key的平均检索长度 $E(n)$ 有

E(n) = \frac{1}{w} [\sum_{0}^{n-1} p_{i}(l_{i}+1) +\sum_{0}^{n} q_{i} l_{i}^{'} ]

其中1/w = sigma p_i + sigma q_i

l_i是内部节点i的层数，l_{i}^{'}是外部节点

最优二叉排序树是使平均检索次数E(n)达到最少的二叉排序树。

最简单情况：所有key的检索频度相等。公式略。

结论是最低的树最好。

构造最简单情况的最优二叉排序树：

设a按关键码排序的字典，

1 low = 0, high = len(a) - 1

2 m = (low + high) /2

3 a[m]存入二叉树的根节点；片段a[low, m-1] 作为a[m]的左子树，a[m+1, high]作为a[m]的右子树；片段为空，则None，表示空树。循环此过程得到最优二叉排序树。由排序字典构成排序树的复杂度O(n)，考虑到生成排序字典的复杂度最低是O(nlogn)，则由任意一组关键码出发，构建最优二叉树的复杂度是O(nlogn).

一般情况的最优二叉树：用动态规划寻找。

平衡二叉(排序)树 a.k.a. AVL树：

最优二叉树的缺点：需要提前知道key的分布并且字典是静态，任何加入或删除的操作都会破坏树的结构。

平衡二叉树亦称AVL树，与其结构类似的有红黑树和B树。

定义：特殊的二叉排序树，或空树，或左右子树都是平衡二叉排序树，其左右子树的高度最大差距是1。(我的理解：平衡二叉排序树中的任何子树，其根节点的左右子树高度差都不超过1.)

BF平衡因子(balance factor): 对结点定义，该结点的左子树高度与右子树高度差，左高-右高。对平衡二叉树来说，BF=-1,0,1.即决定值不超过1. (每个结点如果能同时记录该点的最高高度和BF就非常好了.)

平衡二叉树的树高h与结点数n的关系：推导

2020.02.12

用 $B_i$ 代表高度为 $i$ 的'临界'平衡二叉树，也就是相同高度 $i$ 的平衡二叉树中节点最少的。容易得到

# $B_0$ = 1, # $B_1$ = 2，从高度为2的临界平衡二叉树开始，都可以当做是一个根节点与高度为 $i-1$ 和 $i-2$ 的两棵临界平衡二叉树的组合。有下面推导式

# $B_i =$ # $B_{i-1}$ + # $B_{i-2}$ + 1

其中的1代表一个根节点。

Fibonacci数列 $F_i = F_{i-1} + F_{i-2}$

由数学归纳法可证(?)

# $B_i = F_{i+3} -1$

且 $F_i = 0.447\times 1.618^i$

树高 $h<\frac{3}{2} \log_2 n+1$ .

结论，与最优二叉树相比，最长路径的长度仅差一个常量，检索复杂度 $O(log n)$ .

对平衡二叉树的设计核心，是控制不同子树的高度差，保证高度和所存项数的对数关系，保证检索效率。

对平衡二叉树进行插入操作的再平衡

最小非平衡子树(minimum unbalanced subtree, MUS)：包含新插入结点位置的、根结点的BF非0的最小子树。

如果在MUS中插入新结点后，MUS扔保持平衡，并且高度不变，则整棵树的高度也不变。

插入新结点后，结构调整能够在子树内的一条路径上完成，插入的复杂度O(logn).

插入新结点如果MUS失去平衡的调整和恢复的情况分以下4种：

LL: MUS的左子树较高，新结点插到左子树的左子树

LR: MUS的左子树较高，新结点插到左子树的右子树

RL: MUS的左子树较高，新结点插到右子树的左子树

RR: MUS的左子树较高，新结点插到右子树的右子树

其中LL、RR的处理方式相似，LR、RL的处理方式相似。

LL的处理方式：

图中a是MUS的根结点，b的左右子树等高。

在没有插入新结点之前，各结点和子树的排列顺序是AbBaC。新结点插入子树A，形成A'。此时顺时针调整MUS，b取代a成为根节点，b的右子树成为a的左子树，a成为b的右子树。调整后的子树和结点排序时A'bBaC。与调整前保持一致。(2020.02.18补充我的理解：在树的下面有一个平面，这个树在平面上的project的顺序就是树中节点的排列顺序。调整二叉树失衡之后得到的新树，只要其project顺序与原project顺序相同即可。)

a.left = b.right

b.right = a

a.bf = b.bf = 0

RR的情况：

a.right = b.left

b.left = a

a.bf = b.bf = 0

LR的调整:

插入新结点前的排序时AbBcCaD。新结点插入到B或C的结点之下，从而导致c为根节点的子树失衡。

失衡之后的状态如图(2)所示。此时调整为(3)所示的关系，插入后的排序时AbB'(B)cC(C')aD，顺序没有变化，高度没有变化，新形成的子树仍然是平衡二叉树。

b = c.left

b.right = c.left

a.left = c.right

c.right = a

c.left = b

之后调整各结点bf(略略略).

AVL平衡二叉树的插入操作复杂度O(logn).

动态多分支排序树：

B/B+树: placeholder....

2020.02.19

红黑树：一种平衡二叉树，满足5个性质

1 每个节点是红色或者黑色；

2 根节点是黑色；

3 每个叶子节点(nill)是黑色(注意这里即便叶节点为空，也要标注在图中)；

4 每个红色结点的叶子节点一定是黑色；

5 任意一个结点都叶子结点一定包含相同数量的黑色结点。

插入和删除结点后，如果平衡二叉树失衡，则需要通过变色和旋转调整树。

左旋转

以某点P为支点旋转，其右子节点V旋转后称为P的父节点，V的左子节点称为P的右子节点，V的右子节点不变，V的新左子节点是P，如下图[2]

红黑树左旋转

右旋转

以某点P为支点旋转，其左子节点F旋转后称为P的父节点，F的右子节点成为P的左子节点，F的左子节点不变，F的新右子节点是P，如下图[2]

红黑树右旋转

旋转之后根据5个性质对变化后的节点变色。

reference:

1 裘宗燕，数据结构与算法 Python语言描述.

2 https://www.jianshu.com/p/e136ec79235c

3 http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml

树(数据结构), since 2020.02.07

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读