Some small arguments

[SchrodingerZhu]

所谓说 avl 树每次重平衡需要回溯回根节点的纯粹胡扯

I am so glad to see this. Thanks for providing the clean code and clear comparison. However, I am little bit concerned about the argument you are making here. The following are just some of my simple ideas:

I did some similar benchmarks years ago (https://github.com/SchrodingerZhu/data_structure_for_love/blob/master/report.md, I was not so good at programming at that time as I am today, the code may contain some flaws but I think it can already provide some reasonable comparisons). As you can see, it was really a draw between Rb-Tree (a left-leaning version) and the AVL tree; one performance better in some workloads, the other wins a little in different situations.

I do agree that re-balancing of an AVL tree requires visiting back until the root each time is an exaggeration; yet I do believe there is a reason behind such argument.

In fact, in the summary section of ODS (https://opendatastructures.org/ods-python/9_3_Summary.html), the book spent a full section to prove why red-black trees can have a better re-balancing performance theoretically. In the later chapter, it also argues:

Adersson's variant of red-black trees, Sedgewick's variant of red-black trees, and AVL trees are all simpler to implement than the RedBlackTree structure defined here. Unfortunately, none of them can guarantee that the amortized time spent rebalancing is O(1) per update. In particular, there is no analogue of Theorem 9.2 for those structures.

Again, this is only something theoretically, not practically. We cannot rely fully on the analysis: for example, Fibonacci heap performances great in paper but it is troubled with its large constant time per operation; binary structures should be optimal for in memory operations but b-tree can do better in some projects due to its friendliness to the architecture. And, this exact project also suggests this idea.

Anyway, I wrote this just to leave a room for theory. Sometime, people do need "paperwork" to guarantee some critical properties. and I think that is why rb-tree is widely chosen. However, as the theory also suggest, AVL tree can have a lower height, so it is also widely accepted in many situations to provide faster in-memory lookup. So maybe the problem is to decide which one to use in the particular case.

Just some personal views. Thanks again for this project!

[skywind3000]

OK，学院派还有一个问题，一个劲的在那里算旋转次数，根本不提重新上色，你看看 rbtree 里面换颜色的代码，一点不轻量级，动不动就是父亲，叔叔，祖父，祖父的兄弟，表亲，改一大堆。