4 ms·

Interesting about AVL trees is that almost all implementations out there either use recursive algorithms or require nodes to have parent pointers. This is due t

Interesting about AVL trees is that almost all implementations out there either use recursive algorithms or require nodes to have parent pointers. This is due to the fact that most literature on AVL trees describe top-down insertion/deletion and bottom-up rebalancing. Now the interesting thing is that rebalancing can also be done using a lesser-known top-down algorithm, allowing for a non-recursive algorithm that doesn't rely on parent pointers. https://web.archive.org/web/20180315093634/http://neil.brown.name/blog/20041124101820 https://web.archive.org/web/20180315093634/http://neil.brown... https://web.archive.org/web/20180320115617/http://neil.brown.name/blog/20041124141849 https://web.archive.org/web/20180320115617/http://neil.brown... The downside of such an approach of using two successive top-down algorithms is that a naïve implementation would require twice as many object comparisons. Opposed to traversing a tree bottom-up, you now have to make a choice. As both traversals (insertion/deletion and rebalancing) are identical, this can easily be prevented by storing the path during the first traversal. As AVL trees are strongly balanced and only a finite number of nodes fit in an address space, storing a path only takes very little space (a bitmask would use less than two uintptr_t's). I've implemented such an algorithm for FreeBSD's copy of the POSIX tsearch() and tdelete() functions a couple of years ago: https://svnweb.freebsd.org/base/head/lib/libc/stdlib/tsearch.c?view=markup https://svnweb.freebsd.org/base/head/lib/libc/stdlib/tsearch... https://svnweb.freebsd.org/base/head/lib/libc/stdlib/tdelete.c?view=markup https://svnweb.freebsd.org/base/head/lib/libc/stdlib/tdelete...

ufo 8y ago
Do you happen to remember what improvements you could get from the new algorithm when it comes to memory usage and execution time? Or was this more about getting rid of `void *`?
- EdSchouten 8y ago
  This was already a couple of years ago, so I forgot some of the details. It made a lot of sense in this case to not have a parent pointer in the tree nodes, for the reason that that would bump the size of a node just over 32 bytes (left, right, parent and data pointers, and a balance count). This would cause libc's allocator to allocate 64 bytes per node instead. I also seem to remember that the performance of this implementation was pretty much on par with a conventional recursive implementation. The only differences were that use of stack space was a lot less (i.e., constant) and that the machine code generated by Clang was a tiny bit smaller. I suspect that's because the optimizer didn't have to deal with recursive code.

ufo 8y ago

Do you happen to remember what improvements you could get from the new algorithm when it comes to memory usage and execution time? Or was this more about getting rid of `void *`?

EdSchouten 8y ago
This was already a couple of years ago, so I forgot some of the details. It made a lot of sense in this case to not have a parent pointer in the tree nodes, for the reason that that would bump the size of a node just over 32 bytes (left, right, parent and data pointers, and a balance count). This would cause libc's allocator to allocate 64 bytes per node instead. I also seem to remember that the performance of this implementation was pretty much on par with a conventional recursive implementation. The only differences were that use of stack space was a lot less (i.e., constant) and that the machine code generated by Clang was a tiny bit smaller. I suspect that's because the optimizer didn't have to deal with recursive code.