二叉树——初识
链表 ——> 二叉树 ——> 二叉查找树 ——> 平衡二叉树
二叉树时间复杂度：O(logn) ，即2^x(树的深度)=N
如：21亿点需要查找几次：2^32 = 21亿，查找32次。
1、满二叉树
2、完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。（除最后一层外，为一颗满二叉树）
完全二叉树的基础上可以引申出 堆(heap) 的数据结构：
堆的定义：堆就是一个数组，用来存放完全二叉树。
大堆：所有 根节点值 均大于 左右孩子节点值
小堆：所有 根节点值 均小于 左右孩子节点值
如何理解数组存放完全二叉树？堆排序：
arr = [3, 1, 4, 2, 5] arr[0] 为堆顶。
直接手撕代码：
平均时间复杂度：O(nlogn) ，堆常用于topk算法，大顶堆求小值（前k个最小的值），小顶堆求大值（前k个最大的值）
3、二叉排序树（二叉查找树）的定义：
某结点左子树的所有结点的值都小于该节点的值且该结点右子树的值都大于该节点的值
！！！二叉排序树的使用性质：中序遍历后是一个有序数组。
区别：
(1) 二叉排序树是为了实现动态查找而设计的数据结构，它是面向查找操作的，在二叉排序树中查找一个结点的平均时间复杂度是O(log n)；
(2) 堆是为了实现排序而设计的一种数据结构，它不是面向查找操作的，因而在堆中查找一个结点需要进行遍历，其平均时间复杂度是O(n)。
4、平衡二叉树是特殊的二叉排序树
改进版：平衡二叉树 AVL 为了尽量降低树的高度，平均查找长度越小，查找速度越快
平衡因子 = 左子树的高度 – 右子树的高度
平衡二叉树的条件：
１、是二叉排序树
２、满足每个结点的平衡因子绝对值不大于１
平衡二叉树的平衡调整：
左旋如下：
S结点上提，E结点下降，伴随指针向左滑动
右旋示例：
5、红黑树：寻找相对平衡的二叉树
1.每个结点要么是红的要么是黑的。
2.根结点是黑的。
3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
4.如果一个结点是红的，那么它的两个儿子都是黑的。
5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
红黑树变换：
1、改变颜色：红变黑、黑变黑
2、左旋、右旋
激活谷谷主为您准备了激活教程，为节约您的时间请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/94160.html
