数据结构 二叉树（BST树） 和 平衡二叉树（AVL树 ）

前言一、二叉树

1.特点2.好处3.缺点 二、平衡二叉树（红黑树）

1.特点2.好处：3.缺点： 总结

说到数据结构，就不得不联想到 索引，其中以mysql为代表。索引底层就是利用树结构，以时间换空间。二叉树，平衡二叉树 也叫红黑树，B树，B+树。这篇文章就说下 我对 二叉树和平衡二叉树 的了解。

如图所示 每一个数字都是一个节点，第一排为根节点，上一排作为下一排的父节点。

1. 根节点的值大于其左子树中任意一个节点的值。
2. 根节点的值小于其右节点中任意一节点的值。
3. 这一规则适用于二叉查找树中的每一个节点。

查询的时间复杂度比链表快，链表的查询时间复杂度是O(n)，二叉排序树平均是O(logn)。二叉排序树越平衡，越能模拟二分法，所以越能想二分法的查询的时间复杂度O(logn)。

就是利用二叉树的特性， 用二分法 快速定位到 要查找数据的地方，大大的节省了时间

因为二叉树的特性是，节点左边的小于右边的。如果一组数据是连续单边增 或者 单边减

此时，二叉树就相当于是一个链式结构，失去了树结构的特性，不能再用空间换时间了
由此，就衍生出了 平衡二叉树，也就是红黑树

平衡二叉树（AVL树/红黑树） 就是为了 弥补 二叉树的缺陷。

平衡二叉树（AVL树/红黑树）特点：

根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。AVL树上任意结点的左、右子树的高度差最大为1当树 单边层数过高时，会自动平衡 重新挑选合适的节点作为根节点

由于第二条和第三条的特点：所以 平衡二叉树，就不会像二叉树 那样出现链式结构的致命缺陷。 它是一种“矮胖 ”形状的树。因为任意节点左右 高度相差为1，他不像上面二叉树那样排列，而是：

保留了二叉树的优点 并优化，去除了特殊情况下 变成链表的致命缺陷

成也萧何，败也萧何

因为第二条和 第三条 特点：
当数据量很大时 任意节点左右 高度相差为1，树结构就会分很多层，树就很高。当树过高，查找的数据又在最底层的节点，此时 要经历n个层数 进行比较，需要花费一定的时间，效率也就相应的降低

至于优化方法呢，就是后面要讲的 B树 和 B+树了

本文仅仅介绍了 二叉树和平衡二叉树的 特点，优缺点。不足之处，欢迎大佬们指教 .