普通二叉树(以下简称二叉树)

在二叉树创建的过程中，如果遇到最坏的情况，即有序列去生成二叉树，会导致该二叉树在查找那性能上等同于数组遍历。
例如：1，2，3，4，5，6
将会生成一个高度为6的二叉树，假设查找6，将会入数组遍历。
所以二叉树并不是(最差情况的）最优的树

AVL树(平衡二叉树)

AVL树为了解决上面的问题。
在AVL树的定义是左右子树的高度差不超过1。

image.png

在插入节点后判断树是否平衡，
不平衡的话，
可以通过左右旋转进行平衡处理。
参考该文章

AVL树与红黑树

平衡二叉树类型	平衡度	调整频率	适用场景
AVL树	高	高	查询多，增/删少
红黑树	低	低	增/删频繁

通过上表，我们知道这个AVL树虽然平衡度好，平衡度好的话，就能提供最差情况下，最优的查询效率。
但是插入删除，触发的频率比较高。
所以就有了，红黑树，平衡度低，但插入删除的频率较低。

红黑树

和平衡树相比，不在根据左右树的高度差来判断平衡，而是通过插入的父节点颜色，及其状态来判断是否需要，左变色即旋转操作达到平衡。