Warning: The magic method MchGdbcBasePublicPlugin::__wakeup() must have public visibility in /srv/www/vhosts/cryptomilk/blog/wp-content/plugins/goodbye-captcha/includes/plugin/MchGdbcBasePublicPlugin.php on line 44
Left-Leaning Red-Black Trees – Andreas Schneider

Left-Leaning Red-Black Trees

Red-Black Trees were originally designed by taking a 2-3-4 tree and unrolling the big nodes into a cluster of simpler binary tree nodes. The 2-3-4 node operations are mapped to binary tree operations. Now Robert Sedgewick presented a new tree called Left-Leaning Red-Black Tree.

A Red-Black tree has a lot of cases you have to consider, especially if you delete a node. This makes the code complex. Left-Leaning Red-Black Trees are a simpler variant of Red-Black Trees. They are simpler to implement (less code) while maintaining the nice features of Red-Black Trees. Less code means faster insertion and deletion, but there are no benchmarks yet.

Once Bob released his new book this would be a nice improvement for csync in the future. You can take a look at the slides of his talk.

You may also like...

Leave a Reply

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