ICS2210 - DSA2- Solved

AVL     Trees  and     Red-Black     Trees  
 

 •      Write   a          command       line      program         with     the       following        behaviour.      

•      Let       𝑛          be        a          random          number          between         1000   and      3000.  

•      Create a          set       𝑋          containing      𝑛          integers.         Each    integer            must    be a          random          number          in         the       range  −3000 and      +3000.           Make   sure that     there   are      no        duplicates       in         this      set.      

            

Set X contains ??? elements 

            

•      Let       𝑚         be        a          random          number          between         500     and      1000.  

•      Create a          second            set       𝑌          containing      𝑚         integers.         Each    integer must    be        a          random          number          in         the       range  −3000 and      +3000. Make   sure    that     there   are      no        duplicates       in         this      set.      

            

Set Y contains ??? elements 

            

•      Note    that     the       sets     X          and      Y          may     have    elements         in         common. 

            

Sets X and Y have ??? elements in common 

            

•      Insert  all        the       elements         in         the       set       X          into     an        AVL     tree     and into     a          Red-Black       tree.    Both    are      binary search trees.   The     AVL     tree    and Red-Black     tree    implementations    must   be       your   own.   

•      After    inserting         all        the       values into     each    tree,    you      must    show:  the number          of         rotations        performed     in         total,    the       height of         the       tree, the       number          of         nodes  in         the       tree,    and      the       number          of comparison    operations     (left/right       decisions)       made   in         total.    

            

AVL: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ?? RBT: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ?? 

            

•      Delete all        the       elements         in         the       set       Y          from    the       AVL     tree     and from    the       RedBlack        Tree.   After   deleting          all        the       values into     each    tree, you      must    show:  the       number          of         rotations        performed     in         total,    the height of         the       tree,    the       number          of         nodes  in         the       tree,    and      the number          of         comparison    operations     (left/right       decisions)       made   in total.    

            

AVL: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ?? RBT: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ?? 

            

•      Let       𝑘          be        a          random          number          between         1000   and      2000.  

•      Create a          third    set       𝑍          containing      𝑘          integers.         Each    integer must    be        a          random          number          in         the       range  −3000 and      +3000. Make   sure    that     there   are      no        duplicates       in         this      set.      

•      Search for       every  element          in         the       set       𝑍          in         both    the       AVL     tree and      the       RedBlack        tree.    Note    that     a          search may     be        successful       or not.    

 k is ??? 

AVL: ??? total comparisons required 

RBT: ??? total comparisons required