【数据结构】二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树

概述

二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点），没有限制节点的顺序。特点是简单直观，易于实现，但查找效率较低。

二叉搜索树（Binary Search Tree，BST）：在二叉树的基础上，左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值。特点是插入、删除和查找的平均时间复杂度为O(log n)，但如果树不平衡，可能会退化为链表，时间复杂度为O(n)。

平衡二叉树（Balanced Binary Tree）：在二叉搜索树的基础上，保持树的平衡，即左右子树的高度差不超过1。常见的平衡二叉树有AVL树和红黑树。特点是插入、删除和查找的时间复杂度为O(log n)，但维护平衡的代价较高。

红黑树（Red-Black Tree）：是一种自平衡的二叉搜索树，通过对节点进行着色和旋转操作来保持树的平衡。特点是插入、删除和查找的时间复杂度为O(log n)，并且对于任意节点，从根节点到达该节点的路径长度相等。

B树（B-Tree）：一种多路搜索树，每个节点可以有多个子节点。特点是适合存储在磁盘或其他外部存储设备上的大量数据，可以减少磁盘I/O操作的次数。

B+树（B+ Tree）：在B树的基础上进行了优化，非叶子节点只存储索引信息，所有叶子节点通过指针连接形成链表。特点是适合范围查询和排序，常用于数据库索引。

详解

结构特点：树的节点数目、子节点数目、节点之间的关系等。

平衡性：是否能够保持树的平衡，即节点的左右子树高度差是否有限制。

插入、删除和查找的时间复杂度：不同树对这些操作的时间复杂度不同，影响了树的使用场景。

存储和访问方式：不同树的存储方式和访问方式有所不同，适用于不同的应用场景。

二叉树（Binary Tree）

只是看起来是个树，乱序，查找数据得一个一个的找，所以没啥用。

二叉搜索树（Binary Search Tree，BST）

有序的，查找比二叉树要快，如图，找0005的话，从根节点开始，只需要寻找3次就能找到

 但如果是这样的，那就得找5次，这就退化成了链表

平衡二叉树（Balanced Binary Tree）

为解决退化问题，在二叉搜索树的基础上，通过旋转来保持平衡，使左右子树的高度差不超过1。

旋转方式

先看下每个节点里有什么

1、节点值：每个节点都包含一个值，用于存储数据。
2、左子树指针：指向节点的左子树的指针。
3、右子树指针：指向节点的右子树的指针。
4、父节点指针：指向节点的父节点的指针。这个参数在某些实现中可能会被省略。
5、平衡因子：平衡因子是用于判断节点平衡状态的指标，它是指一个节点的左子树高度减去右子树高度的差值。平衡因子可以为-1、0或1，分别代表左子树高度比右子树高度小1、相等或大1。

情况与旋转方式

LL（左-左）情况：0004作为根节点，右旋操作

RR（右-右）情况：0004作为根节点，左旋操作。

LR（左-右）情况：0003和0004交换，得到LL（左-左）情况。

RL（右-左）情况：0004和0005交换，得到RR（右-右）情况。

旋转前 

 

 

旋转后

下面这种情况，同时满足LL、LR，用两种选择方式来选择都是可以的，默认是LL。（RR、RL同理，默认RR）。

        当作LL情况时， 先无视0004，旋转后，再把0004插入。

        当作LR情况时，先无视0002，旋转后，再把0002插入。

旋转前

 

旋转后

由于绝对平衡，要求过于严苛，当数据庞大的时候，需要消耗大量的资源进行旋转来保持平衡。

红黑树（Red-Black Tree）

红黑树是一种自平衡的二叉查找树，具有以下特点：

1. 节点是红色或黑色：每个节点要么是红色，要么是黑色。

2. 根节点是黑色：根节点始终是黑色的。

3. 叶子节点（NIL节点，空节点）是黑色：叶子节点是特殊的空节点，它们被认为是黑色的。

4. 红色节点的子节点都是黑色的：红色节点不能连续出现，即红色节点的父节点和子节点都是黑色的。

5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点：这个特性保证了红黑树的平衡性，即任意两个叶子节点的路径长度相等。

自平衡：满足红黑树的条件即可、无需像平衡二叉树那样高度差绝对值必须小于等于1。红黑树的自平衡操作主要包括左旋、右旋和颜色翻转三种操作，在插入或删除一个节点时，红黑树最多需要进行3次旋转即可达到平衡。

红黑树旋转 

参照：红黑树最多三次旋转达到平衡 - 简书 (jianshu.com)

B树（B-Tree）

相比于二叉搜索树，B树的每个节点可以存储更多的键和值。数据直接存储在节点上。

B+树（B+ Tree）

相比于B树，B+树内部节点上只存储键，具体数据存到叶子节点上。

在线演示工具
二叉搜索树：https://www.cs.usfca.edu/~galles/visualization/BST.html
平衡二叉树：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
红黑树：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
B树：https://www.cs.usfca.edu/~galles/visualization/BTree.html
B+树：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html