共计 823 个字符，预计需要花费 3 分钟才能阅读完成。
前言
- 数据结构的实现有两种形式，一种是顺序存储，一种是链式存储
顺序存储：应用一片间断的逻辑地址存放数据
链式存储：不必间断地址，应用指针指向下个元素的地址
- 罕用数据结构有：线性表，栈，队列，树，图等等，二叉树是属于这外面的树。
BST(Binary Search Tree)介绍
BST 是一种树，他的个性是
1. 左子树上所有结点的值均 小于或等于 它的根结点的值。
2.右 子树上所有结点的值均 大于或等于 它的根结点的值。
3. 左、右子树也别离为 BST
BST 的长处:
- BST 通常是应用链式构造存储实现的，应用顺序存储要么是 (Full Binary Tree) 或者靠近(Full Binary Tree)
- 顺序存储最大的弊病是必须事后给出数组的存储空间大小插入删除比拟麻烦，长处是能够节俭空间，查找很快
BST 的毛病:
- 抛开顺序存储和链式存储，BST 数据结构自身存在的毛病是，在特定的时候，树的度会始终升高，导致查找效率变低
这个时候咱们就有新的树来解决他的毛病就是(AVL Tree)
AVL Tree
AVL 树，实质上是带了均衡性能的 BST，他多了个 均衡因子 概念
即（每个结点的左右子树的高度之差的绝对值（均衡因子）最多为 1），如果不满足就会旋转来满足这个条件。
下面图一 BST 在 avl 中旋转操作后失去如下，具体怎么旋转的能够在这个网站本人模仿
https://www.cs.usfca.edu/~gal…
那么 AVL 有没有什么毛病呢 ?
最大的毛病就是谋求完满的均衡导致插入和删除须要大量的均衡计算，这个在插入和删除大的状况导致开销较大，这个时候咱们就想着，有没有一种树，解决 BST 的毛病，同时又不要大量的计算均衡，于是 RB-Tree 就被创造了
RB-Tree 和 AVL 区别
- RB-Tree 的定义不介绍了，咱们记得这个区别就行
删除 node 引起树的不均衡时，最坏状况下，AVL 须要保护从被删 node 到 root 这条门路上所有 node 的平衡性，而 RB-Tree 最多只需 3 次旋转。
下图是解决图一不均衡 RB-Tree 的图
正文完