焦作住房和城乡建设局网站,推荐10网站,广州领域设计网络运营有限公司,企业年报网上申报系统网址前言 面试过程中#xff0c;多多少少会问一点数据结构#xff08;二叉树#xff09;的问题#xff0c;今天我们来复习一下二叉树的相关问题#xff0c;文末总结。
1. 二叉树的由来 在 jdk1.8 之前#xff0c;HashMap 的数据结构由「数组链表」组成#xff0c;数组是 Ha…前言 面试过程中多多少少会问一点数据结构二叉树的问题今天我们来复习一下二叉树的相关问题文末总结。
1. 二叉树的由来 在 jdk1.8 之前HashMap 的数据结构由「数组链表」组成数组是 HashMap 的主体链表是为了解决 Hash 冲突引入的正常的数据存放是直接存在数组中但如果发生 Hash 冲突就会以链表的形式进行存储而在 jdk1.8之后当链表的长度超过 8 之后将会转换成红黑树经常存储... 相信这一段 HashMap 的描述一定是大家所熟知的其实细品之后我们可以从这段描述中发掘这些信息。 数组 链表 树。 正所谓有需求就会有发展我们来看看为什么在有「数组链表」的情况下还出来个树结构。
数组优点
简单易用随机访问性强无序数组插入速度很快效率为O1有序数组查找速度较快效率为O(logN)
数组缺点
插入和删除效率低数组大小固定无法动态扩容
链表优点
大小不固定无限扩容插入和删除速度很快
链表缺点
查询效率低不支持随机查找必须从第一个开始遍历在链表非表头的位置进行插入、删除很慢效率为O(N) 从数组到链表的优缺点我们可以看出是各有千秋不能很准确的说链表比数组就一定要高效而正是因为这种关系的存在所以二叉树出现了。 所以二叉树的由来二叉树整合了数组和链表的优缺点使得插入、删除、查找的速度都很快效率比较高。
2. 二叉树是什么 二叉树是树形结构的一个重要类型也是众多数据结构的基石。 树有很多类型每个节点最多只能有两个子节点的叫二叉树。 所以二叉树的特性就是每个节点的子结点不允许超过两个。 3. 二叉查找树 二叉查找树是一种特殊的二叉树二叉查找树的特点就是左子树节点比父节点小右子树节点值比父节点大。 极端 二叉查找树有一种极端的存在二叉树的大部分子节点都比父节点值小然后导致所有的数据偏向左侧进而退化成链表如下图所示 我们使用二叉树的目的是因为其效率高于链表查询但这种退化为链表的现象很显然就突兀怎么办呢。 所以为了解决二叉树退化成一棵链表就引入了平衡二叉树。
4. 平衡二叉树 平衡二叉树又被称为AVL树是为了解决二叉树退化成一棵链表而诞生的。 平衡二叉树特点
拥有二叉查找树的全部特性。每个节点的左子树和右子树的高度差至多等于1。 其中左右子树的高度差是通过左旋右旋实现的。 下面是一个平衡二叉树和非平衡二叉树的图 到底是如何判断高度差的呢我们可以来数节点最长连接数比如左侧节点最长连接数为「3 4 5」3个节点右侧为「9」一个节点所以高度差为2。 再比如下面一个平衡二叉树 左侧最长连接点为「3(9) 7 11」即高度为2右侧最长连接点为「14(16) 15 18 11」即高度为4所以高度差为2。 为了维持二叉树的平衡平衡二叉树是通过左旋、右旋来保证的从大的方向旋转过程又被分为单旋转和双旋转总之旋转的作用就是避免出现节点偏向一边的情况具体左旋、右旋操作在这就不详细阐述了。 但是平衡二叉树这种高度差为 1 的要求太严格了尤其是对于频繁删除、插入的场景非常浪费时间...
5. 红黑树 对于那种频繁删除、插入的场景平衡二叉树的调整过程显然是存在性能问题的所以为了解决这个问题进而又引入了红黑树。
红黑树的特点
具有二叉树所有特点。每个节点只能是红色或者是黑色。根节点只能是黑色且黑色根节点不存储数据。任何相邻的节点都不能同时为红色。红色的节点它的子节点只能是黑色。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树如下图所示 概括为红黑树所有的根节点都是黑色的的空节点也就是根节点不存数据任何相邻的节点都不能同时为红色红色节点是被黑色节点隔开的每个节点从该节点到达其可达的叶子节点是所有路径都包含相同数目的黑色节点。 正是因为这种特点红黑树不同于平衡树的操作红黑树不会因为插入、删除等操作追求绝对的平衡它的旋转次数少插入最多两次旋转删除最多三次旋转所以对于搜索、插入、删除操作较多的情况下红黑树的效率是优于平衡二叉树的。 但是需要注意的是如果应用场景中对插入、删除不频繁只是对查找要求较高那么平衡二叉树还是较优于红黑树。 总结
1、为什么有了数组和链表还要引入二叉树 针对数组和链表的优缺点无法说链表一定优于数组或者是数组一定优于链表因为某些长期的需要所以就推出一个相对折中的二叉树。
2、为什么有了二叉树还要引入平衡二叉树 有了二叉树还不算完二叉树有一种极端的情况就是所有的子结点偏向一端二叉树退化成链表这就相当于我选择了这种的二叉树你现在罢工不干了找了个链表来糊弄我... 所以为了解决二叉查找树退化为链表的情况引入了平衡二叉树即 平衡二叉树是为了解决二叉树退化成一棵链表而诞生的。 既然有了平衡二叉树这下总没有问题了吧
3、为什么有了平衡二叉树还要引入红黑树 但是是实际使用过程中因为平衡二叉树追求绝对严格的平衡关系显然这个规则在于频繁的插入、删除等操作的情景性能肯定会出现问题... 所以为了解决这个问题进而又引入了红黑树。 平衡二叉树追求绝对严格的平衡平衡条件必须满足左右子树高度差不超过1红黑树是放弃追求完全平衡它的旋转次数少插入最多两次旋转删除最多三次旋转所以对于搜索、插入、删除操作较多的情况下红黑树的效率是优于平衡二叉树的。
4、红黑树是终结吗 时代总是进步的大胆猜测不会是就跟当初从数组、链表到二叉树一样。
至此通过这篇希望大家对整个树结构的出现有一个基础的概念目前面试中最为常问的就是红黑树了当然这得益于 HashMap但红黑树还有挺多其他的知识点可以考察例如红黑树有哪些应用场景红黑树与哈希表在不同应该场景的选择红黑树有哪些性质红黑树各种操作(插入删除查询)的时间复杂度是多少等等等等...
