树中的基本概念：https://jingzh.blog.csdn.net/article/details/107128291 树类型概述： 二叉树，完全二叉树，满二叉树，二叉排序树，平衡二叉树，红黑树，B树，B+树，B*树

二叉树：二叉树是每个节点最多有两个子树的树结构； 是n(n>=0)个结点的有限集合，它或者是空树（n=0），或者是由一个根结点及两颗互不相交的、分别称为左子树和右子树的二叉树所组成

二叉树特点：

完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点

完全二叉树特点：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树 满二叉树特点：

二叉排序树：可以为空树，或者是具备如下性质：若它的左子树不空，则左子树上的所有结点的值均小于根节点的值；若它的右子树不空，则右子树上的所有结点的值均大于根节点的值，左右子树分别为二叉排序树。 如下图所示： 但是还有一种特殊情况： 这种情况下，二叉搜索树已经变更为链表，搜索一个元素的时间复杂度从O(lgn)退化为O(n)出现这种情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树

平衡二叉树是一种概念，是二叉查找树的一个进化体，它有几种实现方式：红黑树、AVL树 它是一个空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。

这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多

AVL实现平衡的关键在于旋转操作：

插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn) 由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 红黑树的特性：

红黑树和AVL树区别 RB-Tree和AVL树作为二叉搜索树(BBST)，其实现的算法时间复杂度相同，AVL作为最先提出的BBST，貌似RB-tree实现的功能都可以用AVL树是代替，那么为什么还需要引入RB-Tree呢