数据结构-树的一些概念

二叉树

性质
二叉树是一个有根树，并且每个节点最多有2个子节点。非空的二叉树，若树叶总数为 n0，分支度为2的总数为 n2，则 n0 = n2 + 1。

图片.png
遍历

1. 前序遍历：根 > 左 > 右
2. 中序遍历：左 > 根 > 右
3. 后序遍历：左 > 右 > 根

满二叉树与完全二叉树

1. 满二叉树
   如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

   
   full_binary_tree.png

2. 完全二叉树
   一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

   
   complete_binary_tree.png

3. 堆结构

最大堆： 所有的子节点都不比父节点大
最小堆： 所有的子节点都不比父节点小

二叉堆：非常适合用数组进行存储，对于数组中的元素 a[i]，其左子节点为 a[2*i+1]，其右子节点为 a[2*i + 2]，其父节点为 a[(i-1)/2]，其堆序性质为，每个节点的值都小于其左右子节点的值。二叉堆中最小的值就是根节点。

二叉查找树

性质

1. 若任意节点的左子树不空，则左子树上所有的节点值均小于它的根节点的值。
2. 若任意节点的右子树不空，则右子树上所有的节点值均大于它的根节点的值。
3. 任意节点的左右子树也分别为二叉查找树。
   中序遍历时，相当于升序排列

平衡树

性质
平衡树是对二叉查找树的改进。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。平衡树是使得所有叶子的深度趋于平衡。

各种平衡树

1. AVL树

注：AVL树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文An algorithm for the organization of information中公开了这一数据结构。

2. 红黑树

注：鲁道夫·拜尔(德语：Rudolf Bayer，1939年5月7日－)，自1972年以来一直是慕尼黑工业大学信息技术系的名誉教授。他因发明数据结构而出名: B-树（与Edward M. McCreight合作）和UB-树（与Volker Markl合作）以及 红黑树 。他是2001年美国计算机协会SIGMOD Edgar F. Codd年度创意大奖得主。

红黑树和AVL树的对比：

1. AVL树比红黑树检索更快，因为AVL树更加严格平衡一点。红黑树的插入和删除比AVL树更快。
2. AVL使用的存储空间要高于红黑树。（AVL树每个节点需要记录平衡因子或高度，这需要一个integer类型，红黑树每个节点只需要一个bit位来记录相关数据）
3. 红黑树大量的用于一些程序语言的类库中，如Java里的map，而AVL树大量用于需要高速检索的数据库中。