当前位置：网站首页>平衡二叉树

平衡二叉树

2022-07-16 12:00:00 【萱萱不会秃头】

前言

已经知道数组查询所用到的时间复杂度为O(logn)，如何可以降低时间复杂度呢？
请添加图片描述

要想使用二分法查找，数据就必须是有序的数组，而把有序的数组排好序时间复杂度最小的也是快速排序的时间复杂度O(nlogn)，这样使时间复杂度没有降下来，反而更大了。

哈希表是n%arr.length 来确定数据所在数组中的位置

请添加图片描述

如此通过下标来寻找数据，便可以使复杂度变为O(1)级别
但是如果出现了多个不同的值来计算得到位置相同的值

可以考虑创建二维数组，但是这样下去会造成空间的浪费，并且数组最大的特点就是要在创建数组之前确定好数组的大小。

请添加图片描述

这部分数据，用链表的形式连接，可以减少空间的浪费
请添加图片描述

但是当链表的数据过长时，在查询上复杂度就会变大O(n)
此时可以考虑把链表变成一颗树 --------->有序二叉树/排序二叉树
在这里插入图片描述
这个二叉树可以对此进行折半查找，比如要找2,2比10明显小，直接不看右边，去左边查找，2又比5小，在去左边查找，此时的时间复杂度为O(logn)；

请添加图片描述

而对于下边右边的二叉树已经是一个链表O(n)，左边的二叉树也不能做到折半查找（O(logn)-O(N)），由此可见二叉树的不稳定性（为何会不稳定？-------因为没有受到任何限制，以至于在某种特殊的情况下会变成链表）

如何稳定，就要使用到平衡二叉树！！！

平衡二叉树

平衡二叉树是在有序二叉树的基础之上而来的，它规定着一个节点的左右子树高度差的绝对值不能超过1；如果超过了就要使用到LL LR RL RR 型旋转的类型来保证平衡二叉树的平衡

LL型旋转

请添加图片描述

例如：
请添加图片描述

RR型旋转

请添加图片描述

例如：
请添加图片描述

LR型旋转

请添加图片描述

例如：请添加图片描述

RL型旋转

请添加图片描述

例如

请添加图片描述

版权声明
本文为[萱萱不会秃头]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_53954158/article/details/125712588

边栏推荐

猜你喜欢

随机推荐