Trädsort

Trädsort

Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	O ( n ²) (obalanserad) O ( n log n ) (balanserad)
Bästa möjliga prestanda	O ( n log n )
Genomsnittlig prestanda	O ( n log n )
Värsta tänkbara utrymmeskomplexitet	Θ( n )

En trädsortering är en sorteringsalgoritm som bygger ett binärt sökträd från de element som ska sorteras och sedan korsar trädet ( i ordning ) så att elementen kommer ut i sorterad ordning. Dess typiska användning är att sortera element online : efter varje infogning är uppsättningen av element som setts hittills tillgänglig i sorterad ordning.

Trädsortering kan användas som en engångssortering, men det är likvärdigt med quicksort eftersom både rekursivt partitionerar elementen baserat på en pivot, och eftersom quicksort är på plats och har lägre omkostnader, har trädsortering få fördelar jämfört med quicksort. Det har bättre worst case-komplexitet när ett självbalanserande träd används, men ännu mer overhead.

Effektivitet

Att lägga till ett objekt i ett binärt sökträd är i genomsnitt en O (log n ) process (i stor O-notation ) . Att lägga till n objekt är en O ( n log n ) process, vilket gör trädsortering till en "snabb sorteringsprocess". Att lägga till ett objekt till ett obalanserat binärt träd kräver O ( n ) tid i värsta fall: När trädet liknar en länkad lista ( degenererat träd ). Detta resulterar i ett värsta fall av O ( n ²) tid för denna sorteringsalgoritm. Detta värsta fall inträffar när algoritmen fungerar på en redan sorterad uppsättning, eller en som nästan är sorterad, omvänd eller nästan omvänd. Förväntad O ( n log n ) tid kan dock uppnås genom att blanda arrayen, men detta hjälper inte för lika objekt.

Det värsta tänkbara beteendet kan förbättras genom att använda ett självbalanserande binärt sökträd . Genom att använda ett sådant träd har algoritmen en O ( n log n ) prestanda i värsta fall, och är således gradoptimal för en jämförelsesort . Trädsorteringsalgoritmer kräver dock att separat minne tilldelas för trädet, i motsats till algoritmer på plats som quicksort eller heapsort . På flesta vanliga plattformar betyder detta att heap-minne måste användas, vilket är en betydande prestandaträff jämfört med quicksort och heapsort . När du använder ett splayträd som det binära sökträdet har den resulterande algoritmen (kallad splaysort ) den ytterligare egenskapen att den är en adaptiv sortering , vilket betyder att dess körtid är snabbare än O ( n log n ) för indata som nästan är sorterade.

Exempel

Följande trädsorteringsalgoritm i pseudokod accepterar en samling av jämförbara objekt och matar ut objekten i stigande ordning:

  
     
     
     
 
   
         
            
     
               
              
         
              
 
  
         
          
     
         
          
         
 
  
     
    
         
          
    
      STRUKTUR  BinaryTree  BinaryTree  :  LeftSubTree  Objekt  :  Nod  BinaryTree  :  RightSubTree  PROCEDUR  Infoga  (  BinaryTree  :  searchTree  ,  Objekt  :  objekt  )  IF  searchTree  .  Noden  ÄR  NULL  STÄLL  SENERA  SearchTree  .  Nod  TILL  objekt  ANNAT  OM  objektet  ÄR  MINDRE  ÄN  sökträd  .  Nod  DÅ  Infoga  (  sökträd  .  VänsterTräd  ,  objekt  )  ELSE  Infoga  (  sökträd  .  HögerSubträd  ,  objekt  )  PROCEDUR  InOrder  (  Binärträd  :  sökträd  )  OM  sökträd  .  Noden  ÄR  NULL  ,  AVSLUTA  SEN PROCEDUR  ANNARS  InOrder  (  searchTree  .  LeftSubTree  )  EMIT  searchTree  .  Node  InOrder  (  searchTree  .  RightSubTree  )  PROCEDUR  TreeSort  (  Collection  :  items  )  BinaryTree  :  searchTree  FÖR  VARJE  individuellItem  IN  items  Insert  (  searchTree  ,  individualItem  )  InOrder  (  searchTree  ) 

I en enkel funktionell programmeringsform skulle algoritmen (i Haskell ) se ut ungefär så här:

            

            
        
      
               
                

      
    
             

        
        dataträd  a  =  Blad  |  _  Nod  (  Träd  a  )  a  (  Träd  a  )  infoga  ::  Ord  a  =>  a  -  >  Träd  a  ->  Träd  a  insert  x  Löv  =  Nod  Löv  x  Lövinlägg  x  (  Nod  t  y  s  )  |  x  <=  y  =  Nod  (  infoga  x  t  )  y  s  |  x  >  y  =  Nod  t  y  (  infoga  x  s  )  platta  ::  Träd  a  ->  [  a  ]  ​​platta  Löv  =  []  platta  (  Nod  t  x  s  )  =  platta  t  ++  [  x  ]  ++  platta  s  trädort  ::  Ord  a  =>  [  a  ]  ->  [  a  ]  trädsorter  =  platta till  .  foldr  infoga  Blad 

I ovanstående implementering har både insättningsalgoritmen och hämtningsalgoritmen O ( n ²) värsta scenarier.

externa länkar

• Binary Tree Java Applet och förklaring på Wayback Machine (arkiverad 29 november 2016)
• Trädsort av en länkad lista
• Trädsortering i C++