[835] Tree

Title Text:Not only is that terrible in general, but you just KNOW Billy’s going to open the root present first, and then everyone will have to wait while the heap is rebuilt.

Origin:https://xkcd.com/835/

https://www.explainxkcd.com/wiki/index.php/835:_Tree

Cueball将他家的客厅圣诞树变成了一个令人讨厌的编程双关语。他的父母,Hairbun和一位父亲 – Cueball,如此不受欢迎,明年他不会受到欢迎。

树是计算机科学中的数据结构,基于两个简单的规则:

树从单个节点开始,称为根节点。

树中的每个节点都有两个或多个空间用于其子节点,每个节点可以为空或由另一个节点占用。当然,该节点可能有自己的子节点,依此类推。除根之外的每个节点都只有一个父节点。作为一个小问题,没有子节点的节点称为“叶子节点”。

二叉树是一棵树,其中每个节点都有2个子节点的空格。

“圣诞树”是二叉树的基本表示 – 顶部的星是根节点,向下运行的灯表示父和子之间的连接。与“根”和“叶子”这两个术语的含义相反,计算机科学中的树木通常呈现倒置,根部位于顶部,树叶在下方扇形展开。

圣诞树是在没有明显规则的基础上构建的,但二叉树的主要功能在于根据特定规则组织它们。因为稍后运行的代码可以假设数据以这种特定方式组织,所以它可以使用不同的算法来使事情运行得更快。这样做的一种方法是使用堆。堆是一种特殊的树(通常是二叉树,但在本例中是一个四元树),受一个附加规则的约束:

对于树中的每个节点,该节点下面的所有节点 – 它的所有子节点,它的所有子节点,它们所有的子节点等等 – 都比节点本身“小于”节点。

在这种情况下,“小于”可以指代可以在两个节点之间进行的任何比较 – 在​​这种情况下,它基于礼物的大小。当然,所有这些都要付出代价;堆必须首先按该顺序放置。不仅如此,如果从堆中删除节点,则必须“重建”堆以按正确的顺序将其重新放回。这在标题文本中引用 – 如果Billy打开根目录,必须进行几次比较以将其他礼物移位到其位置以保留堆规则。

在1308年:圣诞灯使用电磁波谱构建了一个类似奇怪的圣诞树。

Leave a Reply

Your email address will not be published. Required fields are marked *

Categories