Notices
Results 1 to 8 of 8

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

  1. #1 AVL, tower-of-Hanoi, red-black; Fundamental cost of tree sort algorithm. 
    New Member
    Join Date
    Oct 2021
    Posts
    4
    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.


    Last edited by cheeseandtomato; October 31st, 2021 at 09:15 PM.
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    1,195
    Your writing style leads to MEGO. I suggest much clarification.


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Oct 2021
    Posts
    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?
    Last edited by cheeseandtomato; October 31st, 2021 at 02:45 AM.
    Reply With Quote  
     

  5. #4  
    KJW
    KJW is online now
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,691
    Quote Originally Posted by cheeseandtomato View Post
    what is the relation between the tower-of-Hanoi and the Sierpiński triangle?
    https://en.wikipedia.org/wiki/Tower_...representation
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  6. #5  
    Forum Professor
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    1,195
    Quote Originally Posted by cheeseandtomato View Post
    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.
    Reply With Quote  
     

  7. #6  
    New Member
    Join Date
    Oct 2021
    Posts
    4
    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.
    Last edited by cheeseandtomato; November 6th, 2021 at 04:26 AM.
    Reply With Quote  
     

  8. #7  
    Forum Radioactive Isotope
    Join Date
    Feb 2009
    Posts
    4,939
    Quote Originally Posted by mathman View Post
    Your writing style leads to MEGO. I suggest much clarification.
    My eyes have taken a trip to Switzerland(rest in mucus)
    Reply With Quote  
     

  9. #8  
    New Member
    Join Date
    Oct 2021
    Posts
    4
    A node-set(triplet) in a quad-tree representation has three nodes, which is represented as a very simple triangle. In an AVL-tree basically, there are only 2(coarse-grained) classes of connected Abelian groups; because I can never be any simpler, if you can draw a simple triangle on the paper, and if you saw which direction the (parity-quasi-inverted) green bit moved when you rotated it(is it up or down), please teach me. The cost branches and duplicates exponentially because you have to take care of two servants(green and red) of each servant. ( You are using an exponential Boolean proof style F(n+1)=F(n)^G(n), which I never use. ) Because this is a quad-tree model, some parameters may need extra metric normalizations. It is well-known that a (constructive, explicit, verbatim) proof cost is always smaller (or equal) than a real simulation.; If the shortest known proof is exponential, the shortest known algorithm is similarly exponential. Any well-balanced tree has a very low global height; the height of a well-balanced tree almost always never changes; Any balancing method (whether red-black or AVL) explicitly or implicitly assumes a certain global invariant height parameter. A red-black tree is a simple binary-tree/quad-tree with an extra overflow cache (the red nodes); the overflow of the secondary cache( = red nodes) historically has never been considered; the red-black tree has 2 main costs; the perfect black-balance and the red-overflow swap-out (the red waterfall). If you push back the red overflow to the original black binary-tree/quad-tree, all the optimization gain is lost, because the black-red-black conversion is always worse than the direct black-black perfect balancing. Although nobody has ever noticed that an AVL-tree (basically) has an invariant height, asymtotically the height-growth probability is (stochastically) almost 0, because of the well-known simple fact lim (x - λlog x)/x =1. The balanced-tree height-growth/height-compression cost always obeys the simple irreversible Maxwell-Boltzman type statistics. Because an algorithm tries to save the rebalancing cost, this growth is (stochastically) irreversible. The red-light condition of an AVL-branch is a very tight recursive restriction ( = Boolean union of forbidding a rotation, because a green-to-red rotation is a very simple AVL double-fault); a red-light at the branch-root forbids any green-to-red rotations in the highest row; Roughly speaking, AVL-optimization-gain = Binary-balancing-rule-violation = #( AVL-deformation-group/Balancing-deformation-group) = green-to-red-unbalancing-deformation-count= red-insertions+red-rotations. Because the green-to-red rotation is (almost always) forbidden in the highest row, an explicit sub-tree height-compression occurs before (almost) every heighest-row optimization. By definition, AVL-optimization/AVL-insertion ~ 1. Recall that (one of the) main cost of the red-black algorithm is the secondary cache overflow ( =global red waterfall) ; we can naturally apply this simple fact to the AVL algorithm; the highest-row of the AVL-tree is a very simple overflow-cashe, and everything else is (basically) a very simple fixed-height trivial binary-tree balancing (which of course has no optimization, except the small non-highest-row overflow cache. This simple decomposition (highest-row + non-highest-rows) enables a natural assumption that the AVL algorithm has 3 main costs; the fixed-height perfect tree-balancing + non-highest-row overflow + highest-row-overflow. If you push back a node from the 2 overflow-caches to the original fixed-hight tree, all the optimization gain is lost; in other words, you have to manage the (height-)overflow within the highest row by horizonally moving the height-overflow from one place to another. Because the AVL height is basically (stocastically) invariant, the tree takes the same height sufficiently many times; in other words, this tree takes sufficiently many secondary-cache internal-swappings. It is well-known that the extra overflow capacity of the AVL tree is smaller than the red-black tree. The fixed-height tree problem is naturally identical to the simple 2-adic sampling height problem. Because each row explicitly has its own overflow-cache capacity, you can analyze the exact overflow swap-out flow speed (to the highest row). AVL-optimization = AVL-deformation/Balanced-deformation = green-to-red deformation group, and in a simple quad-tree model, a green-to-red rotation pushes down 1 sub-tree and pops up 2 sub-trees. It is well-known that the well-balanced sub-tree volume is exponential; the height-potential swap-out of a red-to-green rotation is likely to be (stocastically) exponential; in other words, the required explicit height compression (which must cancel the height-potential swap-out flow) of the global highest-row/tree-top is equally exponential (which has no optimization at all, because it's a balancing action in the balancing-deformation-group). To be strict, a 'balancing-deformation-group' is actually a (one-directional, irreversible, monotonic) semi-group. Similarly, because a red-black tree is a subset of a simple triple quad-tree tensor (quad x quad x quad), you can easily see that a red-black tree has at most only 2 overflow caches; In order to optimize the first quad-tree, the overflow is swapped-out to the second tree; the third tree is unoptimizable, because there is no more cache. An AVL-tree is a subset of a very simple double tri-tree tensor (tri x tri); the second tree is the red-light tree, which represents the overflowing root node of a sub-tree (= height-overflow) , and the first tree is the perfectly-balanced (green-ish) tree; if a node in the second (red) tree is empty ( =red hole), the corresponding first-tree element is a perfect green-light node (= balance 0). In this simple double tri-tree AVL representation, the (upper bound of) overflow capacity is 1/2 of the original (green-ish) perfect tri-tree/binary-tree; you can easily see that the second tri-tree (the red-light tri-tree) is unoptimizable, because it is the last cache in the overflow-cache chain; the red-black tree is a simple 3-cache chain, and the AVL tree is a simple 2-cache chain; the last tree in the chain is always unoptimizable and exponential, whether red-black or AVL.
    Last edited by cheeseandtomato; November 28th, 2021 at 11:38 AM.
    Reply With Quote  
     

Similar Threads

  1. Binary search tree
    By thedude_il in forum General Discussion
    Replies: 5
    Last Post: November 28th, 2011, 07:24 AM
  2. Dijkstra's Algorithm(Priority- First Search)
    By Mavericks in forum Computer Science
    Replies: 4
    Last Post: July 26th, 2011, 10:25 AM
  3. Binary search tree problem
    By tonybasil in forum Computer Science
    Replies: 0
    Last Post: February 16th, 2011, 10:03 PM
  4. search algorithm VS Sql command query
    By wintersky in forum Computer Science
    Replies: 0
    Last Post: September 9th, 2008, 09:43 PM
  5. Replies: 1
    Last Post: April 4th, 2008, 11:13 PM
Tags for this Thread

View Tag Cloud

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
  •