二叉搜索树、AVL树、红黑树
二叉搜索树
二叉搜索树,也称有序二叉树、排序二叉树,是指一颗空数树或者具有下列性质的二叉树:
1.左子树上所有结点的值都小于它的根结点的值;
2.右子树上所有结点的值都大于它的根结点的值;
3.以此类推,左、右子树也分别为二叉查找树
中序遍历 :升序排序
保证性能的关键
1.保证二维维度!——> 左右子树结点平衡
2.保证是平衡的
AVL树
时间复杂度是O(logn)
1.平衡因子:是它的左子树的高度减去它的右子树的高度(有时相反)。balance factor={-1,0,1}
2.通过旋转操作来进行平衡
平衡因子的由来:因为它的时间复杂度是等于数的深度,所以会记录深度差,这就是平衡因子
记录左右子树高度
旋转操作
1.左旋
2.右旋
3.左右旋
4.右左旋
子树形态:右右子树——>左旋
子树形态:左左子树——>右旋
子树形态:左右子树——>左右旋
子树形态:右左子树——>右左旋
带有子树的旋转
不足
结点需要存储额外信息。且调整次数频繁
红黑树
时间复杂度O(logn)
红黑树是一种近似平衡的二叉搜索树,它能够确保任何一个结点的左右子树的高度差小于两倍。具体的来说,红黑树是满足如下条件的二叉搜索树:
- 每个结点要么是红色,要么是黑色
- 根结点是黑色
- 每个叶节点(NILl结点,空结点)是黑色
- 不能有相邻接的两个红色结点
- 从任一结点到其每个叶子的所有路径都包含相同的黑色结点
最后两点证明高度差是小于两倍的
从根到叶子的最长的可能路径不多于最短路径的两倍长
对比
- AVL树提供了更快的查询,因为它是更加严格的平衡
- 红黑树提供了更快的插入和删除的操作,因为AVL的旋转操作会更多,红黑树会更少一些。因为,红黑树是一个近似平衡树。
- AVL要存的额外的信息更多一点,它需要更多的内存附加在每个结点的里面来存这些额外的信息,而红黑树要的信息非常少,它只要一个bit就是来存0和1表示红还是黑,AVL是int型。所以,它对额外内存的消耗小
- 如果在读操作非常多写操作很少的时候,就用AVL,AVL的问题就是插入删除调整得比较频繁,但是它的好处就是比较平衡,适用于数据库。如果这个东西的插入操作也比较多的话,或者插入操作和查询操作一半一半的话,一般来说,使用红黑树,适用于map、set