数据结构-树的一些概念
性质
二叉树是一个有根树,并且每个节点最多有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年度创意大奖得主。
2019-06-26 广告