常见树的数据结构_树的数据结构有哪些

时间复杂度

O(1) 表示一次操作即可直接取得目标元素（比如字典或哈希表），
O(n) 意味着先要检查 n 个元素来搜索目标
常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n²),立方阶O(n³),k次方阶O(n^k),指数阶O(2ⁿ)。

O(log n)

二分搜索一定有某种行为使其时间复杂度为 log n。
最好情况下二分搜索的时间复杂度是 O(1)，最坏情况（平均情况）下 O(log n)。

设有 16 个元素的有序数组，最坏情况下

n就是我们所需要遍历的数组个数（16），底数是2，k就是时间复杂度（4）

但是 O(log2ⁿ)为什么会变成O(log n) 呢
logc^A（c为底数）为常数，由O的运算规则"O(C×f(N))=O(f(N))，其中C是一个正的常数"得O（loga^B）=O（logc^B）可知算法的时间复杂度与不同底数只有常数的关系，均可以省略自然可以用logN代替。

例

Binary Search Tree(时间复杂度 O(log n) )

最坏情况下的时间复杂度

二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NULL）。根结点是树中唯一父指针为NULL的结点，而叶子结点的孩子结点指针也为NULL。

在二叉搜索树中：
1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树。

AVL树（最先发明的自平衡二叉查找树）

在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树

引入对左右子树高度差有限制的平衡二叉树，保证查找操作的最坏时间复杂度也为O(logN)

红黑树是一种特化的AVL树（平衡二叉树）

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。

有了平衡二叉树，为什么还需要红黑树？

AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡
在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣
红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，整体性能优于AVL
红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
红黑树的红黑规则，保证最坏的情况下，也能在O(log_{2}N)时间内完成查找操作。

节点不是红色就是黑色，根节点是黑色
红黑树的叶子节点并非传统的叶子节点，红黑树的叶子节点是null节点（空节点）且为黑色
同一路径，不存在连续的红色节点

B树

M阶B树性质：

1. 根节点至少有两个子节点。
2. 其他节点至少有M / 2个子节点。
3. 每个节点最少2个key，最多M - 1个key。
4. 位于父节点两个key之间的子节点的值位于父节点两个key对应的value之间。

B树的弊端
除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。
（其他关联数组的实现，例如三元搜索树或者开散列哈希表，可以动态适应任意长度的键值）。

B+树

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。

B+树是B树的一种变形，比B树具有更广泛的应用，m阶 B+树有如下特征:
(1)每个结点的关键字个数与孩子个数相等，所有非最下层的内层结点的关键字是对应子树上的最大关键字，最下层内部结点包含了全部关键字。
(2)除根结点以外，每个内部结点有 到m个孩子。
(3)所有叶结点在树结构的同一层，并且不含任何信息(可看成是外部结点或查找失败的结点)，因此，树结构总是树高平衡的。

B树和B+树的区别

1.B树每个节点都会有数据域和关键字，而B+树是在非叶子节点是没有数据域的，所有数据与都在叶子节点中，并且各个叶子节点之间通过指针相连接。

2.B树的查询最好时间复杂度为O(1）最差O（log n），B+树的查询时间复杂度固定为O（log n）。

3.B树更适合查找某一频繁出现的数据，同时B树无法进行范围查找，而B+树可以进行范围查找，只需要找到叶子节点最小的数据然后通过链表O(N)的时间复杂度就能查找整个数据的范围。

4.B+树只需要遍历叶子节点便可以实现整棵树的遍历，包含关键字并有序存储，增删效率更高。