Get best of the week

Red-black trees in javascript

image

Hi Habr! Recently studied red-black trees. I tried to visualize the details of the operation of the insertion and deletion algorithms on d3.js. I hope the result will help save some time for those who study algorithms in javascript. You can see it here . The source code of the implementation from which I relied on here . Under cat short details.

Search for existing solutions


The main goal of the idea was to understand the implementation of the algorithm and visualize it. The first step was to look for an implementation with full and understandable explanations and js code. In the search process, it was saddened that the authors at times unfinished the source, for example, there is an insertion algorithm, but no deletion. Or they do visualization like this , but they don’t provide links to the source. Then I found this excellent article. But at least kill, I still can’t understand why the author inserted the code with pictures and did not give a link to the source code upon request in comments. There is also an npm red-black-tree package , the entire source code of which is: 'in progress ...' in readme. Also found a popular implementation red-black trees on js, on which a lot of packages and millions of downloads per week depend, but the code there is five years old.

Prioritization and task specification


Porakinin brain, I decided that the readability and comprehensibility of the code for educational purposes is a priority, so I took as a basis the article that was mentioned at the beginning, and not the npm package. The implementation turned out to be more convenient and visual in terms of reading code. In the article, the author begins with a binary tree, then extends it to red-black. For visualization, it seems quite logical to inherit from a red-black tree and make an animated tree. Therefore, having re-typed the code and making sure that it works, I started drawing an animated tree. D3.js. comes to the rescue. There are wonderful transitions that allow you to move elements to the right positions and smoothly transform them into suitable states, as the algorithm works.

The meaning of red-black trees


I thought for a long time, as if in a simple way, to explain what's what. Probably, all the same, you need to read the theory from different sources. As the saying goes: "You won’t throw words out of a song." But simple summary conclusions can be formulated in a nutshell. The bottom line is that there are several cases when inserting and deleting an element, depending on which “grandfathers”, “dads”, “uncles”, “children”, “brothers” repaint and shift (turn) to the side where there are fewer elements . As a result, it never happens that the path from the farthest node to the root node is too long, so the search for the desired element in such a structure is very fast. Well, this is offset by the complexity of insertion and deletion.

More articles:


All Articles