一个问题 about c-sharp-algorithms HOT 4 CLOSED

Hey @hwgeone,

Sorry for the late reply. Can you please link the code block you're referring to from the source file?

Cheers,
Ahmad

from c-sharp-algorithms.

from c-sharp-algorithms.

Hi @aalhour

You confirm, look forward to reply
Cheers,
Wei Huang

from c-sharp-algorithms.

Hi @hwgeone,

Sorry for the late reply. I am not sure about your proposal, probably my inline comments are misleading, but I think rotation should happen to the right, that's why the sibling gets coloured as Black and the parent as Red. I have implemented your suggestion and visualised the final result of the tree and I got the following:

With current implementation:

                 ........4........            
                /                 \           
            ..0.999..          ...10...       
           /         \        /        \      
       ..0.997.       2      .8.      .14.    
      /        \     / \    /   \    /    \   
   .0.972     0.998 1   3   6    9   12    17 
  /      \                 / \      / \   / \ 
0.901   0.996             5   7    11 13 15 18
        /                                     
      0.975                                   

With your suggestion:

                 .......4......              
                /              \             
            ..0.999..        ...8...         
           /         \      /       \        
       ..0.997.       2     6      ..12.     
      /        \     / \   / \    /     \    
   .0.972     0.998 1   3 5   7   10     15  
  /      \                       / \    / \  
0.901   0.996                   9  11  14 17 
        /                              /   \ 
      0.975                           13   18

Notice how the balancing on the right side of the tree differs. It is still a Red-Black Tree, but the colouring logic changed it to strictly become a Right-Leaning RB Tree.

I forgot which subtype of an RB Tree is this (RL or LL), so I think I am going to re-implement it to become LL RB Tree which is much simpler to reason about than the current implementation.

Would you like to submit a PR to re-place the current implementation with a simpler Left-Leaning RB Tree implementation?

Cheers,
Ahmad

from c-sharp-algorithms.