简述数据结构中的常见树
阅读数:92 评论数:0
跳转到新版页面分类
算法/数据结构
正文
一、二叉树
Binary Search Tree
1、二叉树性质
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
（2）若它的右子树不空，则右子树上的所有结点的值均大于它的根结点的值。
（3）它的左、右子树也分别为二叉查找树。
（4）可以是空树
二、平衡二叉查找树
对于二叉树，最极端的情况就是线性插入，使得整棵二叉树退化为一条链。
由数学家Adelse-Velskil和Landis提出，并根据二者的英文名称为AVL树。
1、性质
（1）可以是空树。
（2）若不为空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1。
2、解释
因为平衡二叉树查询性能和树的层级（h高度）成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、AVL、RBTree(红黑树)、Splay(伸展树)，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找。
| AVLTree |
追求极致完美，任何两子树的高度差 ≤ 1 ，增删时调整 |
| Splay |
通过巧妙设计的四种旋转来调整树高，增删查都伴随调整 |
| Treap |
通过随机权值强行模拟随机数据插入的二叉树，增删时调整 |
| SBT |
通过子树size域的差距表现来进行旋转维护，增时调整 |
| 替罪羊树 |
暴力美学，必要时直接拍平子树，然后从中间给拎起来重建二叉树 |
| RBTree |
复杂精密的平衡树，增删时调整 |
三、B树
B树也称为B-树，它是一棵多路平衡查找树，一棵B树需要指定它的阶树，阶数表示了一个结点最多有多少个孩子，当m=2时，就是前面说的二叉搜索树。一棵m阶的B树定义如下：
（1）每个结点最多有m-1个关键字。
（2）根结点最少可以只有1个关键字。
（3）非根结点至少有Math.ceil(m/2)-1个关键字
（4）每个结点的关键字都按照从小到大的顺序排列，每个关键字的左子树的所有关键字都小于它，而右子树中的所有关键字都大于它。
（5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
它是B树的变体，有着比B树更高的查询性能。一个m阶的B+树具有如下几个特征：
（1）有k个子树的中间节点包含有k个元素（B树中是k-1个元素）
（2）叶子结点依关键字的大小自小到大顺序链接。
（3）所有的中间节点都同时存在于子节点，在子节点元素中是最大或最小的元素。