# Thread: AVL, tower-of-Hanoi, red-black; Fundamental cost of tree sort algorithm.

1. Yesterday, I asked about the basic AVL cost and explained the tower-of-Hanoi cost structure of a very simple pre-re-balancing AVL algorithm in Stackexchange. Today, I found my explanation deleted. (Almost) everybody knows about the very simple exponential tower-of-Hanoi cost structure, and you can naturally guess that similar structures are found in many other algorithms. The symmetric groups are non-comutative; there is no simple isomorphism between the original sorting and the logarithmic tree swapping (assuming the mapping volume is logarithmic); a simple substitution generates a massive tree perturbation. Because I knew less about AVL tree than red-black tree, my first (simple) normalization of the AVL algorithm was {left,even,right} ~ {down,0,up} ~ {green,green,red} , which is a coarse-grained 2-adic rounding. In order to deterministically clear one red-light (excluding the simple subtree costs), you must first move down one new green-light from the tree-top, which is generated by a simple rotation. In order to move down one green-light, you must clear every red-light one by one. The node doesn't move; only the green bits move (just as the pixels of the PC screen flow.) The (partial) cost of the AVL algorithm (excluding the subtree cost) is (roughly) summerized as dF(y)/dy> ∫F(y)dy; in other words, partial cost=exp(height); this is a very simple exponential cost structure with the randomized bad-balance height. Because the green pixels move down, the red pixels move up; it resembles the global red-waterfall of the red-black tree; the red pixel flow direction is the same. The tree-top of a tree algorithm always works as a very simple heatbath. Because the red-green distribution is randomly flipped after every node insertion, the tree is in a hot equilibrium state. The red-entropy swap-out is (super-) linear to time.

2.

4. No wonder nobody is interested. I think my writing style is OK; it's just too new. For example, I had to write 'red-light' and 'pixel', because otherwise nobody can understand the simple meanings. It sometimes gets very hard to explain simple facts to others, if they don't have the common simple intuitions. I am also very surprised to know that nobody knows about the simple tower-of-Hanoi mechanism; I thought it was trivial. Don't you think that the Sierpiński triangle and the AVL-tree have (more or less) the same funny shape?

5. Originally Posted by cheeseandtomato
what is the relation between the tower-of-Hanoi and the Sierpiński triangle?
https://en.wikipedia.org/wiki/Tower_...representation

6. Originally Posted by cheeseandtomato
No wonder nobody is interested. I think my writing style is OK; it's just too new. For example, I had to write 'red-light' and 'pixel', because otherwise nobody can understand the simple meanings. It sometimes gets very hard to explain simple facts to others, if they don't have the common simple intuitions. I am also very surprised to know that nobody knows about the simple tower-of-Hanoi mechanism; I thought it was trivial. Don't you think that the Sierpiński triangle and the AVL-tree have (more or less) the same funny shape?
My comment was not about content, but presentation. It is about as readable as a James Joyce novel.

7. When you are not interested in something, sometimes you can't see simple things at all. An AVL node-set in a quad-tree representation has 4 branches, and if you want to avoid an absurd loop logic, you usually want to define everything in a simple and atomic manner. As long as the monotonic cost valuation is concerned, this style is the best. You must avoid unverified probability estimations and trust only the simple explicit counting. The red-black tree is a very simple quad-tree cost structure with the height-parity, and you can naturally apply it to AVL. I think the main reason for the simplicity of the quad-tree model is the topological Jordan isolation, which naturally enables atomic decomposition. Historically, this simple method was used by (at least as old as) Hamilton. A relatively flat AVL-tree has a shape that is more or less similar to the tower-of-hanoi; The height parity defines the maximally commutative (isolated) operators.

8. Originally Posted by mathman
My eyes have taken a trip to Switzerland(rest in mucus)

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement