Skip to content

Latest commit

 

History

History
550 lines (468 loc) · 28.3 KB

STUDY_CASE.md

File metadata and controls

550 lines (468 loc) · 28.3 KB

Binary Search Tree Visualization Study Case

I. Fixed Node/Space Length Algorithm

II. Matching Adaptive Node/Space Length Algorithm

III. Adaptive Node Length with Fixed Space Length Algorithm

IV. Hybrid Algorithm

I. Fixed Node/Space Length Algorithm

  • Set both nodes' and spaces' lengths to a Fixed value (3 chars for example).
Advantages Disadvantages
Nodes with large values won't be displayed properly
Nodes' and spaces' lengths should be either even or odd but not both

fixed-3-char-length Tree

                     0X0                     
                     / \                     
                    /   \                    
                   /     \                   
                  /       \                  
                 /         \                 
                /           \                
               /             \               
              /               \              
             /                 \             
            /                   \            
           /                     \           
         0X0                     0X0         
         / \                     / \         
        /   \                   /   \        
       /     \                 /     \       
      /       \               /       \      
     /         \             /         \     
   0X0         0X0         0X0         0X0   
   / \         / \         / \         / \   
  /   \       /   \       /   \       /   \  
0X0   0X0   0X0   0X0   0X0   0X0   0X0   0X0

II. Matching Adaptive Node/Space Length Algorithm

  • Set both nodes' and spaces' lengths to the maximum node value's length.
Advantages Disadvantages
Visually symmetric 1-char-length node/space trees are bugged
Node length is adaptive Trees' width/height is too big
Consecutive even-length trees and odd-length trees have different heights
Nodes' and spaces' lengths should be either even or odd but not both

1-char-length Tree (bugged)

       X       
      / \      
     /   \     
    /     \    
   X       X   
  / \     / \  
 X   X   X   X 
X X X X X X X X

2-char-length Tree

              XX              
              /\              
             /  \             
            /    \            
           /      \           
          /        \          
         /          \         
        /            \        
      XX              XX      
      /\              /\      
     /  \            /  \     
    /    \          /    \    
  XX      XX      XX      XX  
  /\      /\      /\      /\  
XX  XX  XX  XX  XX  XX  XX  XX

3-char-length Tree

                     0X0                     
                     / \                     
                    /   \                    
                   /     \                   
                  /       \                  
                 /         \                 
                /           \                
               /             \               
              /               \              
             /                 \             
            /                   \            
           /                     \           
         0X0                     0X0         
         / \                     / \         
        /   \                   /   \        
       /     \                 /     \       
      /       \               /       \      
     /         \             /         \     
   0X0         0X0         0X0         0X0   
   / \         / \         / \         / \   
  /   \       /   \       /   \       /   \  
0X0   0X0   0X0   0X0   0X0   0X0   0X0   0X0

4-char-length Tree

                            0XX0                            
                             /\                             
                            /  \                            
                           /    \                           
                          /      \                          
                         /        \                         
                        /          \                        
                       /            \                       
                      /              \                      
                     /                \                     
                    /                  \                    
                   /                    \                   
                  /                      \                  
                 /                        \                 
                /                          \                
               /                            \               
            0XX0                            0XX0            
             /\                              /\             
            /  \                            /  \            
           /    \                          /    \           
          /      \                        /      \          
         /        \                      /        \         
        /          \                    /          \        
       /            \                  /            \       
    0XX0            0XX0            0XX0            0XX0    
     /\              /\              /\              /\     
    /  \            /  \            /  \            /  \    
   /    \          /    \          /    \          /    \   
0XX0    0XX0    0XX0    0XX0    0XX0    0XX0    0XX0    0XX0

5-char-length Tree

                                   00X00                                   
                                    / \                                    
                                   /   \                                   
                                  /     \                                  
                                 /       \                                 
                                /         \                                
                               /           \                               
                              /             \                              
                             /               \                             
                            /                 \                            
                           /                   \                           
                          /                     \                          
                         /                       \                         
                        /                         \                        
                       /                           \                       
                      /                             \                      
                     /                               \                     
                    /                                 \                    
                   /                                   \                   
                  /                                     \                  
               00X00                                   00X00               
                / \                                     / \                
               /   \                                   /   \               
              /     \                                 /     \              
             /       \                               /       \             
            /         \                             /         \            
           /           \                           /           \           
          /             \                         /             \          
         /               \                       /               \         
        /                 \                     /                 \        
     00X00               00X00               00X00               00X00     
      / \                 / \                 / \                 / \      
     /   \               /   \               /   \               /   \     
    /     \             /     \             /     \             /     \    
   /       \           /       \           /       \           /       \   
00X00     00X00     00X00     00X00     00X00     00X00     00X00     00X00

III. Adaptive Node Length with Fixed Space Length Algorithm

  • Set spaces' length to 3 chars in case node length is odd.
  • Set spaces' length to 4 chars in case node length is even.
  • Set nodes' length to the maximum node value's length.
Advantages Disadvantages
Node length is adaptive Spacing between long-length-leaves is visually low
Trees' width/height is smaller than Matching Node/Space length Trees Nodes' and spaces' lengths should be either even or odd but not both
1-char-node-length trees aren't bugged
Consecutive even-length trees and odd-length trees have same height

1-char-length-node + fixed-3-char-length-space Tree

              X              
             / \             
            /   \            
           /     \           
          /       \          
         /         \         
        /           \        
       /             \       
      X               X      
     / \             / \     
    /   \           /   \    
   /     \         /     \   
  X       X       X       X  
 / \     / \     / \     / \ 
X   X   X   X   X   X   X   X

2-char-length-node + fixed-4-char-length-space Tree

                     XX                     
                     /\                     
                    /  \                    
                   /    \                   
                  /      \                  
                 /        \                 
                /          \                
               /            \               
              /              \              
             /                \             
            /                  \            
           /                    \           
         XX                      XX         
         /\                      /\         
        /  \                    /  \        
       /    \                  /    \       
      /      \                /      \      
     /        \              /        \     
   XX          XX          XX          XX   
   /\          /\          /\          /\   
  /  \        /  \        /  \        /  \  
XX    XX    XX    XX    XX    XX    XX    XX

3-char-length-node + fixed-3-char-length-space Tree

                     0X0                     
                     / \                     
                    /   \                    
                   /     \                   
                  /       \                  
                 /         \                 
                /           \                
               /             \               
              /               \              
             /                 \             
            /                   \            
           /                     \           
         0X0                     0X0         
         / \                     / \         
        /   \                   /   \        
       /     \                 /     \       
      /       \               /       \      
     /         \             /         \     
   0X0         0X0         0X0         0X0   
   / \         / \         / \         / \   
  /   \       /   \       /   \       /   \  
0X0   0X0   0X0   0X0   0X0   0X0   0X0   0X0

4-char-length-node + fixed-4-char-length-space Tree

                            0XX0                            
                             /\                             
                            /  \                            
                           /    \                           
                          /      \                          
                         /        \                         
                        /          \                        
                       /            \                       
                      /              \                      
                     /                \                     
                    /                  \                    
                   /                    \                   
                  /                      \                  
                 /                        \                 
                /                          \                
               /                            \               
            0XX0                            0XX0            
             /\                              /\             
            /  \                            /  \            
           /    \                          /    \           
          /      \                        /      \          
         /        \                      /        \         
        /          \                    /          \        
       /            \                  /            \       
    0XX0            0XX0            0XX0            0XX0    
     /\              /\              /\              /\     
    /  \            /  \            /  \            /  \    
   /    \          /    \          /    \          /    \   
0XX0    0XX0    0XX0    0XX0    0XX0    0XX0    0XX0    0XX0

5-char-length-node + fixed-3-char-length-space Tree

                            00X00                            
                             / \                             
                            /   \                            
                           /     \                           
                          /       \                          
                         /         \                         
                        /           \                        
                       /             \                       
                      /               \                      
                     /                 \                     
                    /                   \                    
                   /                     \                   
                  /                       \                  
                 /                         \                 
                /                           \                
               /                             \               
            00X00                           00X00            
             / \                             / \             
            /   \                           /   \            
           /     \                         /     \           
          /       \                       /       \          
         /         \                     /         \         
        /           \                   /           \        
       /             \                 /             \       
    00X00           00X00           00X00           00X00    
     / \             / \             / \             / \     
    /   \           /   \           /   \           /   \    
   /     \         /     \         /     \         /     \   
00X00   00X00   00X00   00X00   00X00   00X00   00X00   00X00

6-char-length-node + fixed-4-char-length-space Tree

                                   00XX00                                   
                                     /\                                     
                                    /  \                                    
                                   /    \                                   
                                  /      \                                  
                                 /        \                                 
                                /          \                                
                               /            \                               
                              /              \                              
                             /                \                             
                            /                  \                            
                           /                    \                           
                          /                      \                          
                         /                        \                         
                        /                          \                        
                       /                            \                       
                      /                              \                      
                     /                                \                     
                    /                                  \                    
                   /                                    \                   
               00XX00                                  00XX00               
                 /\                                      /\                 
                /  \                                    /  \                
               /    \                                  /    \               
              /      \                                /      \              
             /        \                              /        \             
            /          \                            /          \            
           /            \                          /            \           
          /              \                        /              \          
         /                \                      /                \         
     00XX00              00XX00              00XX00              00XX00     
       /\                  /\                  /\                  /\       
      /  \                /  \                /  \                /  \      
     /    \              /    \              /    \              /    \     
    /      \            /      \            /      \            /      \    
00XX00    00XX00    00XX00    00XX00    00XX00    00XX00    00XX00    00XX00

7-char-length-node + fixed-3-char-length-space Tree

                                   000X000                                   
                                     / \                                     
                                    /   \                                    
                                   /     \                                   
                                  /       \                                  
                                 /         \                                 
                                /           \                                
                               /             \                               
                              /               \                              
                             /                 \                             
                            /                   \                            
                           /                     \                           
                          /                       \                          
                         /                         \                         
                        /                           \                        
                       /                             \                       
                      /                               \                      
                     /                                 \                     
                    /                                   \                    
                   /                                     \                   
               000X000                                 000X000               
                 / \                                     / \                 
                /   \                                   /   \                
               /     \                                 /     \               
              /       \                               /       \              
             /         \                             /         \             
            /           \                           /           \            
           /             \                         /             \           
          /               \                       /               \          
         /                 \                     /                 \         
     000X000             000X000             000X000             000X000     
       / \                 / \                 / \                 / \       
      /   \               /   \               /   \               /   \      
     /     \             /     \             /     \             /     \     
    /       \           /       \           /       \           /       \    
000X000   000X000   000X000   000X000   000X000   000X000   000X000   000X000

IV. Hybrid Algorithm

  • Set spaces' length to 3 chars or 4 chars depending on node length value is even or odd.
  • Set nodes' length to the maximum node value's length and type (odd/even).
Advantages Disadvantages
Nodes' and spaces' lengths can be both even and odd in the same tree
Branching & spacing depends on whether the node length value is even or odd

Hybrid Trees

+----------------------------------------------+-----------------------------------------------+
|   2-char-length-node + 4-char-length-space   |   3-char-length-node + 3-char-length-space    |
+----------------------------------------------+-----------------------------------------------+
|                      XX                      |                      0X0                      |
|                      /\                      |                      / \                      |
|                     /  \                     |                     /   \                     |
|                    /    \                    |                    /     \                    |
|                   /      \                   |                   /       \                   |
|                  /        \                  |                  /         \                  |
|                 /          \                 |                 /           \                 |
|                /            \                |                /             \                |
|               /              \               |               /               \               |
|              /                \              |              /                 \              |
|             /                  \             |             /                   \             |
|            /                    \            |            /                     \            |
|          XX                      XX          |          0X0                     0X0          |
|          /\                      /\          |          / \                     / \          |
|         /  \                    /  \         |         /   \                   /   \         |
|        /    \                  /    \        |        /     \                 /     \        |
|       /      \                /      \       |       /       \               /       \       |
|      /        \              /        \      |      /         \             /         \      |
|    XX          XX          XX          XX    |    0X0         0X0         0X0         0X0    |
|    /\          /\          /\          /\    |    / \         / \         / \         / \    |
|   /  \        /  \        /  \        /  \   |   /   \       /   \       /   \       /   \   |
| XX    XX    XX    XX    XX    XX    XX    XX | 0X0   0X0   0X0   0X0   0X0   0X0   0X0   0X0 |
+----------------------------------------------+-----------------------------------------------+

+----------------------------------------------+-----------------------------------------------+
|               Hybrid-even-root               |                Hybrid-odd-root                |
+----------------------------------------------+-----------------------------------------------+
|                      XX                      |                      0X0                      |
|                      /\                      |                      / \                      |
|                     /  \                     |                     /   \                     |
|                    /    \                    |                    /     \                    |
|                   /      \                   |                   /       \                   |
|                  /        \                  |                  /         \                  |
|                 /          \                 |                 /           \                 |
|                /            \                |                /             \                |
|               /              \               |               /               \               |
|              /                \              |              /                 \              |
|             /                  \             |             /                   \             |
|            /                    \            |            /                     \            |
|          XX                     0X0          |          XX                      0X0          |
|          /\                     / \          |          /\                      / \          |
|         /  \                   /   \         |         /  \                    /   \         |
|        /    \                 /     \        |        /    \                  /     \        |
|       /      \               /       \       |       /      \                /       \       |
|      /        \             /         \      |      /        \              /         \      |
|    XX         0X0         XX          0X0    |    XX         0X0          XX          0X0    |
|    /\         / \         /\          / \    |    /\         / \          /\          / \    |
|   /  \       /   \       /  \        /   \   |   /  \       /   \        /  \        /   \   |
| XX   0X0   XX    0X0   XX   0X0    XX    0X0 | XX   0X0   XX    0X0    XX   0X0    XX    0X0 |
+----------------------------------------------+-----------------------------------------------+