3 ms·
Skimming through, I didn't see any discussion of AA trees which I have seen discussed as similar to red black trees but simpler to implement and have been inter
by mattnewport 3y ago
Skimming through, I didn't see any discussion of AA trees which I have seen discussed as similar to red black trees but simpler to implement and have been interested in exploring for learning purposes. Any reason you didn't look specifically at AA trees, or were they covered somewhere that I missed?
- rtheunissen 3y agoYou are correct, they have not been covered yet. I've added a note in the "work in progress" section. There are also LLRB trees that would be interesting to see compared within this framework. All the red-black trees are implemented as rank-balanced trees, so there is no concept of "color" exactly, but the authors do mention the left-leaning 2-3 rule and the left-leaning red-black rule -- I just haven't implemented those yet. See Pg. 5 of https://citeseerx.ist.psu.edu/document?type=pdf&doi=52330eed3864490c8bc30c3bc2f824d2ad609be0 https://citeseerx.ist.psu.edu/document?type=pdf&doi=52330eed...