სრული ორობითი ხე vs სრული ორობითი ხე
ორობითი ხე არის ხე, სადაც თითოეულ კვანძს ჰყავს ერთი ან ორი შვილი. ბინარულ ხეში კვანძს არ შეიძლება ჰყავდეს ორზე მეტი შვილი. ბინარულ ხეში ბავშვებს უწოდებენ "მარცხენა" და "მარჯვენა" ბავშვებს. ბავშვის კვანძები შეიცავს მითითებას მათ მშობელზე. სრული ორობითი ხე არის ორობითი ხე, რომელშიც ბინარული ხის ყველა დონე მთლიანად არის შევსებული, გარდა ბოლო დონისა. შეუვსებელ დონეზე, კვანძები მიმაგრებულია ყველაზე მარცხენა პოზიციიდან დაწყებული. სრული ბინარული ხე არის ხე, რომელშიც ხის ყველა კვანძს ჰყავს ორი შვილი, გარდა ხის ფოთლებისა.
რა არის სრული ორობითი ხე?
სრული ორობითი ხე არის ბინარული ხე, რომელშიც ხის ყველა კვანძს აქვს ზუსტად ნული ან ორი შვილი. სხვა სიტყვებით რომ ვთქვათ, ხის ყველა კვანძს ფოთლების გარდა ჰყავს ზუსტად ორი შვილი. ქვემოთ მოყვანილი სურათი 1 ასახავს სრულ ბინარულ ხეს. სრულ ბინარულ ხეში კვანძების რაოდენობა (n), ლავების რაოდენობა (l) და შიდა კვანძების რაოდენობა (i) დაკავშირებულია სპეციალურად ისე, რომ თუ რომელიმე მათგანს იცნობთ, შეგიძლიათ განსაზღვროთ დანარჩენი ორი. მნიშვნელობები შემდეგნაირად:
1. თუ სრულ ბინარულ ხეს აქვს i შიდა კვანძები:
– ფოთლების რაოდენობა l=i+1
– კვანძების საერთო რაოდენობა n=2i+1
2. თუ სრულ ბინარულ ხეს აქვს n კვანძი:
– შიდა კვანძების რაოდენობა i=(n-1)/2
– ფოთლების რაოდენობა l=(n+1)/2
3. თუ სრულ ორობით ხეს აქვს l ფოთოლი:
– კვანძების საერთო რაოდენობა n=2l-1
– შიდა კვანძების რაოდენობა i=l-1
რა არის სრული ორობითი ხე?
როგორც ნაჩვენებია სურათზე 2, სრული ორობითი ხე არის ორობითი ხე, რომელშიც ხის ყველა დონე მთლიანად არის შევსებული, გარდა ბოლო დონისა. ასევე, ბოლო დონეზე, კვანძები უნდა იყოს მიმაგრებული ყველაზე მარცხენა პოზიციიდან დაწყებული. h სიმაღლის სრული ორობითი ხე აკმაყოფილებს შემდეგ პირობებს:
– ძირეული კვანძიდან ბოლო დონის ზემოთ დონე წარმოადგენს h-1 სიმაღლის სრულ ბინარულ ხეს
– ერთ ან მეტ კვანძს ბოლო დონეზე შეიძლება ჰყავდეს 0 ან 1 შვილი
– თუ a, b არის ორი კვანძი ბოლო დონეზე ზემოთ, მაშინ a-ს ჰყავს b-ზე მეტი შვილი, თუ და მხოლოდ იმ შემთხვევაში, თუ a მდებარეობს b-ის მარცხნივ.
რა განსხვავებაა სრულ ორობით ხესა და სრულ ორობით ხეს შორის?
სრულ ბინარულ ხეებსა და სრულ ბინარულ ხეებს აშკარა განსხვავება აქვთ. მიუხედავად იმისა, რომ სრული ორობითი ხე არის ორობითი ხე, რომელშიც ყველა კვანძს ჰყავს ნული ან ორი შვილი, სრული ორობითი ხე არის ბინარული ხე, რომელშიც ბინარული ხის ყველა დონე მთლიანად ივსება ბოლო დონის გარდა. ზოგიერთი სპეციალური მონაცემთა სტრუქტურა, როგორიცაა heaps, უნდა იყოს სრული ბინარული ხეები, ხოლო ისინი არ უნდა იყვნენ სრული ორობითი ხეები. სრულ ბინარულ ხეში, თუ იცით მთლიანი კვანძების რაოდენობა ან ლავების რაოდენობა ან შიდა კვანძების რაოდენობა, შეგიძლიათ იპოვოთ დანარჩენი ორი ძალიან მარტივად. მაგრამ სრულ ბინარულ ხეს არ გააჩნია სპეციალური თვისება, რომელიც ეხება ამ სამ ატრიბუტს.
