What & How & Why

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版
前一修订版
cs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/04/04 00:58] – [Heap] codingharecs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/04/14 14:21] (当前版本) – [原理:双子节点的情况] codinghare
行 200: 行 200:
 //Predecessor//(**最大前继**) 是指在 BST 中,比 root **小**的节点中**最大**的一个节点;而 //Successor//(**最大后继**) 是指在 BST 中,比 root **大**的节点中**最小**的一个节点。比如下面 BST 中的 ''21'' 和 ''30'' 就是 root ''24'' 的最大前继和最小后继: //Predecessor//(**最大前继**) 是指在 BST 中,比 root **小**的节点中**最大**的一个节点;而 //Successor//(**最大后继**) 是指在 BST 中,比 root **大**的节点中**最小**的一个节点。比如下面 BST 中的 ''21'' 和 ''30'' 就是 root ''24'' 的最大前继和最小后继:
 \\ \\  \\ \\ 
-{{ :cs:dsa:courses:gtx_1332x:ii_non_linear:prede_n_successor.svg?250 |}}+{{ :cs:dsa:courses:gtx_1332x:ii_non_linear:prede_n_successor_1_.svg?250 |}}
   * **//为什么要使用 Predecessor 和  Successor?该如何使用?//**   * **//为什么要使用 Predecessor 和  Successor?该如何使用?//**
 这种解决方案来源于一种很朴素的想法,化繁为简。首先可以明确的是,直接删除拥有两个子节点的节点,并且还要保证 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)/O(log(n))*$| +|**//Add//**|$O(1)$|$O(1)$|$O(n)/O(log(n))*$| 
-|Remove Min/max|$O(1)$|$O(log(n))$|$O(log(n))$| +|**//Remove Min/max//**|$O(1)$|$O(log(n))$|$O(log(n))$| 
-|Aribitray Search/Remove|$O(1)$|$O(n)$|$O(n)$| +|**//Aribitray Search//**/Remove|$O(1)$|$O(n)$|$O(n)$| 
-|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)^*$ $O(n^2)$|
 |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)$|