სტრუკტურული მონაცემები - (ხე AVL Tree)

                                                            

                                                                          AVL Tree

AVL Tree გახლავთ თვით ბალანსირებადი ხე, რომელიც ბინარული ხის ნაირსახეობაა,  სტრუკტურულ მონაცემებში ეს იყო პირველი ხე, რომელსაც ბალანსირების უნარი გააჩნდა, მისი შემქნელები არიან რუსი(ეთნიკურად ებრაელი) გიორგი ადელსონ ველსკი და უკრაინელი ევგენი ლანდის, დასახელებაც აქედან გამომდინარეობს, Adeson Velski Landis (AVL). მსგავსად Red Black Tree-სა არც ეს ხე არის იდეალურად ბალანსირებული, (Perfectly Balanced) თუმცა ერთი უპირატესობა რაც ამ კონკრეტულ ხეს გააჩნია RBT ხესთან მიმართებაში არის ის რომ ძიება ხდება გაცილებით სწრაფად და ამას თავისი მიზეზიც აქვს, როგორც მოგეხსენებათ, Red Black Tree-ში მნიშვნელოვანია წესების დაცვა და ხის შავი ბალანსის კონტროლი. (Black Height Of Tree) რაც არ იძლევა გარანტიას იმისა რო ხე რომელიმე ქვე ხე-ში ბალანსირებულია, შეიძლება მთლიანი ხე ბალანსირებულია, მაგრამ არ არის აუცილებლობა ყველა შვილობილი ხე იყოს ბალანსირებული.  AVL ხე-ში კი ეს ვალდებულებას წარმოადგენს, Root კვანძიდან ნებისმიერი ფოთოლ კვანძამდე ორივე ქვე ხე-ში Difference in Height არ უნდა აღემატებოდეს 1-ს, ისევე როგორც ნებისმიერი მშობელი კვანძიდან ფოთლამდე. გამომდინარე აქედან ძიება გაცილებით სწრაფად ხდება AVL ხე-ში.

როგორც ესეთი ამ ხის შექმნა არ არის ისევე რთული როგორიც Red Black Tree იყო, სულ რამოდენიმე საბაზისო წესი აქვს, რომლებიც უკვე ვიცით და მთლიანი ფილოსოფია, რაც მის ბალანსირებას ხელს უწყობს ეს გახლავთ როტაციის მეთოდები. როტაციას კი ვახდენთ მაშინ როცა ხეში დისბალანსია, ხის დისბალანსზე გადამოწმება როგორ ხდება ეგეც იცით, მასზე ბინარული ხის შექმნის დროს ვისაუბრეთ. გამოდის რომ ახალს არაფერს არ ვიტყვით, თუ ამას კითხულობთ RBT & BST წაკითული გაქვთ ჩემი ბლოგებიდან. წესები:

1.     ყველა ქვე ხე-ში კვანძებს შორის სიმაღლის სხვაობა არ უნდა აღემატებოდეს 1-ს.

2.     ყველა ქვე ხე არის AVL ხე.

მარტივად რო წარმოვიდგინოთ ვნახოთ რა სხვაობა არის RBT და AVL ხეებს შორის, ქვემოთ მოცემული სურათზე გვაქ ბალანსირებული RBT:

არც ერთ წითელ კვანძს არ ყავს წითელი შვილობილი კვანძი, ხის ორივე მხარეს ერთი და იგივე ოდენობის შავი კვანძებია, ხის შავი სიმაღლე დაცულია. ხე ბალანსირებულია. იგივე სიტუაციაში მსგავსი ხე რო გადავიტანოთ AVL ოპერაციებზე ხე იქნება დისბალანსით დ რატომ: როგორც მაღლა ვახსენე ამ ხის მთავარი მოთხოვნა არის რო ყველა მშობელი კვანძის სიმაღლე შვილობილ კვანძებს შორის არ უნდა აღემატებოდეს 1-ს. იგივე ფოტოზე დავთვალოთ რა სიმაღლე აქვს ხეს:

ციფრები კვანძის ორივე მხარეს გვეუბნება თუ რამდენი შვილობილი კვანძი ყავს ხეს. 0 და 0 არის ფოთოლი კვანძი, 75 – 90 -30 -60 , 1 და 1 გვეუბნება რო კვანძი არის მშობელი კვანძი რომელსაც ორივე მხარეს თითო შვილობილი კვანძი ყავს, შემდეგ მოდის 70 რომელსაც 2 კვანძი ყავს მარჯვნივ და 1 კვანძი ყავს მარცხნივ, ბოლო 50 რომელსაც 3 კვანძი ყავს მარჯვნივ და 1 კვანძი ყავს მარცხნივ, ანუ სხვაობა აღემატა 1-ს დარღვევა კი ხდება კვანძ ნომერ 50-ზე, RBT-ში ეს ნორმალურია, AVL ხე-ში კი აუცილებელი იქნება ხის გადაბალანსება. ზუსტად იგივე ლოგიკით ვამოწმებთ დარღვევას ნებისმიერ ქვე ხეში. სადაც მეთოდი შეწყვეტს თვლას და გვეტყვის თუ რომელი ხის მარჯვნივ ან მარცხნივ კვანძების ოდენობა აღემატება 1-ს სიმაღლეში. ნახეთ იგივე ხე ამჯერად AVL სტრუკტურაში:

როგორც ესეთი სიმაღლე არის საზღვრების ოდენობა და არა კვანძებს ოდენობა ხის ორივე ხმარეს, მაგრამ მე მიჩვეული ვარ კვანძების თვლას. ფოტო კვანძ ნომერ 35-ის წაშლამდე და ფოთო 35-ის წაშლის შემდგომ:

ხედავთ სხვაობას, AVL ხე ამ კონკრეტულ შემთხვევაში იდეალურად ბალანსირებულია, ძიებაც ზუსტად ამის გამო ხდება გაცილებით სწრაფად ვიდრე RBT-ში.  დაუშვათ ელემენტი ნომერი 90 თუ მოვიძიეთ ის 1 ნაბიჯშია AVL ხე-ში Root ელემენტიდან, როდესაც 4 ნაბიჯში შეგვხვდება RBT ხე-ში.

ელემენტის წაშლას და დამატებას რაც შეეება, ორივე თითქმის ერთნაირად უმკლავდება ამ ოპერაციას, არის მცირედი სხვაობა, იმდენად მცირე რო ამაზე ყურადღების გამახვილებაც კი არ ღირს.

მაშ ასე. ვნახოთ ელემენტის დამატებსი პროცესი:

დამატებისთვის დაგვჭირდება კვანძი, მას როგორც  მჩვევია ვაბუდებ კლასში, თქვენ თუ სურვილი გაქვთ ცალკე კლასი გააკეთეთ, რის შემდგომაც ვახდენთ ცვლადების დეფინირებას, ამ ჯერზეც სამი მიმთითებლით ვიმუშავებთ ცხოვრება რო გაგვიადვილდეს:

მთლიანი არსი ამ ხის როტაციებშია, რაშიც შემდეგი მეთოდები დაგვეხმარება:

Left Rotate:

Right Rotate:

Left-Right Rotate:

Right-Left Rotate:

4-მა მეთოდმა მათზე დაკისრებულ მოვალეობას რო გაართვან თავი საჭიროა ვიცოდეთ ხის რომელ მონაკვეთზე გვაქ დისბალანსი, ამაში მეთოდი დაგვეხმარება რომელიც ხის სიმაღლეს შეგვიმოწმებს.

მეთოდი გადაწოდებული ელემენტის ორივე მხარეს დათვლის კვანძების ოდენობას და დაგვიბრუნებს სხვაობას. სხვაობის დაბრუნების შემდგომ, თუ ხვაობა მეტია ერთზე ან ნაკლებია მინუს ერთზე: (Math.abs() მეთოდს თუ გამოიყენებთ, შეგიძლიათ <-1 ველი წაშალოთ)

მაშინ უნდა მოვახდინოთ რებალანსირება ხის იმ კონკრეტულ კვანძზე, სადაც გვაქ დისბალანსი. როგორც ხედავთ მეთოდი რეკურსიულად იძახებს საკუთარ თავს და იმუშავებს მანამ სანამ Root კვანძამდე არ მივა.  ბალანსირებას შემდეგი მეთოდი უმკლავდება:

აქაც არ გვაქ არაფერი ახალი, თუ მარცხენა ხის მარცხენა კვანძი მეტია მარცხენა ხის მარჯვენა კვანძზე ესეიგი დისბალანსი მარცხენა ხეშია და ვახდენთ მარჯვნივ როტაციას, წინააღმდეგ შემთხვევაში დარღვევა მარცხენა ხის მარჯვენა კვანძზშია და მარცხენა-მარჯვენა როტაცია აღმოფხრის პრობლემას, იგივე ლოგიკით მიუდგებით მარჯვენა ხესაც. 

ამის შემდგომ წერთ სტანდარტულ დამატების მეთოდს და სურათზე checkBalance მეთოდს გადააწოდებთ ბოლო დამატებულ ელემენტს.

სულ ეს გახლავთ დამატების ფილოსოფია, როგორც ხედავთ არც ისეთი საშიში და რთულად წარმოსადგენია,  როგორც RBT, ბევრ ყველაზე პრიმიტიულ სტრუკტურულ მონაცემზე მარტივად იწერება. (ყველაფერი გენიალური მარტივიაო, ამ ხეზეა ნათქვამი)

მოკლედ გავეცანით დამატების მეთოდს, ძიების მეთოდს არ გავეცნობით, გადადით რომელიმე ხის კლასზე, რომელიც GitHub-ზე მაქ ატვირთული და დააკოპირეთ. წაშლის მეთოდს კი განვიხილავთ.

ყველაზე კარგი რაც წაშლის მეთოდში გვაქ ეს არის ის, რომ ელემენტის წასაშლელად არ გვჭირდება ცალკე დამხარე მეთოდები, როგორც ეს წინა-მორბედ ხეებ-ში იყო საჭირო, (პრინციპში მე არ მჭირდება თორე ცალკე თუ დაწერთ ეს თქვენ გემოვნებაზეა დამოკიდებული, ან ვინმეს გემოვნებაზე თუ სადმე წააწყდით ამ ოპერაციას განცალკევებით) ვშლით ჩვეულებრივად, როგორც ბინარულ ხეში და ბალანსირებას ვახდენთ იგივე მეთოდით, რომელიც ახდენს ხის ბალანსირებას ელემენტის დამატების დროს. ნახეთ მაგალითი:

პირველი ვპოულობთ ელემენტს, შემდგომ ვამოწმებთ არის თუ არა ეს ელემენტი მშობელი, თუ მშობელია მაშინ უნახავთ იდეალურ შემცვლელს მარჯვენა ან მარცხენა ხეში, რის შემდგომაც ვშლით ელემენტს (შემცვლელს ან უბრალოდ ელემენტს), რომელსაც მაქსიმუმ 1 შვილობილი კვანძი ყავს.

წაშლის შემდგომ ბალანსირებაზე ვამოწმებთ წაშლილი ელემენტის მშობელ ელემენტს. თუ დისბალანსია ხეში, დამხმარე მეთოდები მოახდენენ მის ბალანს. სულ ეს არის.

იმედია საინტერესო იყო. ამით AVL ხე-ზე საუბარს მოვრჩით. მთლიან კოდს მიაგნებთ შემდეგ ბმულზე