本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
cs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/04/04 00:58] – [Heap] codinghare | cs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/04/14 14:21] (当前版本) – [原理:双子节点的情况] codinghare | ||
---|---|---|---|
行 200: | 行 200: | ||
// | // | ||
\\ \\ | \\ \\ | ||
- | {{ : | + | {{ : |
* **// | * **// | ||
这种解决方案来源于一种很朴素的想法,化繁为简。首先可以明确的是,直接删除拥有两个子节点的节点,并且还要保证 BST 的结构不出问题,是非常困难的。但相比之下,删除只有一个子节点或者没有子节点的节点则非常简单。因此,相比直接删除节点,我们选择**替换**节点中的内容,而这正是使用 Predecessor 或 Successor 的精妙之处。 | 这种解决方案来源于一种很朴素的想法,化繁为简。首先可以明确的是,直接删除拥有两个子节点的节点,并且还要保证 BST 的结构不出问题,是非常困难的。但相比之下,删除只有一个子节点或者没有子节点的节点则非常简单。因此,相比直接删除节点,我们选择**替换**节点中的内容,而这正是使用 Predecessor 或 Successor 的精妙之处。 | ||
行 509: | 行 509: | ||
==Heap== | ==Heap== | ||
^Operation^Best^Average^Worst^ | ^Operation^Best^Average^Worst^ | ||
- | |Find Min / max|$O(1)$|$O(1)$|$O(1)$| | + | |**//Find Min// / max**|$O(1)$|$O(1)$|$O(1)$| |
- | |Add|$O(1)$|$O(1)$|$O(n)/ | + | |**//Add//**|$O(1)$|$O(1)$|$O(n)/ |
- | |Remove Min/ | + | |**//Remove Min/max//**|$O(1)$|$O(log(n))$|$O(log(n))$| |
- | |Aribitray Search/ | + | |**//Aribitray Search//**/ |
- | |BuildHeap|-$O(n)$|$O(n)$|$O(n)$| | + | |**//BuildHeap//**|-$O(n)$|$O(n)$|$O(n)$| |
- | |Space Complexity|$O(n)$|$O(n)$|$O(n)$| | + | |**//Space Complexity//**|$O(n)$|$O(n)$|$O(n)$| |
==HashMap== | ==HashMap== | ||
^Operation^Best^Average^Worst^ | ^Operation^Best^Average^Worst^ | ||
|Put / Add New Key (Closed Addressing)|$O(1)$|$O(1)$|$O(n)$| | |Put / Add New Key (Closed Addressing)|$O(1)$|$O(1)$|$O(n)$| | ||
- | |Put / Add New Key (Open Addressing)|$O(1)$|$O(1)$|$O(n)^*$$O(n^2)$| | + | |Put / Add New Key (Open Addressing)|$O(1)$|$O(1)$|$O(n)^*$ |
|Remove Key|$O(1)$|$O(1)$|$O(n)$| | |Remove Key|$O(1)$|$O(1)$|$O(n)$| | ||
|Searching for a Key|$O(1)$|$O(1)$|$O(n)$| | |Searching for a Key|$O(1)$|$O(1)$|$O(n)$| |