Question

数据结构-树的一些概念

Answer 1

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

满二叉树与完全二叉树

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

性质

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

各种平衡树

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

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