002-数据结构与算法-树

二叉树

什么是二叉树

二叉树就是每一个节点,最多只有两个子节点的树。这两个子节点分别是左子节点和右子节点。

特殊的二叉树

  • 满二叉树:每个节点都有两个叶子节点。
  • 完全二叉树:所有叶子节点都在最底下两层,最下一层的叶子节点要么是满的,要么靠左排列,倒数第二层的叶子节点是满的。

下图中2号是满二叉树,3号是完全二叉树。

二叉树的存储方式

  • 链表存储。

    每个节点包含三个字段,当前数据,做节点指针,右节点指针,如下图:

  • 数组存储

    根节点存储在下标i=1的位置,左节点存储在2i,右节点存储在2i+1,如下图;

https://wangtao-1256981172.cos.ap-guangzhou.myqcloud.com

链表存储方式简单易懂,但是比较浪费内存。

数组存储省内存,尤其是二叉树,节点都存储在连续的下标中。但是这种方式不适合存储数据量较大的树,因为数组需要连续的内存空间。

二叉树的遍历方式

根据父节点在遍历过程中的位置,可以分为前序、中序、后序三种方式。

前序遍历:父节点->左节点->右节点 中序遍历:左节点->父节点->右节点 后序遍历:左节点->右节点->父节点

三种遍历方式的示意图:

二叉查找树

二叉查找树是一种特殊的二叉树,用在快速查找数据的场景,其要求:树中的任意一个节点,都要大于其左子树(注意是树不是节点)所有的节点,小于其右子树的所有节点。

二叉查找树的查找操作

从根节点开始,取出当前节点的值A,与要查找的值X做比较。

  1. 如果A与X相等,则返回。
  2. 如果A比X大,则取出A的左子节点,继续与X比较。
  3. 如果A比X小,则取出A的右子节点,继续与X比较。

直到最后找到X在树中的位置,或者树中不存在X。

二叉查找树的插入操作

首先执行查找操作,找到与插入值X最接近的节点A,判断A是否是叶子节点。

  • 如果是叶子节点,则将X当做A的子节点直接插入。
  • 如果不是叶子节点,则需要对A的子节点做一列迁移操作。

二叉查找树的删除操作

首先执行查找操作,如果存在与删除值X相同的节点,则判断该节点是否叶子节点。

  • 如果是叶子节点,直接删除该节点。
  • 如果不是叶子节点,则需要对该节点的子节点做一系列迁移的操作。

时间复杂度分析

二叉查找树的时间复杂度,与树的高度成正比,在相同数据的情况下,树越高,时间复杂度也就越高,例如下图的三棵树。

这三棵树存储的数据是一样的,但是第1棵树已经退化成了一条离岸边,而第3棵树相对而言更加平衡一些。

从时间复杂度上将,第3棵树无论是查询、删除、还是插入,复杂度都是最低的。

红黑树

红黑树的实现非常复杂,如果不是专门研究算法的同学,其实并不需要去弄懂他,只需要记住红黑的特点以及适用场景就可以了。

  • 特点。红黑树是特殊的二叉查找树,其出现的目的就是希望树在经过插入和删除操作之后,仍然能够尽量保持平衡,以降低查询、删除、插入操作的时间复杂度。
  • 适用场景。 需要频繁动态更新树节点的场景。
  • 与跳表的比较。两者的插叙、删除、插入操作时间复杂度都是O(logn),红黑树出现时间更早,应用更广。跳表实现逻辑更简单。

B+树

B+树广泛应用于数据库的索引中,例如MySQL的索引就是基于B+树实现。

B+树特点:

  • 树中的节点并不存储数据本身,而是存储子节点的数据范围。
  • B+树也可以称为M叉树,与二叉树相比,二叉树只有两个分叉,而B+有M个分叉。因为B+树一般用来存储大量的数据信息,是放在硬盘中的。树的分叉越多,可以降低树的高度,减少从硬盘读取数据的次数。
  • B+的M取值也有讲究,在选择M大小的时候,要尽量让M个叶子节点的大小等于操作系统中一页的大小。因为操作系统从硬盘读取数据是一页一页读取的。
  • 通过链表将叶子节点串联在一起。方便按照区间查找数据。
上篇502 Maven-标准目录&Profile&POM
下篇002-数据结构与算法-哈希算法