tree.md

二叉搜索树

一种树形结构的数据结构

1. 特点

   • 根节点的左子树上的所有节点都比根节点小
   • 根节点的右子树上的所有节点都比根节点大
   • 每个子节点也是一个二叉搜索树
   • 所有节点上没有重复的值

2. 时间复杂度

   • 最优

     从上面列出来的特点其实就可以看出二叉搜索树其实是基于二分查找的原理，因为所有比当前节点小的值都在左边，大的值则在右边。所以每次查找都是O(logn)，而插入和删除也都是在查询的基础上进行，只需要改动每个节点的指针即可，所以也是O(logn)。

     比如下列这张图就是一棵4层二叉搜索树，所以从根节点开始最多只要查4次就可以查到想要的值，因为最多只有4层。

     

   • 最差

     上面是在整棵树比较平衡的情况下来进行查找，有时候数据的插入会造成一种很极端的情况，比如下面这棵树，所有的节点都只有右子树，整棵书直接退化成了线性结构，这个时候查找，插入和删除都会是O(n)。

     

---

平衡搜索树(B树)

在二叉搜索树的基础上解决了树不平衡的问题，是指的一类树，具体的实现有AVL树、红黑树和B树等，每种树的实现都不一样，解决平衡的方式也不同，这里以B树为例子。

1. 特点

   B树的非叶子节点可以存拥有可变数量的子节点，随着子节点的增删，这些内部子节点也会合并或者分离，这样B树保持平衡就不需要频繁修改节点之间的关系了，所以就需要键隔开，也就是下面说的有k个子节点的非叶子节点拥有k−1个键的含义，例如，3个子节点需要两个键隔开，但是可能会造成一些内部节点的空缺，浪费空间。

   常见的有2-3 B树，即每一个内部节点只能有2或3个子节点，其中[6]，[8]和[10,11]，7和9就是分割这三个子节点的键，所以本质上键就是父节点上的值。

   

   所以B树在二叉搜索树的基础上还有着下面的特点。

   • 每一个节点最多有m个子节点，m是树的阶层
   • 每一个非叶子节点(除根节点)最少有m/2个子节点
   • 如果根节点不是叶子节点，那么它至少有两个子节点
   • 有k个子节点的非叶子节点拥有k−1个键
   • 所有叶子节点都处于同一层

2. 时间复杂度

   • 最优和最差

     因为B树的特性就是提前将内部子节点的数量维持在一个范围内，并且还保证了所有叶子节点都处于同一层，所以整棵树一定是完全平衡的，所以查询，插入和删除一定是O(logn)。

---

B+树

在B树的基础上进行了改进，B树本身就是适用于数据库和文件系统的存储，B+树则是针对这方面进行优化和改进。

1. 特点

   它所有的数据都是放在叶子节点中，也就是最下面那层，而非叶子节点中只存放键，这样可以存放更多的键，其实键就可以理解为索引。正因为每层可以存更多的索引值，也就是子节点会越多，整棵树层级会更小，更矮，搜索更快，此外B+树的叶子节点是互相相连的，并且是有序的，所以在范围查询的时候性能也非常好。

   • 有k个子节点的非叶子节点拥有k个键(B树是k-1个键)
   • 节点的关键字表示的是子树中的最大数或最小数，在子树中同样含有这个数据
   • 叶子节点包含了全部数据，同时符合左小右大的顺序

   

2. 时间复杂度

   • 最优和最差

     因为是在B树的基础上进行改进和优化，主要的原理还是差不多，所以查询，插入和删除也是O(logn)。