【树合集】

二叉树：

满二叉树：每一层的节点都达到最大值，如果树高h，节点总数有2^h-1。
完全二叉树：树高为h，前h-1层节点都是最大值，最后一层h不满且从左到右连续。

存储方式：顺序存储（数组）和链式存储（链表）。

二叉搜索树：

特点：左节点值<跟节点的值，右节点值>跟节点的值，左右子树都是二叉搜索树，中序遍历是升序。

增删改查效率：因为增删改前都需要查询节点值，所以查询的时间复杂度就是增删改的时间复杂度，最好时间复杂度是O（logn），最坏时间复杂度是O（n）是因为退化成链表了。

删除操作（ps：删除情况多较重要，而增删改都是递归操作）：

• 删除根节点：特判一下是根节点，然后找寻左子树的最大节点，或者右子树的最小节点进行替换删除。
• 删除孩子节点：该孩子节点的父节点指向nullptr即可。
• 删除中间节点：托孤，该中间节点的父亲领养一个或两个孙子。

平衡二叉树AVL：

特点：首先平衡二叉树的前提是二叉搜索树（中序遍历有序说明是二叉搜索树），且每个节点的左右子树的高度差绝对值（平衡因子）不超过1。

优点：时间复杂度为O(logN)，解决了二叉搜索树成为链表的缺点，因为平衡因子使节点均匀分布，降低了树的高度，提高查询效率。

缺点：如果对AVL树做一些结构修改，插入删除等操作，性能是十分低下的，因为保证平衡因子需要多次旋转，最差的情况是可能一直要旋转持续到根的位置。

ps：旋转分四种情况：左旋，右旋、左右双旋、右左双旋。

红黑树

是一个自平衡的二叉搜索树，在插入和删除后能够通过左旋和右旋以及重新着色保持树的平衡，增删查的时间复杂度是O（logn）

特点：

• 每个节点都有颜色，黑色或者红色。
• 跟节点和叶子节点都为黑色。
• 红色节点的左右孩子节点都为黑色。
• 跟节点到叶子节点上黑色节点的个数一致。

红黑树和平衡二叉树的比较？

查询：选平衡二叉树

插删：选红黑树

• 平衡二叉树的平衡规则相比于红黑树要严格，所以红黑树的高度会略高于平衡二叉树，所以平衡二叉树查询的时间复杂度要快一些。
• 当插入和删除操作进行时，平衡二叉树需要多次旋转达到严格的平衡规则，而红黑树的平衡规则不算严格所以最多需要两次旋转就可以达到平衡状态，所以黑红树插入和删除的时间复杂度要快一些。

前缀树：

特点：

• 除了根节点外每个节点都包含一个字符
• 每个节点的所有子节点，包含的字符不同
• 从根节点到某节点：字符连接起来可以形成该节点的字符串

应用：利用字符串的公共前缀来减少查询时间，减少无所谓的字符比较，从而提高查询效率

B树：

B树是一个平衡多叉树，为什么不采用AVL树存储MySQL的索引文件呢，是因为随着索引文件增多，AVL树的树高会逐渐变高，那么根据索引读取数据的速度取决于磁盘IO次数，也就是树的高度（一次磁盘IO读取一个节点），采用B树也就是平衡多叉树可以降低树的高度，减少磁盘IO的次数，提高效率。

特点：

叶子节点和非叶子节点都存储着索引键值key和数据data。

B树的范围查询是中序遍历，没B+树好。

B+树：

B+树是MySQL关系型数据库innodb存储引擎下的存储索引文件的数据结构。首先它也是一个平衡多叉树，那为什么选择它呢？因为B+只有叶子节点存储索引键值key和数据data，非叶子节点存储的都是键值key，所以B+树的高度要比B树还要矮，磁盘IO次数更少，查询效率更高。

特点：

叶子节点存储键值和数据，非叶子节点只存储键值。

B+树的范围查询依靠叶子节点之间形成的双向链表。

ps：

所以B+树的范围查询比B树的中序遍历效率高太多，B+树用于MySQL的innodb存储引擎，而B树可以考虑单个索引的查询，用于nosql的MongoDB存储引擎。