数据结构中的那些树

那些树

二叉树(binary tree)
满足每个节点的孩子均限制不超过两个的树称为二叉树. (数据结构 邓俊辉 5.1.2 二叉树)

有序树(ordered tree)
符合任一节点的所有孩子之间存在一线性关系的多叉树被称为有序树.

有序二叉树(ordered binary tree)
孩子节点以左,右区分的二叉树称为有序二叉树. (数据结构 邓俊辉 5.1.2 二叉树)

多叉树
树中各节点的孩子(或等价地, 分支)数目既不确定, 也没有上限的树称为多叉树. (数据结构 邓俊辉 5.1.3 多叉树)

二叉搜索树(binary search tree, BST), 又称(二叉查找树(binary search tree), 或者 二叉培训树(binary sort tree)). 本文中沿用二叉搜索树作为这一类树的名称(数据结构 邓俊辉 7.2 二叉搜索树).

平衡二叉搜索树(balanced binary search tree, BBST)
在不致影响二叉搜索书基本操作渐进复杂度的前提下, 适当放松标准之后的平衡性, 称为适度平衡. 就渐进的意义而言, AVL树, 伸展树, 红黑树, kd-树的树高都能保持在O\log(n)以内, 所以都可以称作平衡二叉搜索树.

AVL树(AVL tree, 1962年由G. M. Adelson-Velsky和E. M. Landis发明, 以他们名字的首字母命名.)
*平衡二叉树**(balanced binary tree),

伸展树(splay tree)

多路搜索树(multi-way search tree)

B-树
m阶B-树(B-tree),即m路平衡搜索树, 也称多路搜索平衡树.

红黑树(red-black tree)
红黑树的雏形于1972年由R. Bayer发明,命名为对称二叉B-树(sysmetric binary B-tree),后经L. J. Guibas 与 R. Sedgewick改进, 定名为红黑树(red-black tree)

kd-树
1975年由J. L. Bentley 发明.其名字来源于”k-dimensional”的缩写, 可以推广至任意k维欧式空间, 相应的分别称作2d-树,3d-树等等.

满树

平衡树

完全二叉树

二叉树

二叉树中每个节点的孩子均限制为不超过两个.

二叉搜索树

介绍

一颗二叉树是二叉搜索树, 当且仅当其中序遍历序列单调非降. (数据结构 邓俊辉 7.2.2节)

二叉搜索树 最好的情况下, 目标词条恰好在树根处或附近, 此时只需 O(1) 时间; 最坏的情况下, 在一个规模为n的二叉搜索树中, 目标节点的深度在最坏情况下可达 \Omega(n).

AVL树

介绍

在渐进复杂度的意义下, AVL树可始终将其高度控制在O(\log(n))以内, 从而保证每次查找,插入或删除操作均可在O(log(n))的时间内完成. (数据结构 邓俊辉 7.4 AVL树)

在AVL树中插入一个节点之后, 经过至多两次旋转即可使之恢复平衡.(数据结构 邓俊辉 7.4.2 节点插入)

在AVL树中删除一个节点之后, 可能干会出现”失衡传播”现象(即由于对失衡后代的重平衡而致使高层祖先失衡的现象). 因此在删除节点时, 至多需要操作O(log(n))个节点. 但是因为每次调整只需常数时间, 所以在重平衡方面花费短时间总量不会超过O(log(n)).

“3+4″重构

B-tree

介绍

m阶B-树(B-tree),即m路平衡搜索树, 也称多路搜索平衡树. 这里的B, 代表的是Balanced, 平衡的意思, 需要和二叉树的binary进行区分. 而且B-树一般是m阶, 而m一般大于等于2.

作为多路平衡搜索树的B-树可以被理解为二叉搜索树经”扁平化”之后的版本, 因此其管库(底层节点的数目)往往远大于高度.

红黑树

介绍

通过引入 n+1个外结点, 保证原树中每一结点(现称作内部节点)的左,右孩子均非空-尽管有可能其中之一甚至二者同时是外部节点. 在经过如此扩展之后, 由红,黑两色节点组成的二叉搜索树, 若同时满足:
1. 树根始终为黑色;
2. 外部节点均为黑色;
3. 一般的节点若为红色, 则其孩子节点必为黑色;
4. 从任一节点到根节点的沿途, 黑色节点的数目相等;
则称作红黑树(red-black tree).

其他

二叉树,有序二叉树和二叉搜索树,B-树的区别

二叉树仅仅是满足每个节点的孩子不超过两个的树, 并没有对孩子之间,孩子与父亲之间大小关系有限制.
而有序二叉树也仅仅只是在二叉树的基础上添加了左右之分, 并没有大小之分.

根节点, 子节点, 叶子节点, 内部节点

(树的)平衡性

反向B-树(reversed B-tree)

References

数据结构中各种树

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据