Diagram: Binary Search Tree, Insertion

Assume that the numbers 67, 29, 6, 44, 65, 39, 30, 12, 38, 3, 99, 23, 11, 71, 10, 5, 70, 9, 81, 7, 73, 19 are going to be inserted. Notice that the tree does not offer the same numbers for insertion. Therefore, in database aspect, the tree’s node seems like a primary key with unique. Assume that each number is an element of its node.

 

67ROOT

 

          67ROOT                      

         PATH                   because 29 < 67; Notice that lesser goes left greater goes right

29 LEAF

 

 

                   67ROOT

    PATH

          29                        because 6 < 67 and 6 < 29

 

6 LEAF

 

                   67ROOT

 

          29                        because 44 < 67 and 44 > 29

                   PATH

6                 44 LEAF

 

 

                   67ROOT

 

          29

                   PATH                   because 65 < 67 and 65 > 29 and 65 > 44

6                 44

 

                             65 LEAF

 

                   67ROOT

 

          29

                                      because 39 < 67 and 39 > 29 and 39 < 44

6                 44

    PATH

          39 LEAF    65

 

 

 

                   67ROOT

 

          29

                                                  because 30 < 67 and 30 > 29 and 30 < 44 and 30 < 39

6                 44

    PATH

          39               65

 

30 LEAF

 

                   67ROOT

 

          29

       PATH                                        because 12 < 67 and 12 < 29 and 12 > 6

6                           44

           

LEAF   12      39               65

 

30

 

                   67ROOT

 

          29                        38 < 67 and 38 > 29 and 38 < 44 and 38 < 39 and 38 > 30

                           PATH                    

6                           44

 

          12     39               65

 

30              

 


          38 LEAF

 

                                      67ROOT

 

                             29                                  3 < 67 and 3 < 29 and 3 < 6

            PATH

                   6                           44

 

LEAF  3                  12     39               65

 

30              

 


                             38

 

 

                                      67  ROOT

                                                PATH

                             29               99 LEAF                          99 > 67

 

                   6                           44

 

          3                 12     39               65

 

30              

 


                             38

 

                                      67      ROOT

 

                             29                                            99

            PATH

                   6                                              44

 

          3                 12                        39               65

 

LEAF 23       30       23 < 67 and 23 < 29 and 23 > 6 and 23 > 12   

                                                    

                                                38

 

                                      67     ROOT

 

                             29                                            99

 

                   6                                              44

                          PATH

          3                 12                        39               65

 

LEAF  11                23     30              

                                                      11 < 67 and 11 < 29 and 11 > 6 and 11 < 12

                                                38

 

 

 

 

 

 

 

 

                                                          67ROOT

                                                                                     PATH

                             29                                                               99

 

                   6                                              44               71 LEAF

 

          3                 12                        39               65

 

11               23     30                                            71 > 67 and 71 < 99

 


                                                38

 

                                                          67ROOT

 


                             29                                                               99

            PATH

                   6                                              44               71

 

          3                 12                        39               65

 

11               23     30              

 


10 LEAF                                    38

10 < 67 and 10 < 29 and 10 > 6 and 10 < 12 and 10 < 11

 

                                                          67ROOT

 


                             29                                                                        99

            PATH

                   6                                                       44               71

 

          3                           12                        39               65

 

LEAF 5      11               23     30              

 


10                                            38

5 < 67 and 5 < 29 and 5 < 6 and 5 > 3

 

 

 

 

 

 

 

                                                          67ROOT

 


                             29                                                                                  99

                                                                                                   PATH

                   6                                                       44                        71

 

          3                           12                        39               65     70 LEAF

 

5       11               23     30              

 


10                                            38

70 > 67 and 70 < 99 and 70 < 71

                            

                                                             67ROOT

 


                             29                                                                                  99

 

                   6                                                       44                        71

                                     PATH

          3                           12                        39               65     70

 

5       11               23     30              

 


10                                            38

 

          9 LEAF

9 < 67 and 9 < 29 and 9 > 6 and 9 < 12 and 9 < 11 and 9 < 10

 

                                                          67ROOT

 


                             29                                                                                  99

                                                                                                    PATH

                   6                                                       44                        71

 


          3                           12                        39               65     70               81 LEAF

 

5       11               23     30              

  81 > 67 and 81 < 99 and 81 > 71

10                                            38

 

          9

         

                                                67ROOT

 


                             29                                                                                  99

 

                   6                                                       44                        71

 


          3                           12                        39               65     70               81

 

5       11               23     30              

 


10                                            38

    PATH

          9

 

7 LEAF    7 < 67 and 7 < 29 and 7 > 6 and 7 < 12 and 7 < 11 and 7 < 10 and 7 < 9

 

                                                          67ROOT

 


                             29                                                                                  99

 

                   6                                                       44                        71

                                                                                                                 PATH

          3                           12                        39               65     70               81

 


5       11               23     30                        LEAF 73

 


10                                            38

 

          9

                             73 > 67 and 73 < 99 and 73 > 71 and 73 < 81

7

 

 

 

 

 

 

 

 

 

 

 

 

Tree

Depth

                                                                        67ROOT                                                                                                                                                                                                                           0

 

                                    29                                                                                99                            1

 


                        6                                                                      44                                 71             2

                                         PATH

            3                                  12                                 39                     65         70                81      3

 

5          11                     23         30                                                                             4

 


10                     19      LEAF                  38                                                                 5

 

            9                                                                                                                                                 6

 

7                                                                                                                                                              7   

 

19 < 67 and 19 < 29 and 19 > 6 and 19 > 12 and 19 < 23                                                                     8         

 

 

Tree Depth: 7

Balance/Un-balance: Un-balance

 

_ IFF search engine (ひ114715419.552), ア メ リ カ   緬 甸   .網     usamyanmar.net     ;

  

 

Up