(ListNode* pListHead, ListNode* pToBeDeleted); 这是一道广为流传的Google面试题，考察我们对链表的操作和时间复杂度的了解，咋一看这道题还想不出什么较好的解法...一般单链表删除某个节点，需要知道删除节点的前一个节点，则需要O(n)的遍历时间，显然常规思路是不行的。...在仔细看题目，换一种思路，既然不能在O(1)得到删除节点的前一个元素，但我们可以轻松得到后一个元素，这样，我们何不把后一个元素赋值给待删除节点，这样也就相当于是删除了当前元素。...可见，该方法可行，但如果待删除节点为最后一个节点，则不能按照以上思路，没有办法，只能按照常规方法遍历，时间复杂度为O(n)，是不是不符合题目要求呢？...其实我们分析一下，仍然是满足题目要求的，如果删除节点为前面的n-1个节点，则时间复杂度为O(1)，只有删除节点为最后一个时，时间复杂度才为O(n)，所以平均的时间复杂度为：（O(1) * (n-1) +
1、二叉搜索树 又称之为二叉排序树（二叉查找树），它或许是一棵空树，或许是具有以下性质的二叉树： 若他的左子树不为空，则左子树上所有节点的值都小于根节点的值； 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值...那么插入的时间复杂度就变成了O(n)，导致这种糟糕的情况原因是因为这棵树极其不平衡，右树的重量远大于左树，因此我们提出了叫平衡二叉搜索树的结构，又称之为 AVL 树，是因为平衡二叉搜索树的发明者为 Adel...数组中如果找到某个值在什么位置，需要循环遍历整个数组，时间复杂度为O(n),而Hash表的时间复杂度基本为O(1)。因为哈希通过一次计算大幅度缩小查找范围，比从全部数据里查找速度要快。...HashMap 通过引入红黑树来解决这个问题，使复杂度降到了O(logn)....方法中根据哈希值进行相关操作，如果当前 哈希表内容为空，新建一个哈希表； 如果要插入的桶中没有元素，新建个节点并放进去； 否则从桶中第一个元素开始查找哈希值对应位置； 如果桶中第一个元素的哈希值和要添加的一样
此时时间复杂度就变为味了O（N），为了解决这种情况，出现了二叉平衡树。 平衡二叉树 平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。 AVL树也规定了左结点小于根节点，右结点大于根节点。...AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN），但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。...不过，B树的查找不稳定，最好的情况就是在根节点查到了，最坏的情况就是在叶子结点查到。另外，B树在遍历方面比较麻烦，由于需要进行中序遍历，所以也会进行一定数量的磁盘IO。...红黑树规定了： 节点是红色或黑色。 根节点是黑色。 每个叶子节点都是黑色的空节点（NIL节点） 每个红色节点的两个子节点都是黑色。也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点)。...红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的.
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 4.红黑树的各种操作的时间复杂度是多少？...能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn） 5.红黑树相比于BST和AVL树有什么优点？...红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. ...红黑树通过扩展节点域可以在不改变时间复杂度的情况下得到结点的秩。 7.如何扩展红黑树来获得比某个结点小的元素有多少个？...这其实就是求节点元素的顺序统计量，当然任意的顺序统计量都可以需要在O(lgn)时间内确定。
2021-07-11：给定一个棵完全二叉树，返回这棵树的节点个数，要求时间复杂度小于O(树的节点数)。...福大大 答案2021-07-11： 右树最左节点层数==左树最左节点层数，左树是满二叉树，统计左树节点个数，递归右树。 右树最左节点层数!...=左树最左节点层数，右树是满二叉树，统计右树节点个数，递归左树。 时间复杂度：O(logN的平方)。空间复杂度：O(logN)。 代码用golang编写。..., 1, mostLeftLevel(head, 1)) } // 当前来到node节点，node节点在level层，总层数是h // 返回node为头的子树(必是完全二叉树)，有多少个节点 func...，最大深度是多少 // node为头的子树，一定是完全二叉树 func mostLeftLevel(node *Node, level int) int { for node !
，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。 ...1.2 AVL树的性质 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的...如果它有n个结点，其高度可保持在 O(log_2 n) ，搜索时间复杂度O( log_2 n ) 1.3 AVL树的节点 那么AVL树节点的内容除了左右子树的指针以及存储数据的类型，还需要保存该节点的平衡因子...2.2 红黑树的性质 红黑树的节点可以是红色或黑色，满足以下性质： 根节点是黑色的。 如果一个节点是红色的，则它的两个子节点都是黑色的。 从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。...这些操作可以保证树的高度保持在O(logn)，从而提供了较好的性能。 在实际应用中，AVL树和红黑树都可以用于需要高效的插入、删除和查找操作的场景，例如数据库中的索引结构、编译器中的符号表等。
基于二叉查找树的这种特点，我们在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。...对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。 3、为什么有了平衡树还需要红黑树？...正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。至于为什么就能够保证时间复杂度为 O(logn)，我这里就不细讲了，后面的文章可能会讲。...不过，红黑树还有挺多其他的知识点可以考，例如红黑树有哪些应用场景？向集合容器中 HashMap，TreeMap 等，内部结构就用到了红黑树了。还有构建一棵节点个数为 n 的红黑树，时间复杂度是多少？...红黑树与哈希表在不同应该场景的选择？红黑树有哪些性质？红黑树各种操作的时间复杂度是多少？
由于AVL树保持平衡，因此任何操作的时间复杂度都是O(log n)。2.AVL树常见术语AVL树的节点高度是该节点到其最远叶子节点的路径长度，即从该节点往下到最底层节点的路径长度。...将B节点的左子节点C连接到A节点的右子节点上。如果C节点不为空，则将C节点的父节点改为A节点。计算A节点和B节点的高度差，更新它们的高度属性。返回修改后的AVL树。...3.4 先右旋后左旋先来了解一下什么是AVL树：AVL树是一种自平衡二叉搜索树，它的每个节点的左子树和右子树的高度差至多为1，这就保证了它的查找、插入和删除操作的时间复杂度都是O(log n)。...val); }}5.优点和缺点优点：AVL树保证了每个节点的左右子树高度差不超过1，因此查询效率较高，时间复杂度为O(logn)。...例如，在数据库中，AVL树常常被用来存储索引数据，以便快速地查找和访问表中的数据；在编译器中，AVL树通常被用来实现符号表，以便快速地查找和访问变量和函数等标识符信息；在路由算法中，AVL树常常被用来维护路由表
二叉树遍历的时间复杂度 从我前面画的前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 O(n)。...中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。...这个时候，插入、删除、查找的时间复杂度是多少呢？ 从我前面的例子、图，以及还有代码来看，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。...第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。...红黑树的高度不是很好分析，我带你一步一步来推导。 首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？
实现跳表的关键之处是在有序链表的基础上加上各层索引，通过这些索引可以做到O(log n)的时间复杂度快速地插入、删除、查找元素。...没错，当按照元素的自然顺序插入元素的时候，二叉查找树就退化成单链表了，单链表的插入、删除、查找元素的时间复杂度是多少？O(n)。 所以，在极限情况下，二叉查找树的时间复杂度是非常差的。...比如，上面那颗树，按A、B、C插入元素后，做一次旋转操作，就可以再次变成查找时间复杂度为O(log n)的树。 ?...过程与2-3树一样，向上分裂即可，此时，中间节点有两个，取任意一个上移都是可以的，我们这里以左中节点上移为例，大致过程如下： ? 是不是挺简单的，至少比AVL树那种左旋右旋简单得多。...B树，一个节点可以存储多个元素，有利于缓存磁盘数据，整体的时间复杂度趋向于O(log n)，原理也比较简单，所以，经常用于数据库的索引，包括早期的mysql也是使用B树来作为索引的。
二叉查找树 二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意节点的左子树不空，...avl树即平衡树，他对二叉树做了改进，在我们每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。...依然是大的数据放右边，小的数据放左边。此时我们向该树重如果该数可以直接放入二节点中，就直接进去，但如果正好需要放在三节点中，就像图中一样，Z正好要放在SX中。...红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。加快检索速率。...⑶该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。 这里节点之间的连接分为红连接和黑连接，取代了红节点和黑节点的定义（本质是一样的），将之前的黑高度相等定义为了黑连接数相等。
简述二叉树的前中后序遍历算法 前序遍历：若二叉树为空树，则执行空逻辑，否则： 访问根节点 递归前序遍历左子树 递归前序遍历右子树 中序遍历：若二叉树为空树，则执行空逻辑，否则： 递归中序遍历左子树 访问根节点...递归中序遍历右子树 后序遍历：若二叉树为空树，则执行空逻辑，否则： 递归后序遍历左子树 递归后序遍历右子树 访问根节点 简述解决Hash冲突的方法 开放定址法：当发生哈希冲突时，如果哈希表未被装满，那么可以把这个值存放到冲突位置中的下一个空位置中去...简述AVL树 AVL树是一种改进版的搜索二叉树，其引入平衡因子（左子支高度与右子支高度之差的绝对值），通过旋转使其尽量保持平衡。 任何一个节点的左子支高度与右子支高度之差的绝对值不超过1。...红黑树保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。...通过对这种数据结构进行每个元素的插入，插入值后，更新堆的过程中，把想等大小的值的相对位置上浮的过程中可能会改变，不稳定。 排序算法不稳定，时间复杂度 O(nlogn)，空间复杂度 O(1)。
，也被称为NIL节点) 任意结点到其每个叶子结点的简单路径上，黑色节点的数量相同：确保了树的黑平衡性，即红黑树中每条路径上黑色结点的数量一致。...而AVL树也是O( log_2 N ），但AVL树是比较严格的O( log_2 N ），而红黑树是省略了常数项。...5.4 插入相同数量随机数比较AVL树和红黑树的高度 然后我们AVL树写的求高度的函数拷贝过来，在AVL树和红黑树中插入相同数量的随机数，看看它们的高度会差多少： 我们看到插入相同数量随机数它们的高度是可以达到一样高的...红黑树与AVL树的比较 红黑树和AVL树都是高效的自平衡搜索二叉树，增删改查的时间复杂度都是O( log_2 N )。...因为AVL树在插入和删除节点后，会进行更多的旋转操作以维持一个较为严格的平衡，所以插入和删除操作的时间复杂度更高。
B树，不是二叉树，是一种多叉树。 红黑树是一种近似平衡的二叉查找树。 二叉树、红黑树、B树定义以及时间复杂度计算方式 二叉树 在计算机科学中，二叉树是每个节点最多有两个子树的树结构。...红黑树的定义 *红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪倍。...具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）： 每个节点要么是红色，要么是黑色。 根节点必须是黑色 每个叶节点（NIL节点，空节点）是黑色的。...红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。...当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。 红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.
在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。 为了让二叉搜索树不至于太“倾斜”，我们需要构建一棵 平衡二叉搜索树。 ?...可以看出，平衡二叉搜索树的搜索时间复杂度为O(logn)，避免了因为随机选取根节点构建二叉搜索树而可能造成的退化成链表的情况。下面再抄一段平衡二叉搜索树的官方定义： 平衡二叉查找树：简称平衡二叉树。...我们可以简单思考一下，对于一棵普通的平衡二叉搜索树来说，它的搜索时间复杂度为O(logn)，而作为红黑树，存在着最坏的情况，也就是查找的过程中，经过的节点全都是原来2-3树里的3-节点，导致路径延长两倍...，时间复杂度为O(2logn)，由于时间复杂度的计算可以忽略系数，因此红黑树的搜索时间复杂度依然是O(logn)，当然，由于这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL树）搜索效率要低一些...AVL树是严格平衡，红黑树只能达到“黑平衡”，即从任意节点出发到叶子节点经过的黑节点数量相同，但经过的红色节点数量不确定，最差的情况下，经过的红色节点和黑色节点一样多。 2.
树和二叉树的三个主要差别 树的节点个数至少为1，而二叉树的节点个数可以为0 树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2 树的节点没有左右之分，而二叉树的节点有左右之分 二叉树特点...对于目标节点的查找过程类似与有序数组的二分查找，在二叉排序树中查找一个结点的平均时间复杂度是O(log n)； 设节点数目为n，树的深度为h，假设树的每层都被塞满(第L层有2^L个节点，层数从1开始)，...平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。...在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(logn)。...O(logn)，但是每次操作均摊时间复杂度为O(logn)，例如伸展树。
如下是一棵二叉查找树： 当需要快速查找时，将数据存储在 BST 是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(lgn)。...当插入数据时，最多只需要1次旋转（单旋转或双旋转）；但是当删除数据时，会导致树失衡，AVL 需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。...但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像 AVL 树进行O(lgn)次数的旋转。...因此，当总节点数量相同时，B 树的高度远远小于 AVL 树和红黑树（B 树是一颗“矮胖子”），磁盘 IO 次数大大减少。...更稳定的查询效率：B 树的查询时间复杂度在1到树高之间（分别对应记录在根节点和叶节点），而 B+ 树的查询复杂度则稳定为树高，因为所有数据都在叶节点。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
云直播
对象存储
