先看一张表：
树的种类
没想到竟然有这么多树，相对而言，重要一点的就是二叉树，AVL树，红黑树，B树，B+树，咱们就从简单的到深入的慢慢讲
一、二叉树
二叉树是每个节点最多有两个子节点的树结构，二叉树里面还分：
满二叉树：顾名思义，每一层都是满的，因此深度为k的满二叉树的节点数为2^k-1个
完全二叉树：完全二叉树为除了最后一层都是满的，并且最后一层节点都集中在左边的树
一个节点的子节点数为节点的度，对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1
二叉树理论上是二分法的所以查找效率为logN，但是因为不是平衡的，所以有可能在更新过程中变成是单链的，效率会降低为N
对于二叉树的遍历，有前序中序后序，使用递归法非常容易理解但是调用栈太深了，容易出现效率太低甚至溢出的情况，因此可以采用非递归的方法，非递归其实也是用到了栈来存储一路走下来的节点，中序遍历最简单，后续遍历会难一些，如果需要可以留言，我把思路和代码写出来。
二、AVL树
AVL树即平衡二叉树，又叫二叉排序树，之所以是平衡的，是因为它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡的。
平衡二叉树的查找效率一定是logN的，因此适合用来搜索。
在插入和删除的时候要想保持一颗树的平衡性不是那么容易的，需要先从上往下遍历找到位置，插入的时候还需要在从下往上遍历使它保持平衡，保持一颗树平衡的方法有左旋和右旋，双向旋转无非就是先左后右或者先右后左的组合。
那么如何知道它不平衡了呢，平衡二叉树引入了一个平衡因子，其实就是该节点左右子树的高度差，该因子的值为0，-1，1视为平衡，其他时候为不平衡，就需要做旋转操作。
三、红黑树
红黑树也是一种自平衡二叉树，它的定义比较复杂：
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
性质5.每个叶子的节点都是黑色的null节点
保持红黑树的平衡挺蛋疼的，需要旋转加变色的配合，旋转通过AVL树的练习倒是容易理解，但是变色因为要同时满足5个性质，所以emmmm
四、B树
B树又称B-树，它已经不是二叉树了，可以称为m叉树，m为节点的最大子节点个数，m>=3，非根非叶子节点至少有m/2个（向上取整）分支。如果一个结点有n-1个关键字，那么该结点有n个分支。
B树的节点中包含关键字和数据，这是和B+树，查找的关键字如果等于非叶子的关键字那么就可以返回了。
B树的插入有可能导致个数超过限制，因此通过分裂操作来保持满足规则，同理，删除结点的时候导致个数小于m/2，可以通过合并来保持。
五、B+树
对标B树，最大的特点就是信息只保存在叶子节点中，中间节点不带数据，只作为索引，并且叶子节点包含了全部关键字，父节点的关键字在子结点中为该子树的最大值。因此B+树要想得到数据，必须要查找到叶子节点才能返回。
B+树的叶子节点同时还形成一个有序列表。
B树和B+树的区别：
1、B+树的中间节点不带数据，因此能存储更多内容，所以B+树更加的矮胖，查询的IO次数就会更少
2、所有查询都要查找到叶子节点，查询性能稳定。
3、所有叶子节点形成有序链表，便于范围查询。
网友评论