数据结构树的种类

Answer 1

性质：二叉树是一种拥有根节点的树，每个节点最多可有两个子节点。对于非空二叉树，若叶节点的数量为n0，分支度为2的节点数量为n2，则有n0 = n2 + 1。
满二叉树与完全二叉树：满二叉树是一种特殊的二叉树，其中每个节点都有0个或两个子节点。完全二叉树是一种深度为k，且有2k-1个节点的二叉树。
二叉堆：二叉堆适合用数组存储，数组中的元素a[i]的左子节点是a[2*i+1]，右子节点是a[2*i + 2]，父节点是a[(i-1)/2]。二叉堆具有堆序性质，即每个节点的值都小于其左右子节点的值。因此，二叉堆中最小的值位于根节点。
平衡树：平衡树是对二叉查找树的改进。一般的二叉查找树查询复杂度取决于目标节点到树根的距离（即深度），当节点深度普遍较大时，查询的均摊复杂度会上升。平衡树通过使所有叶节点的深度趋于平衡来改进这一点。
各种平衡树：AVL树是一种自平衡的二叉查找树，它的发明者是G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文中首次公开描述了这一数据结构。鲁道夫·拜尔是慕尼黑工业大学信息技术系的名誉教授，自1972年以来，他因发明数据结构而闻名，包括B树（与Edward M. McCreight合作）、UB树（与Volker Markl合作）以及红黑树。他曾在2001年获得美国计算机协会SIGMOD Edgar F. Codd年度创新大奖。