Get best of the week

JavaScript中的红黑树

图片

哈勃！最近研究了红黑树。我试图可视化d3.js上插入和删除算法的操作细节。我希望该结果将为那些学习javascript算法的人节省一些时间。你可以在这里看到它。我在这里依赖的实现的源代码。根据猫短的细节。

搜索现有解决方案


这个想法的主要目的是了解算法的实现并将其可视化。第一步是寻找带有完整且易于理解的解释和js代码的实现。在搜索过程中，令人遗憾的是作者有时没有完成源代码，例如，有一个插入算法，但没有删除。或者他们像这样进行可视化，但是他们不提供到源的链接。然后我找到了这篇出色的文章。但是，即使杀死，我仍然不明白为什么作者在代码中插入了图片，却没有按注释的要求提供源代码的链接。还有一个npm red-black-tree软件包，其完整源代码为：readme中的“进行中...”。还发现了流行的实现 js上的红黑树，每周要依赖大量软件包和数百万下载，但是其中的代码已有五年历史了。

优先级和任务规范


在Porakinin大脑中，我认为将代码的可读性和可理解性用于教育目的是一个优先事项，因此我以开头提到的文章（而不是npm软件包）为基础。事实证明，该实现在阅读代码方面更加方便且直观。在本文中，作者从二叉树开始，然后将其扩展为红黑色。为了可视化，从红黑树继承并制作动画树似乎很合逻辑。因此，在重新键入代码并确保其可以正常工作之后，我开始绘制动画树。D3.js.来了。有很棒的过渡，可以让您将元素移动到正确的位置，并在算法工作时将其平滑地转换为合适的状态。

红黑树的意思


我想了很长时间，好像是用一种简单的方式来解释什么。可能都是如此，您需要从不同的来源阅读该理论。俗话说：“您不会在歌曲中吐出言语。” 但是可以简单地总结出简单的总结性结论。最重要的是，在插入和删除元素时有几种情况，具体取决于哪些“祖父”，“爸爸”，“叔叔”，“孩子”，“兄弟”重新绘制并移动（转向）元素较少的那一侧。结果，从最远节点到根节点的路径永远不会太长，因此在这种结构中搜索所需元素的速度非常快。好吧，这被插入和删除的复杂性所抵消。

More articles:


All Articles