TechCodeview

Först kommer vi att förstå binärt träd och binärt sökträd separat, och sedan kommer vi att titta på skillnaderna mellan ett binärt träd och ett binärt sökträd.

Vad är ett binärt träd?

A Binärt träd är enPekare till vänster barn:Den lagrar referensen för den vänstra underordnade noden.Pekare till rätt barn:Den lagrar referensen för den högra underordnade noden.Dataelement:Dataelementet är värdet på data som lagras av noden.

Det binära trädet kan representeras som:

I figuren ovan kan vi observera att varje nod innehåller ytterst 2 barn. Om någon nod inte innehåller vänster eller höger underordnad så skulle värdet på pekaren med avseende på det underordnade vara NULL.

Grundläggande terminologier som används i ett binärt träd är:

Rotnod:Rotnoden är den första eller den översta noden i ett binärt träd.Föräldernod:När en nod är ansluten till en annan nod genom kanter, är den noden känd som en överordnad nod. I ett binärt träd kan föräldranoden ha maximalt 2 barn.Barnnod:Om en nod har sin föregångare är den noden känd som en barnnod .Bladnod:Noden som inte innehåller något barn som kallas en lövnod .Intern nod:Noden som har minst 2 barn känd som en intern nod .Djup av en nod:Avståndet från rotnoden till den givna noden kallas a djupet av en nod . Vi tillhandahåller etiketter till alla noder som rotnoden är märkt med 0 eftersom den inte har något djup, barn till rotnoderna är märkta med 1, barn till rotnoden är märkta med 2.Höjd:Det längsta avståndet från rotnoden till lövnoden är nodens höjd .

I ett binärt träd finns det ett träd som kallas a perfekt binärt träd . Det är en träd där alla interna noder måste innehålla två noder, och alla bladnoder måste vara på samma djup. I fallet med ett perfekt binärt träd kan det totala antalet noder som finns i ett binärt träd beräknas genom att använda följande ekvation:

n = 2^m+1-1

där n är antalet noder, m är djupet av en nod.

Vad är ett binärt sökträd?

A Binärt sökträd är ett träd som följer någon ordning för att ordna elementen, medan det binära trädet inte följer någon ordning. I ett binärt sökträd måste värdet på den vänstra noden vara mindre än föräldernoden, och värdet på den högra noden måste vara större än föräldernoden.

Låt oss förstå konceptet med ett binärt sökträd genom exempel.

I figuren ovan kan vi observera att värdet på rotnoden är 15, vilket är större än värdet på alla noder i det vänstra underträdet. Värdet på rotnoden är mindre än värdena för alla noder i ett högerunderträd. Nu flyttar vi till rotnodens vänstra underordnade. 10 är större än 8 och mindre än 12; det uppfyller också egenskapen för det binära sökträdet. Nu flyttar vi till det högra underordnade av rotnoden; värdet 20 är större än 17 och mindre än 25; det uppfyller också egenskapen för binärt sökträd. Därför kan vi säga att trädet som visas ovan är det binära sökträdet.

Nu, om vi ändrar värdet på 12 till 16 i ovanstående binära träd, måste vi ta reda på om det fortfarande är ett binärt sökträd eller inte.

Värdet på rotnoden är 15 vilket är större än 10 men mindre än 16, så det uppfyller inte egenskapen för det binära sökträdet. Därför är det inte ett binärt sökträd.

Operationer på binärt sökträd

Vi kan utföra infogning, radering och sökoperationer på det binära sökträdet. Låt oss förstå hur en sökning utförs på en binär sökning. Det binära trädet visas nedan där vi måste utföra sökoperationen:

Anta att vi måste söka 10 i ovanstående binära träd. För att utföra den binära sökningen kommer vi att överväga alla heltal i en sorterad array. Först skapar vi en komplett lista i ett sökutrymme, och alla siffror kommer att finnas i sökutrymmet. Sökutrymmet är markerat med två pekare, dvs start och slut. Arrayen i ovanstående binära träd kan representeras som

Först kommer vi att beräkna mittelementet och jämföra mittelementet med elementet som ska sökas. Mellanelementet beräknas genom att använda n/2. Värdet på n är 7; därför är mittelementet 15. Mellanelementet är inte lika med det sökta elementet, dvs 10.

Obs: Om elementet som söks är mindre än mittelementet, kommer sökningen att utföras i den vänstra halvan; annars kommer sökning att göras på den högra halvan. Vid jämlikhet återfinns elementet.

Eftersom elementet som ska sökas är mindre än mittelementet, så kommer sökningen att utföras på den vänstra arrayen. Nu är sökningen reducerad till hälften, som visas nedan:

Mittelementet i den vänstra arrayen är 10, vilket är lika med det sökta elementet.

Tidskomplexitet

I en binär sökning finns det n element. Om mittelementet inte är lika med det sökta elementet, reduceras sökutrymmet till n/2, och vi kommer att fortsätta att minska sökutrymmet med n/2 tills vi hittade elementet. I hela reduktionen, om vi flyttar från n till n/2 till n/4 och så vidare, kommer det att ta log₂n steg.

Skillnader mellan binärt träd och binärt sökträd