数据结构和算法——二叉树、AVL树、B树、红黑树总结
转载：原创链接：https://blog.csdn.net/wanderlustLee/article/details/81297253
二叉查找树
二叉查找树是一种排序树，其中左节点小于根节点，右节点大于根节点，也称为二叉查找树。也叫BST，英文二进制排序树。
二叉查找树比普通的树搜索速度快，搜索、插入和删除的时间复杂度为O(logN)。但是二进制查找树有一个极端的情况，就是会变成线性链表结构。此时，时间复杂度变为O(N)。为了解决这种情况，出现了二元平衡树。
平衡二叉树
平衡二叉树叫做平衡二叉查找树，也叫AVL树。它是一棵自我平衡的树。
AVL树还规定左节点小于根节点，右节点大于根节点。还规定左子树和右子树的高度差不能超过1。这确保了它不会成为线性链表。AVL树搜索稳定，搜索、插入、删除的时间复杂度为O(logN)。然而，为了保持自身的平衡，在插入和删除节点时需要频繁地旋转节点。
AVL树的每个节点只能存储一个元素，每个节点只有两个子节点。搜索时，需要多个磁盘IO(数据存储在磁盘中，每次查询都是将磁盘中的一页数据添加到内存中，树中的每一层节点存储在一页中，而不同层的数据存储在不同的页中。)这样如果需要多级查询，就需要多个磁盘IO。为了解决AVL树的这个问题，出现了B树。
B树
B树也叫平衡树，也叫B树，英文是Blance-Tree。是一棵多路径平衡树。
M阶的B树规定：
根节点至少有两个子节点。
每个中间节点包含k-1个元素和k个子节点，其中m/2=k=m。
每个叶节点包含k-1个元素，其中m/2=k=m。
的所有叶节点都位于同一层。
每个节点中的元素是从小到大排列的，节点中的k-1个元素正好是k个子节点包含的元素的范围划分。
每层B树存储的节点更多，从AVL树的“瘦高”到“矮胖”。磁盘IO的数量可以相对减少。MongoDB的索引是通过B树实现的。
b树也是一种自平衡树，在插入和删除时需要旋转节点。
然而，B树的搜索是不稳定的。最好的情况是在根节点找到它，最坏的情况是在叶节点找到它。此外，B树在遍历上比较麻烦。因为需要按照中间顺序遍历，所以也会执行一定的磁盘IO。为了解决这些问题，B树应运而生。
B+树
存储在B树每个非叶节点中的元素仅用于索引，所有数据都存储在叶节点中。
M阶的B树规定：
具有k个子树的中间节点包含k个元素(B-树中的k-1个元素)。每个元素不存储数据，只用于索引。所有数据都存储在叶节点中。
的所有叶节点都包含所有元素的信息和指向包含这些元素的记录的指针，并且叶节点本身根据关键字的大小按照从小到大的顺序进行链接。
的所有中间节点元素同时存在于子节点中，这是子节点元素中最大(或最小)的元素。
因为存储在非叶节点中的元素不存储数据，所以每一层可以容纳更多的元素，也就是说，磁盘中的每一页可以容纳更多的元素。这样，搜索时磁盘IO的数量就会减少。
此外，B树的搜索是稳定的，因为所有的数据都在叶节点。每个叶节点还通过指针指向形成一个链表结构，所以遍历数据会简单得多。
B树的插入和删除与B树相似。
红黑树
红树林也叫RB树，RB-Tree。是一个自平衡的二进制查找树，其节点是红色和黑色的。它没有严格控制左右子树的高度差或节点数小于等于1。也是解决二进制查找树极端情况的数据结构。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/100413.html