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

სტრუკტურულ მოცამებში უამრავი საჭირო სტრუკტურა არსებობს, სხვა და სხვა დანიშნულებებით და ოპერაციების წარმოების სისწრაფით, მაგალითად მასივი არის სტატიკური სტრუკტურული მონაცემი, რომელიც კომფორტულია ელემენტებზე წვდომის კუთხით, რადგან ოპერაციებს ასრულებს კონსტანტურ დროში, მისი შექმნაც მარტივია, ინსტანცირებაც და გამოყენებაც. მასივზე ბაზირებული სტრუკტურული მონაცემები, ისეთები როგორიც მასიური სია, ვეკტორი და სხვა არიან აგრეთვე საკმაოდ სწრაფები ზუსტად იმ ფუნქციონალიზმის გამო რომელიც სტატიკურ მასივს გააჩნია, მეორე ყველაზე გავრცელებული სტრუკტურა არის დაკავშირებული სია, რომელიც დინამიურია და იყენებს კვანძებს, დაკავშირებული სიას თავისი პრიორიტეტები გააჩნია ის იდეალურად ართმევს თავს ისეთ ოპერაციებს როგორიც არის ელემენტის დამატება, განახლება, წაშლა. გვაქ ისეთი სტრუკტურები რომლებიც სპეციფიური ოპერაციების შესასრულებლად გამოიყენება, (Stack, Queue) მატი დახმარებით საკმაოდ რთულ ამოცანებს ვართმევთ პროგრამირების დროს თავს, გვაქ HashTable (მასზე არ გვისაუბრია ჯერ მაგრამ დეტალურად განვიხილავთ) რომელიც იდეალურად ართმევს თავს ძიების პროცეს. ანუ კონსტანტურ დროში ასრულებს ძიებას, რომლის უნარი არც ერთ ზემოთ ხსენებულ სტრუკტურას არ გააჩნია, ანუ მისი ძიების ალგორითმია O(1).

როგორც ხედავთ ყველას თავისი დადებითი მხარე აქვს, მათი უარყოფითი მხარეები არის ის რომ ძიებას ჭირდება სტანდარტულად ერთნაირი დრო თითქმის ყველა სტრუკტურაში(რამოდენიმეს გამოკლებით) და მათი ძიების ალგორითმია O(n) . სია და რიგი არიან წრფივი კოლექციები, შესაბამისად იტერაციაც წრფივი თანმიმდევრობით ხდება, მილიონი ელემენტის წაკითხვას მილიონი ოპერაცია დაჭირდება(ყველაზე კარგ შემთხვევაში 1 ოპერაცია თუ ელემენტი სტრუკტურის დასაწყისში იმყოფება და ყველაზე ცუდ შემთხვევაში მილიონი თუ ის ბოლოში იმყოფება) თუ გავითვალისწინებთ იმასაც, რომ დღევანდელი ხელსაწყოები საკმაოდ განვითარებული და სწრაფია მსგავსი სცენარი მაინც მიუღებელია. მიუღებელი მსუბუქად ნათქვამია, მსგავსი სცენარი კატეგორიულად მიუღებელია დღევანდელ ტექნოლოგიურ სამყაროში. რადგან დრო = ფულს, სისწრაფე არის შემოსავლის წყარო.

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

რა არის ხე?

ხე არის კვანძების(nodes) ერთობა რომელიც ვიზუალურად გავს ჩვეულებრივ ხეს. აქედან მოდის მისი დასახელებაც: ის არის იერარქიული სტრუკტურული მონაცემი რომელიც მუშაობს რეკურსიულად,  ხეში ნებისმიერ ინდივიდუალურ კვანძს რომელიც იფორმაციას ინახავს ქვია node, კვანძი ინახავს რეალურ იმფორმაციას და შემდეგი კვანძის მიმთითებელს. ხეში თუ ჩვენ გვაქ N რაოდენობის ელემენტი, მაშინ კავშირი ელემენტებს შორის უდრის N-1-ს.

ელემენტების ოდენობას და მათ კავშირს შემდეგი ფოტო მოფენს ნათელს.

ფოტოზე ხედავთ ხეს 11 კვანძით, მათ შორის კავშირის ოდენობა უდრის 10-ს. გამომდინარე აქედან N კვანძების ოდენობას გააჩნია N-1 კავშირების ოდენობა. ნებისმიერ სიტუაცია ეს ფორმულა არ შეიჩვლება.

                                                            ტერმინოლოგია

Root - ხეში ელემენტს რომელიც მოქცეულია ხის სათავეში ეძახიან Root ელემენტს. არ არსებობს ხე რომელსაც არ გააჩნია Root ელემენტი,  აგრეთვე ვერ შეხვდებით ხეს რომელსაც ერთ-ზე მეტი Root ელემენტი გააჩნია. (არსებობს ხის სხვა სახეობები სადაც რამოდენიმე Root ელემენტი გვხვდება, მაგრამ მათზე ჩვენ აღარ ვისაუბრებთ, მათ ხისებრ სტრუკტურებს ეძახიან Tree Like Structure)  ნახეთ ფოტო:

ფოტოზე A კვანძი არის Root ელემენტი.

Edge - ხეში კავშირს კვანძებს შორის ეძახიან Edge-ს. როგორც მაღლა ვახსენე ხეში Edge-ის რაოდენობა უდრის ელემენტების რაოდენობას მინუს ერთს. (N nodes N-1 Edge)

Parent-(მშობელი) არის კვანძი, რომელსაც გააჩნია შვილობილი კვანძი და არის ქვე-მდგომი კვანძი ზე-მდგომი კვანძის. ხეში ზემდგომი კვანძი არ გააჩნია Root კვანძს, ის არის მშობელი ყველა არსებული კვანძის.

ფოტოზე E,G,B,C,A არიან მშობლები, მათ გააჩნია ზემდგომი კვანძები და ყავთ ქვემდგომი კვანძები, ყვითელ წრეში მოქცეულ კვანძებს, როგორც ხედავთ არ ყავთ ქვე-მდგომი კვანძები.

Child-შვილობილი, მემკვიდრე კვანძი. ხეში კვანძი რომელსაც გააჩნია კავშირი, მშობელ კვანძთან ნაცნობია, როგორც შვილობილი კვანძი. Root კვანძის გამოკლებით, მას არ ყავს მშობელი.

მაგალითად. ფოტოზე B და C არიან შვილობილი კვანძები A-ის, G და H არიან შვილობილი კვანძები C კვანძის,  K კვანძი არის შვილობილი G კვანძის.

Siblings-ნათესავები. კვანძები, რომელსაც გააჩნიათ ერთი მშობელი არიან ნათესავები. Root კვანძის გამოკლებით. მას არ ყავს ნათესავები.

ფოტოზე: I &J, D & E & F, G & H, B & C  არიან ნათესავები.

Leaf-(ფოთოლი). კვანძი რომელსაც არ გააჩნია შვილობილი კვანძი ხეში ნაცნობია, როგორც ფოთოლი, სხვანირად მას Terminal Node  ან External Node-ს ეძახიან.

ფოტოზე I, J, K, D, F, H არიან ფოთლები.

Internal - შიდა კვანძი. კვანძი, რომელსაც ერთი შვილობილი კვანძი მაინც გააჩნია, ხეში ნაცნობია როგორც Internal node. თუ დავფიქრდებით ხეში ყველა კვანძი Internal კვანძია გარდა External კვანძებისა.

A, B, C, E, G არიან Internal კვანძები.

Degree-ხეში შვილობილი კვანძების მაქსიმუმ ოდენობას ეძახიან Degree-ს. ყველაზე დიდ ოდენობას ყველა სხვა ოდენობასთან შედარებით ეძახიან “Degree of Tree”.

ფოტოზე: Degree Of E = 2, Degree of B = 3, Degree Of A = 2, Degree of H = 0;

Level-ხეს გააჩნია საფეხურები, ყველა ახალი კვანძის დასაწყისი როგორც წესი ახალ საფეხურად ითვლება, Root ელემენტი იმყოფება 0 საფეხურზე, მისი შვილობილი ელემენტი იმყოფება პირველ საფეხურზე, შვილობილის შვილობილი იმყოფება მეორე საფეხურზე და ა.შ

Height- სიმაღლე. ხეში საზღვრების ჯამურ ოდენობას ფოთლიდან სასურველ ელემენტამდე ეძახიან სიმაღლეს. დაუშვათ თუ ვზომავთ ფოთლიდან Root ელემენტამდე სიმაღლეს, მაშინ ამ სიმაღლეს ხის სიმაღლე ქვია. “Height Of Tree”

Depth-ზუსტად იგივე საზომი ერთეულია როგორიც Height, ამ ჯერზე სიმაღლე იზომება Root ელემენტიდან ნებისმიერ ელემენტამდე ან ფოთლამდე.  გზას Root ელემენტიდან ყველაზე შორს მდგარ ფოთლამდე ეძახიან Depth Of the Tree

ფოტოზე A-ან D-დე გვაქ Depth რომელიც უდრის 2-ს. A-ან K-დე გვაქ  Depth Of The Tree. იმიტომ რო K ყველაზე შორს მდგარი ელემენტია. (ხშირად პროგრამისტებს ერევათ ორი ტერმინოლოგია. ბევრი Depth-ს Heigth-ს ეძახის და პირიქით, ზოგიც ორივეს Heigth-ს ეძახის, ამიტომ თუ მოხვდით სიტუაციაში სადაც ამ ტერმინოლოგიით საუბრობენ (თემა იქნება, წიგნი თუ უბრალოდ არგუმენტირებული დავა, კარგად დააკვირდით ხოლმე რას გულისხმობენ, მათ შორის გამსაუბრებელსაც დააკონკრეტებინეთ რას გულისხმობს თუ გკითხათ ხის height ან depth რას ნიშნავსო)

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

ფოტოზე A,B,E,J არის გზა. C,G,K აგრეთვე არის გზა. გზას როგორც წესი გააჩნია სიდიდე, A,C,E,J-ის სიდიდე უდრის 4-ს.

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

ფოტოზე გვაქ სამი ქვე ხე, ჯამში 4 ხე. თუ Root ელემენტსაც ჩავთვლით.

Visiting- ეს არის პროცესი ხეში როდესაც ყველა კვანძის წაკითხვა ხდება. მარტივი ენით იტერაცია.

Traversing - არის პროცესი როდესაც გარკვეული ალგორითმით და თანმიმდევრობით ვკითხულობთ ელემენტებს. (დეტალურად მაგალითებზე ნახავთ, არსებობს რამოდენიმე გავრცელებული კითხვის სტილი)

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

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

ხის ყველაზე გავრცელებული ფორმებია: Binary Tree(BT), Binary Search Tree(BST), Red-Black Tree(RBT), AVL Tree, AA Tree, B Tree, Heap, ამ 7 ტიპის საფუძვლიანად ცოდნის შემდგომ თავისუფლად შეგიძლიათ თქვათ რომ ხის სტრუკტურას ფლობთ, ჩამოთვლილთაგან ყველაზე გავრცელებული ხის ტიპია Binary Tree(BT), Binary Search Tree(BST). ჩვენ საუბარს სწორედ მათი განხილვით დავიწყებთ.

ნაკლება ნაცნობი ხეებია: Huffman Tree, Suffix Tree, Trie Structure Tree, N-Array Tree,  Splay-Tree და ა.შ ზოგად ხის გაცილებით მეტი ვარიანტი არსებობს, ისინი განხილვის ან გამოყენების საგანი იმიტომ არ ხდებიან, რომ ვერაფრეს თავაზობენ მომხმარებლებს(პროგრამისტებს) ისეთს რასაც ყველაზე გავრცელებული ტიპები ვერ ართმევენ თავს ან უბრალოდ დამწყები პროგრამისტებისთვის გამოუსადეგარია) R-Tree, B+-Tree, Range Tree, Markel Tree, Fenwick Tree, K-D tree, Counted Tree, ჩამონათვალი საკმაოდ დიდია.  

                                                            Binary Tree

ბინარული ხე არის რეკურსიული სტრუკტურული მონაცემი სადაც გვაქ Root ელემენტი და 2 შვილობილი ელემენტი, რომლებსაც LeftChild &  RightChild სახელით მოიხსენიებენ ხოლმე პროგრამირებაში. ყველა შვილობილ კვანძს გააჩნია 2 შვილობილი კვანძის ქონის უფლება მაქსიმუმ. ანუ ამ სტრატეგიით ხდება ფორმირება ქვე ხეების. როგორც ესეტი ბინარულ ხეს შეიძლება საერთოდ არ ყავდეს შვილობილი კვანძი, ყავდეს 1 შვილობილი კვანძი და მაქისმუმ 2 კვანძი ნებისმიერ საფეხურზე, რომლებიც ერთმანეთან დაკავშირებულები არიან საზღვრებით. რეკურსიული იმიტომ არის ბინარული ხე, რომ ნებისმიერი დამატებული კვანძი არის შვილობილი კვანძი რომელიმე კვანძის და მშობელი კვანძი ქვე მდგომი კვანძების, გააჩნია ახალი ხის ფორმირების საშუალება და ყველა სხვა ფუნქცია რაც მის ზემდგომ ამ ქვემდგომ კვანძებს გააჩნია, აქედან თუ ლოგიკურად შევხედავთ ის რეკურსიულია, რადგან თავის თავში ნებისმიერი კვანძი არის მშობელი, შვილობილი დ ნათესავი კვანძი. რეკურსიიც არსიც ამაშია, ოპერაცია რომელიც ახდენს საკუთარი თავის გამოძახებას(განმეორებას) არის რეკურსიული. ხის კვანძს  თუ საკუთარ თავში აქვს შესაძლებლობა იყოს რამოდენიმე დასახელების მატარებელი ის რეკურსიულია. (თითქმის ყველა ხე რეკურსიულია, უმეტესობა მეთოდების ხეში რეკურსიულად იწერება ამიტომ კარგი იქნება თუ გაიხსენებთ რა არის რეკურსია)

ბინარული ხე არ იცავს თანმიმდევრობას, ანუ მასში ელემენტები ხვდება Random თანმიმდევრობით, თუ წარმოვიდგენთ შემდეგ ციფრებს 2,3,5,6,12,4,67 ისინი ბინარულ ხეში აღმოჩდებიან იმ თანმიმდევრობით რა თანმიმდევრობითაც მოხდა მათი ხეში შეყვანა. 2 მოექცევა ხის სათავეში დანარჩენი ელემენტები კი განაწილდებიან მარჯვნივ და მარცხნივ, ეს გარკვეულწილად ქმნის საფრთხეს იმისა რო ხემ განიცადოს დეგენერაცია რაც ნიშნავს იმას რომ ხის შექმნით დავიწყებთ და დავასრულებთ დაკავშირებული სიით. ელემენტები არ განაწილდება მარჯვნივ და მარჯვნივ, ნახეთ მაგალითი:

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

ამ კონკრეტულ ხეში ელემენტების კონტროლზე წარმოდგენა რომ შეგექმნათ გავაკეთებთ მაქსიმალურად მარტივ მაგალითს. დეტალურად და დაწვრილებით დარჩენილი ფუნქციონალიზმების ერთობას Binary Search Tree-ს განხილვის დროს ვნახავთ. მაშ ასე „სულელი“ ხის მაგალითი:

ხის შექმნა დავიწყეთ იქიდან რომ შევქმენით კვანძებითვის ჩაბუდებული კლასი. (მსგავსად დაკავშირებული სიისა) სადაც გვაქ ორი მიმთითებელი:

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

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

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

ამის შემდგომ Root კვანძის ადგილას იკავებს პირველი შეყვანილი ელემენტი და ვახდენთ ტრევერსირებას inOrder თანმიმდევრობით:

ტრევერსირების რამოდენიმე ტიპი არსებობს და ყველას განვიხილავთ სათითაოდ:

კომპილირების შემდგომ:

                              

                                                           Binary Search Tree

Binary Search Tree და Binary Tree შორის ძირითად განსხვავებას ალბათ დასახელებიდანაც ხვდებით, Binary Search Tree-ს გააჩნია უნარი ელემენტის ძიების, ალბათ კითხვაც იბადება ესეთ სიტუაციაში, რათ გვინდა ხე (მაგ:Binary Tree) რომელსაც ძიების უნარი არ გააჩნია? არის სიტუაციები როდესაც საჭიროა მსგავსი ხის ქონა, მაგალითად Binary Heap-ს არ გააჩნია ძიების უნარი, მას კი პრიორიტეტული რიგი იყენებს, რომელიც ელემენტების გამოძახებას აღმავლობის ან დაღმავლობის პრინციპით ახდენს, ანუ მისთვის მნიშვნელოვანი მხოლოდ ერთი ელემენტია ერთ კონკრეტულ ოპერაციაში. ამიტომაც არ არის აუცილებლობა ძიების.

მსგავსად ბინარული ხისა Binary Search Tree-ც შედგება სათაო კვაძის და 2 შვილობილი კვანძისგან, რომლებიც განლაგებულნი არიან სათაო კვანძის მარჯვნივ და მარცხნივ. ელემენტების განლაგებას ამ კონკრეტულ ხეში უკვე თანმიმდევრობა აქვს:

1.    ყველა ელემენტი რომელიც ნაკლებია მშობელ ელემენტზე უნდა მოთავსდეს მშობლის მარცხნივ.

2.  ყველა ელემენტი რომელიც მეტია მშობელ ელემენტზე უნდა მოთავსედეს მშობლის მარჯვნივ.

3.     Binary Search Tree-ს გააჩნია ელემენტის ძიების უნარი. 

ეს სამი სხვაობა არის ბინარულ ხეს და ძიების უნარიან ბინარულ ხეს შორის.

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

ვიზუალური წარმოდგენისთვის ნახეთ Binary Search Tree-ს ფოტო:

ყველა ელემენტი, რომელიც მეტია მშობელ ელემენტზე განლაგებულია მარჯვნინვ, რომელიც ნაკლებია მარცხნივ.

ეს მას უპირატესობას ანიჭებს ძიების პროცესში, არ უწევს მთლიანი სიის გადაკითხვა როგორც ეს დაკავშირებულ სიაში ხდება, შესაბამისად მისი ძიება O(log n) ალგორითმის მატარებელია. რაც გაცილებით სწრაფია დაკავშირებული სიის ძიებას თუ შევადარებთ და უფრო ნელია თუ მასივს შევადარებთ ან მასზე ბაზირებულ სტრუკტურებს.

ელემენტის დამატების ან წაშლის პროცესიც აგრეთვე არიან O(log n) ალგორითმის მატარებელი რაც მას უპირატესობას ანიჭებს მასივთან და მასზე ბაზირებულ სტრუკტურებთან მიმართებაში, იგივე ოპერაციების წარმოების დროს, თუმცა უფრო ნელია ვიდრე დაკავშირებული სია. (როგორც გახსოვთ დაკავშირებულ სიაში ელემენტის დამატება კონსტანტურ დროში ხდება, მასივზე ბაზირებულ სტრუკტურაშიც კონსტანტურ დროში, მაგრამ ელემენტები განსხაზღვრულ სიდიდეს როცა ავსებენ მასივის გადაწერა და გაზრდა ხდება რაც O(n) ალგორითმის მატარებელია.

მსგავსად დაკავშირებული სიისა ამ კონკრეტულ ხესაც არ გააჩნია საზღვრები, მასში ელემენტები შედის მანამ სანამ მეხსიეებაში ადგილი გაგვაჩნია.

ძირითადი პრიორიტეტები ხის:

1.    ის არის იერარქიული სტრკტურა

2.    ადვილია  დალაგებული ხით მანიპულირება

3.    ინფორმაციის ძიება ხდება სწრაფად.

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

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

6. ყველა ობიეკტი რომელსაც გადავაწოდებთ ხეს უნდა იყოს Comparable ინტერფეისის ტიპის. (ესეც არჩევითია, მაგალითად Binary Heap-ს თუ ვქმნით არჩევანი ნაკლებად გაგვაჩნია, აუცილებელია ობიეკტი იყოს Comparable ტიპის)

ბინარულ ხის კვანძი შემდეგი იმფორმაციის მატარებელია:

·        Root Element

·        Node Left

·        Node Right

არსებობს რამოდენიმე სახეობა Binary Search Tree-ის , ესენია შევსებული ბინარული ხე (FBN Full Binary Tree), სრული ბინარული ხე(CBN Complete Binary Tree), სრულყოფილი ბინარული ხე(PBN Perfect Binary Tree), ბალანსირებული ბინარული ხე(BBT Balanced Binary Tree), დეგრადირებული ბინარული ხე(DBT Degenerate Binary Tree). როგორც წესი ბოლო სახეობად ნაკლებად შეიძლება ჩაითვალოს. მას შეიძლება ეწოდოს ხე, რომელსაც პროგრამირების დროს უნდა გავექცეთ, ანუ ჩვენმა ხემ არასდროს არ უნდა განიცადოს დეგენერაცია.

Full Binary Tree არის ბინარუ ხე, რომლის ყველა კვანძს გააჩნია 2 ან 0 შვილობილი კვანძი. ნახეთ ფოტო:

როგორც ხედავთ მაქსიმუმ 2 შვილობილი კვანძი ყავს კვანძს ან საერთოდ არ ყავს. გასაუბრებაზე თუ მოხვდით ამ კონკრეტული ხის ტიპთან დაკავშირებით შემდეგი შეკითხვა შეიძლება შეგხვდეთ, რამდენი ფოთოლია მოცემულ ხეში? ვიზუალურად ამის დადგენა ძალიან მარტივია, ჩანს რამდენი ფოთოლია მაგრამ კოდის დონეზე ამ მეთოდის დაწერა მოგიწევთ, ფორმულა ფოთლების ოდენობის დადგენის შემდეგია:  Leaf = Internal Node + 1; Internal Node არის კვანძი, რომელსაც ერთი შვილობილი კვანძი მაინც ყავს, მაღლა ფოტოზე 4 Internal Node გვაქ, ანუ ფოთლების ოდენობა უდრის 5-ს. (თუ ხე არც ერთ კატეგორიაში არ ხვდება მაშინ ეს ფორმულა გამოუსადეგარია, დათვლა მოგიწევთ სათითაოდ და ამის მაგალითს ნახავთ კოდის დონეზე)

Perfetc Binary Tree - არის ხე, რომელშიც ყველა Internal კვანძს ყავს ორი შვილობილი კვანძი და ყველა ფოთილი იმყოფება ერთ Level-ზე

Complete Binary Tree - არის ხე სადაც ყველა Level ხის შევსებულია, თუ აღმოჩდა რომ ხე არ არის ბოლომდე შევსებული მაშინ ყველა ფოთოლი განლაგებულია უკიდურესაც მარცხნივ მშობელი კვანძისგან. ანუ ეს ხე წააგავს Perfetc Binary Tree-ს თუმცა ბოლომდე შევსების აუცილებლობა არ გააჩნია. მთავარია ბოლო ფოთოლი კვანძი იყოს მშობელი კვანძისგან მარცხნივ განლაგებული.

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

Balanced Binary Tree- არის ხე სადაც Root ან კონკრეტული მშობელი კვანძიდან ფოთლამდე მანძილი ყველა ქვე -ხეში(sub-tree) ერთმანეთს უდრის ან მაქსიმუმ 1 საზღვრით განსხვავდებიან. რთულად წარმოსადგენია ალბათ, ნახეთ ფოტო:

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

შედეგად მივიღებთ დისბალანს ქვე-ხეებს შორის, რადგან ერთ ქვე ხეში Depth უდრის 3-ს და მეორეში 5-ს. სხვაობა უდრის 2-ს, კონვენციის მიხედვით სხვაობა ვერ იქნება ერთზე მეტი. გასაუბრებაზე ამ ხის ტიპთან დაკავშირებით შეხვდებით დიდი ოდენობის კითხვებს, 1. გაიგე ხე ბალანსირებულია თუ არა? 2. ხე არის დისბალანსით, მოახდინე მისი ბალანსირება. 3. რომელი ხეებია ბალანსირებული? და ა.შ ამ ყველაფრის მაგალითებს ვნახავთ. გავრცელებული ხეებიდან ბალანსირებული ხეებია AVL Tree და  Red-Black Tree.  რჩევა: გამსაუბრებელს ყოველთვის დააკონკრეტებინეთ ბალანსირებაში რას გულისხმობს. დეტალურად მოაყოლეთ თუ რას სურვს თქვენგან.

ზოგადად ბალანსირებას იმიტო ეთმობა დიდი ყურადღება რომ უბალანსო ხეში შეიძლება შემდეგ პრობლემებს წააწყდეთ, მაგალითად წარმოიდგინეთ გაქვთ ხე სადაც მარცხენა ქვე-ხეში 1 მილიონი იმფორმაციაა და მარჯვენა ქვე ხეში 5. თუ ხის საძიებო სისტემა იყენებს, სიტყვა „ალავერდს“ მოგიძებნით 0.0001 მილი წამში და სიტყვა „ზიმბაბვეს“ მოგიძებნით 0.0040 მილი წამში, მილიონობით იმფორაციის დროს იტერაცია იმდენად სწრაფად ხდება რომ სხვაობას ვერ იგრძნობთ, მაგრამ თუ google-ის მსგავსი საიტი გაქვთ, ან საიტი სადაც მილიარდობით ჩანაწერის ძიება არის შესაძლებელი, მაშინ სხვაობა საკმაოდ საგრძნობი იქნება, რადგან ერთ შემთვევაში 8-9 ოპერაცია შესრულდება სასურველი შედეგის მისაღწევად და მეორე შემთხვევაში 40-50.

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

Degenerate Tree-დეგრადირებული ხე(ხე რომელიც ერთი თანმიმდვრობით ივსება და ემგვანება დაკავშირებულ სიას) უკვე ვახსენე მაღლა, მაგრამ როგორ არ უნდა განიცადოს ხემ დეგრადაცია არ მითქვია. ხის შექმნის დროს ჩვენი ამოცანა არის რომ ხემ ნებისმიერი სიდიდის მონაცემზე ერთი აგლორითმით განახორციელოს ოპეერაციის წარმოება, ანუ მისი ალგორითმი უნდა იყოს O(log n).

O(log n). ალგორითმის მატარებელი რომ იყოს ხე :

1.    მისი Heigth/ Depth უნდა იყვნენ ამ ალგორითმის მატარებლები.(ანუ ეს ორი ტერმინოლოგია უნდა იყვნენ ბინარული ლოგარითმის მატარებლები, თუ არ იცით რა არის ბინარული ლოგარითმი, მოიძიეთ მასალა)

2.  ამ ალგორითმის მატარებლები თუ უნდა იყვნენ Heigth/ Depth, მაშინ ხეში ელემენტები არ უნდა მოხვდნენ აღმავლობის ან დაღმავლობის პრინციპით.

3.   თუ ელემენტი მაინც შეაღწევენ ხეში აღმავლობის ან დაღმავლობის პინციპით ის განიცდის დეგენერაციას.

4.   ხემ შეიძლება დეგენერაცია განიცადოს გაუთვალისწინებელ სიტუაციებშიც: მაგალითისთვის წარმოიდგინეთ შემდეგი ციფრები, 60, 15, 25, 30, 20. ვიცით რომ 60 არის Root ელემენტი, 15 განთავსდება ხელ-მარცხნივ, 25 განთავსდება 15-ს ხელ0მარჯვნივ, 30 განთავსდება 25-ის ხელ-მარჯვნივ და 20 განთავსდება 30-ის ხელ-მარცხნივ რაც შედეგად მოგვცემს დეგრადირებულ ხეს, რომელიც უფრო დაკავშირებული სია იქნება ვიდრე ხე. მსგავსი სიტუაციების თავიდან არიდების გზები არსებობს და ამას მაგალითებზე ნახვთ: უკეთ წარმოდგენისთვის მოცემული ციფრების ხე ნახეთ:

როგორც ხედავთ მეთოდი რომელიც დაამატებს ელემენეტს ხეს გამართულა უნდა მუშაობდეს და ყველა მოსალოდნელი საფრთხე გათვალისწინებული უნდა ქონდეს, წინააღმდეგ შემთხვევაში არც ერთი სხვა მეთოდი არ იმუშავებს ზუსტად იმ შეცდომით რა შეცდომაც დაუშვა დამატების მეთოდმა. არ მუშაობაში იგულისხმება Worst Case Scenario როცა მოსალოდნელი O(log n) ალგორითმიდან მოულოდნელ O(n) ალგორითმს მივიღებთ შედეგად.

დავიწყოთ ხის შექმნა კოდის დონეზე:

პირველი დაგვჭირდება კლასი ან ჩაბუდებული კლასი, რომელსაც კვანძად გამოვიყენებთ. მას ესაჭიროება 2 მიმთითებელი, 2 ფორმალური ტიპი, რომლის პირველი ფორმალური ტიპი ამ კონკრეტულ მაგალითზე იქნება Comparable ტიპის. ერთი კონსტრუკტორი გვექნება რომელსაც ღირებულებებს გადავაწოდებთ + getter’s & setter’s რის შემდგომაც კვანძი მზად არის გამოყენებისთვის. ნახეთ ფოტო:

ამის შემდგომ ძირითადი კლასზე ფორმალური პარამეტრების გადაწოდებას ვახდენთ და Root კვნძის დეფინირებას.

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

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

შემდგომ if გამოხატულებაში ვამოწმებთ Root ელემენტი არის თუ არა ცარიელი, თუ ცარიელია მაშინ მას შევავსებთ. თუ არა და გადავალთ else ბლოკში სადაც გვაქ infinite loop, არც ეს არის კარგი პრაკტიკა, მაგრამ მაგალითად გამოდგება, უკეთესი ვარიანტი იქნება თუ რეკურსიულად დავამატებთ ელემენტებს ხეს, ანუ else ველზე მოვახდენთ დამატების მეთოდის გამოძახებას, რომელიც დაამატებს ელემენტს მარჯვნივ ან მარცხნივ, მაგრამ ისევ და ისევ ასე უფრო წაკითხვადია დამწყებთათვის. infinite loop-ში მნიშვნელოვანი if გამოხატულება გახლავთ ის, რომელიც ამოწმებს დუბლირებულ ელემენტებზე ხეს. თუ მსგავსი ელემენტი არსებობს მაშინ მეთოდი უბრალოდ შეწყვეტს მუშაობას და გავა stack მეხსირებიდან, ყველანაირი დანამატების, გამონაკლისების და ღირებულებების გარეშე. გასლვას მეხსიერებიდან current ცვლადის ნულზე გადამოწმება უწყობს ხელს, ანუ ძიება გრძელდება მანამ სანამ current არ მიუახლოვდება საჭირო სიცარიელეს, მაგრამ ის თუ დუბლირებული ელემენტის მატარებელია შეწყვეტს მუშაობას if გამოხატულების ველზე სადაც მოწმდება დუბლირებაზე ელემენტი. არც ისე რთულია მეთოდი დამეთანხმებით, ნუ თუ რთულად გეჩვენებათ წინ ელემენტის წაშლის მეთოდი გელოდებათ, რომელიც დიდ მოტივაციის შედეგად იწერება.

შემდეგი მეთოდი გახლავთ ძიება:

მასში განსაკუთრებული არაფერია, ძიება გრძელდება მანამ სანამ სასურველი შედეგი არ დადგება, ძიებას აქვს ორი მიმართულება, თუ ელემენტი ნაკლებია root-ზე მაშინ მარცხნივ თუ მეტია მარჯვნივ, ქვე ხეებშიც იგივე ლოგიკით გრძელდება ძიება, თუ ნაკლებია მშობელ კვანძზე მარცხნივ თუ არა და მარჯვნივ, პლიუსი ამ მეთოდის არის ის რომ რამოდენიმე ნაბიჯში ახდენს სასურველი ელემენტის მოძებნას, თუ სწორად მახსოვს 4 მილიონ ელემენტში 32 ოპერაცია ჭირდება სასურველი შედეგის მისაღწევად.  ძიების ალგორითმია O(Log n) სადაც Log შეიძლება ნებისმიერი Base იყოს. მაგალითად(2,10 და ა.შ)

მაშ ასე, გვაქ ორი მეთოდი, ერთი  ამატებს ელემენტს ხეს და მეორე ეძებს ელემენეტს ხეში. დროა ვნახოთ თუ როგორ ხდება ელემენტების წაკითხვა ხეში. არსებობს ორი სახის ტრევერსირება ელემენტების და ესენია: BFS & DFS. მათ გააჩნიათ ოპერაციების სახეობა ან სახეობები. როგორც მიხვდით უბრალოდ toString მეთოდის გენერირებას და ელემენტების წაკითხვას ვერ მოვახერხებთ, როგორც ეს სხვა სტრუკტურებში ხდება. ელემენტების წაკითხვასაც კი ალგორითმი და ოპერაციების ერთობა გააჩნია ხეში.

BFS– Breadth first traversal.  მას ერთი ტიპის ოპერაცი გააჩნია და ეს არის Level Order Traversal.  ანუ ელემენტების წაკითხვა უნდა მოხდეს ხის საფეხურების მიხედვით. ნახეთ შემდეგი ფოტო უკეთ წარმოდგენისთვის.

Level Order წაკითხვის დროს პირველი ეკრაზე გამოვა root ელემენტი, მეორე მისი მარცხენა შვილობილი და შემდგომ მარჯვენა შვილობილი, ყველა საფეხურის წაკითხვა მოხდბა იგივე ლოგიკით. სურათზე არსებული ელემენტები კონზოლში. 20 , 25 , 50 , 22 , 30 , 60 ამ თანმიმდვრობით მოხვდებიან. ამ ტრევერსიების დროს გამოიყენება Queue სტრუკტურული მონაცემი, როგორც წესი, მაგრამ მის გარეშეც შესაძლებელია ოპერაციის წარმოება.

განვიხილოთ რა მოხდა ოპერაციაში. ვიწყებთ იქიდან, რომ ვამოწმებთ root უდრის თუ არა null-ს, თუ უდრის მაშინ მეთოდი გავა მეხსიერებიდან. წინააღმდეგ შემთხვევაში ვქმნით რიგს, სადაც ელემენტები FIFO მანერით ხვდებიან და ვამატებთ root ელემენტს. შემდგომ ვიწყებთ იტერაციას მანამ სანამ რიგი არ გაცარიელდება. Root ელემენტის შემდგომ ოპერაცია წაიკითხვას მარცხენა შვილობილ კვანძს და მარჯვენა შვილობილ კვანძს, ჯერ მარცხენას დაამატებს რიგს შემდგომ მარჯვენას. იგივე თანმიმდვრობით დატოვებენ რიგს ელემენტები რაც შედეგად გვაძლევს levelorder თანმიმდევრობას. ნახეთ stack მეხსიერების ფოტო თუ როგორ არიან ისინი მეხსიერებაში განლაგებული.

 

ყველაფერი ნათელი უნდა იყოს წესით. ამ სახის ტრევერსირება არის O(n) ალგორითმის მატარებელი, რაგან ყველა კვანძის წაკითხვა გვიწევს, ხეში.

DFS- Depth First Traversal-ს გააჩნია სამი სახის ოპერაცია ტრევერსირებაზე. ესენია: In-Order, Pre-Order, Post-Order ტრევერსირებები.

In-Order ტრევერსირების დროს როგორც წესი ვიყენებთ stack სტრუკტურულ მონაცემს, რადგან გვაწყობს პირველ ელემენტი, რომელიც მეხსიერებაში მოხვდება რო ბოლო გავიდეს. თუმცა ამ მაგალითზე ვნახავთ უბრალო იტერაციით ტრევერსირებას. მთავარი რამ რაც უნდა გვახსოვდეს In-Order თანმიმდევრობის დროს არის ის, რომ ელემენტები იკითხება leftchild >> root >> rightchild ამ თანმიმდვრობით. ნახეთ ფოტო უკეთ წარმოდგენისთვის.

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

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

Pre-Order ტრავერსირება. ამ სტილით წაკითხვის შემთხვევაში, ეკრანზე პირველი გამოდის მშობელი კვანძი, შემდგომ მარცხენ კვანძი და ბოლო მარჯვენა კვნძი. ელემენტების გამოტანა შესაძლებელია რეკურსიულად და იტერაციულად. ჩვენ ვნახავთ იტერაციულ მაგალითს. აქაც შესაძლებელია Stack სტრუკტურის გამოყენება, მაგრამ აზრს ვერ ვხდები მისი გამოყენების, როდესაც implicity მაინც  Stack  მეხსიერების გამოყენება გვიწევს, გასაუბრებაზე თუ მოხვდით შეიძლება მოგთხოვონ Stack სტრუკტურის გამოყენებით ამ ოპერაციის წამრმოება. გამომცდელს სავარაუდოდ თქვენი Stack -ის ცოდნის შემოწმება სურს. თანმიმდევრობა: root >> leftChild >> rightChild.

ზუსტად ისე გამოიყურება როგორც In-Order, უბრალოდ Sout გადაინაცვლა მაღლა.

ბოლო ტრევერსირების მაგალითი არის Post-Order თანმიმდევრობით ელემენტების ეკრანზე გამოტანა. ალბათ ხვდებით უკვე System.out.print() მეთოდი რომელ ველზე გადაინაცვლებს.

პირველი ეკრანზე მარცხენა შვილობილი გამოდის, მერე მარჯვენა და ბოლოს root ელემენტი. ამით ტრავერსირებაზე საუბარს მოვრჩით.

მოკლე მონახაზი გავაკეთოთ, არსებობს ორი სტილი ტრავერსირების BFS = Breath First Traversal & DFS Deapth First Traversal. BFS ნიშნავს Level Order თანმიმდევრობით ელემენტების ეკრანზე გამოტანას, DFS აქვს 3 ალგორითმი ელემენტების ეკრანზე გამოტანის და ესენია In-Order, Pre-Order & Post-Order. 4-ვე ტრევერსირება არის O(n) ალგორითმის მატარებელი, რადგან ყველა ელემენტის გამოტანა ხდება ეკრანზე.

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

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

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

1. კვანძი რომელიც უნდა წაიშალოს არის ფოთოლი. (ყველაზე მარტივი სიტუაცია). მსგავსად დაკავშირებული სიისა, ვეძებთ კვაძს და მის მშობელკვანძს ვეუბნებით, რომ შვილობილი უდრის Null-ს.

2. კვანძი რომელიც უნდა წაიშალოს არის მშობელი კვანძი, რომელსაც ერთი შვილობილი ყავს.

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

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

ოპერაცია 1. კვანძი რომელსაც ვშლით არის ფოთოლი.

დასაწყისისთვის დაგვჭირდება ორი ცვლადი, current & parent. Current იმოძრავებს ხეში იმ მიმართულებით რა მიმართულებითაც მას გადაწოდებული ელემენტი უკარნახებს და parent ცვლადი, რომელიც მას უკან გაყვება ერთი ნაბიჯის დაშორებით. ძიება მოხდება K ფორმალურ ცვლადზე დაყრდნობით, რადგან ის არის უნიკალური, თუ მოვძებნით K-ს წავშლით V ღირებულებასაც.

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

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

ძიება დაიწყება 20-ან, 17 ნაკლებია 20-ზე, მოხდება if ველეზე ჩაბუდებული if ველის წაკითხვა, მშობელი ცვლადი ამ დროს უდრის 20-ს და current ცვლადი უდრის 15-ს, შემდეგ იტერაციაზე, თუ 17 ნაკლებია 15-ზე მაშინ მარცხნივ უნდა ვიმოძრაოთ, თუ არა და current = current.rightChild-ს, ახლიდან დაიწყება იტერაცია სადაც მშობელი უდრის 15-ს და current ცვლადი 18-ს, ასეთი თანმიმდევრობით გაგრძელდება სანამ 17 არ უდრიდეს იქნება 17-ს. როცა ეს მომენტი დადგება მშობელმა იცის, 17 მისი მარჯვენა შვილობილია თუ მარცხენა, რაგან წაკითხვა მხოლოდ თითო მხარის ხდება თითო იტერაციაზე. ფოტოზე მოცემულ შემთხვევაში წასაშლელი ფოთოლი მარჯვენა ფოთოლია მშობლისთვის, რაც მოახდენს

ამ ველის წაკითხვას, წაშლის 17-ს, შეამცირებს ხის სიდიდეს და დავაბრუნებთ true-ს.

ოპერაცია 2. კვანძი, რომელსაც წავშლით არის მშობელი კვანძი, 1 შვილობილით. წესით ეს ოპერაცია ბოლოს იწერება, პირველი ვამოწმებთ ფოთოლს, მეორე ვამოწმებთ 2 შვილობილზე და თუ ამ ორი ოპერაციის წაკითხვა არ მოხდა ამის შემდგომ ვიცით დანამდვილებით, რომ კვანძი რომელიც უნდა წაიშალოს მშობელია ერთი შვილობილი კვანძით.  მეორე ოპერაცია რამოდენიმე საფეხურით უფრო რთულია პირველზე.

1.     უნდა მოვნახოთ ელემენტი რომელიც უნდა წაიშალოს.

2. უნდა შევამოწმოთ მშობელს რომელ მხარეზე ყავს შვილობილი კვანძი (მარჯვნივ თუ მარცხნივ)

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

კოდი რომელიც მოთავსებულია მარცხენა ხის იტერციის ჩარჩოებში:

თუ ამ ველამდე მოდის კომპილატორი, მაშინ დაზუსტებით ვიცით რომ მშობელს ერთი შვილობილი კვანძი ყავს. რადგან ამ ველის თავზე არის კოდის ნაგლეჯი, რომელიც შლის კვანძს ორი შვილობილი კვანძით. მთავარი რაც გასატვალისწინებელია, სასურველი შედეგის დადგომის დროს, უნდა გადავამოწმოთ რომელ მხარეზე ყავს მშობელს შვილობილი, ვინაიდან ოპერაცია მარცხენა ხეში ხდება დაზუსტებით ვიცით ისიც რომ მშობელი კვანძი რომელიც უნდა წაიშალოს parent კვანძის მარცხნივ დგას. გადამოწმების შემდგომ თუ current ცვლადის მარცხენა კვანძი არ არის ცარიელი, მშობელი კვანძი დასვამს მას მის შემდგომ კვანძად თუ არა და მარჯვენა მხარეს დასვამს შემდგომ კვანძად, რის შედეგადაც მშობელი მიმთითებელს დაკარგავს, მას შემდგომ GC მოაკითხვას და წაშლის. კოდი მარჯვენა ხეში იგივე შინაარსის მატარებელია, უბრალოდ მარჯვენა მიმთითებელით მუშაობს მშობელი.

ნახეტ ამ ოპერაციის ილუსტრაცია ფოტოზე:

მაგალითად თუ ვშლით 18-ს ის მარჯვენა ხის ნაწილია მშობელი კვანძისთვის. ანუ მოხდება წაკითხვა კოდის, რომელიც ბოლო ფოტოზეა. ზუსტად ვიცით რომ 18 მარჯვენა მხარეს იმყოფება, ვამოწმებთ მის მარჯვენა და მარცხენა შვილობილებს, თუ მარცხნივ ყავს შვილი, მაშინ კოდი რომელიც ამოწმებს მარცხენა კვანძს არასდროს წაიკითხება კომპილატორის მიერ, შესაბამისად მშობელს. 15-ს ვეტყვით რომ მისი მარჯვენა კვანძია, current კვანძის ხელ-მარცხნივ მდგომი კვანძი ან მთლიანი ხე. 16 შეიძლება მარცხენა შვილი 14 ყავდეს, რომელსაც ეყოლება 15 და 10 შვილობილი კვანძები, მათაც შეიძლება ეყოლოთ დაბლა კვანძები, ამას ამ კონკრეტულ სიტუაციაში არსებითი მნიშვნელობა არ ექნება.

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

ოპერაცია 3. კვანძი რომელიც უნდა წაიშალოს არის მშობელი ორი შვილობილი კვანძით.

1.     უნდა მოვნახოთ სასურველი კვანძი,

2.     უნდა გადავამოწმოთ არის თუ არა ის მშობელი ორი შვილობილი კვანძით

3.     თუ მშობელია 2 შვილობილით ის უნდა წავშალოთ ისე რომ ხის ბალანსი არ დაირღვეს ამისთვის საჭიროა მშობელ კვანძს მოუნახოთ შემცვლელი, უბრალოდ შემცვლელის მონახვით ფონს ვერ გავალთ, იმიტომ რომ ნებისმიერი ელემენტით თუ შევცვლით მშობელს შესაძლოა ხის ბალანსი დაირღვეს. წარმოიდგინეთ შემდეგი სიტუაცია.

გვაქ მსგავსი ხე, სადაც გვინდა 25-ის წაშლა, რომელმა ელემენტმა უნდა შეცვლალოს 25? 20-მა თუ 45-მა? დაუშვათ ლოგიკური აზროვნებით მივედით იმ დასკვამდე რო 25 უნდა შეცვალოს 20-მა, შეცვლაზე იმიტომ ვსაუბრობ რო მშობელი ელემენტი ხიდან არ იშლება, ის თუ პირდაპირ წაშალეთ ყველა ელემენტს დაკარგავთ რაც მის ქვემოთ დგას. რადგან ის მიმთითებლების მატარებელიც არის გარდა იმისა რო ღირებულება გააჩნია. დაუბრუნდეთ 20-თ შეცვლას, შევცვალეთ 25 და მის ადგილზე გვაქ ახლა 20, რის შემდგომაც 2 პრობლემას გადავაწყდებით, 1. დუბლირებული ელემენტები გვაქ ხეში, 20 მშობელი და 20 შვილობილი, ვინაიდან ჩვენ თავიდანვე მოვახდინეთ ოპერაციების წარმოება ისე რომ დუბლირებული ელემენტები არ ხვდება ხეში, მოგვიწევს შვილობილი 20-ის წაშლა, რაც დაგვაბრუნებს პირველ და მეორე ოპერაციასთან, ანუ 20 შეიძლება ყველაზე კარგ ვარიანტში ფოთოლი იყოს ან შეიძლება მშობელი, 1 ან 2 კვანძით შედეგად კოდი გადაეშვება infinite loop-ში და ვირტუალური მანქანა დაიწყებს 20-ის წაშლას გაუთავებლად. 2. 20-ს შეიძლება მარჯვენა შვილობილი კვანძი ყავს 24, ის 25-ზე ნაკლებია და 20-ზე მეტი რაც მას 20-ის ხელ-მარჯვნივ განათავსებს, 25-ის 20-ით შეცვლის შემდგომ მივიღებთ შემდეგ სურათს, 20 მშობელი მარცხენა შვილობილი 24 და მარჯვენა შვილობილი 45, ორი შვილობილი 20-ზე მეტია. არც ერთი ამათგან არ არის ჩვენთვის გამოსავალი, უფრო მარტივი გზა არის მოსანახი.  ნებისმიერი ხეში მარჯვენა იქნება ის თუ მარცხენა წავაწყდებით მსგავს პრობლემას. გამოსავალი შემდეგში მდგომარეობს, მარჯვენა ხეში მშობელი კვანძის იდეალური შემცვლელია მარჯვნივ მდგარი ხის ყველაზე პატარა ელემენტი, მარცხენა ხეში მშობელი კვანძის იდეალური შემცვლელია მარცხნივ მდგარი ხის ყველაზე დიდი ელემენტი. ნახეთ სურათი უკეთ წარმოდგენისთვის.

მაგალითად, მარჯვენა ხიდან ვშლით 12-ს, მისი იდეალური შემცვლელია არის მარჯვნივ მდგარი ხის ყველაზე პატარა ელემენტი, ყველაზე პატარა ელემენტი როგორც ვიცით განლაგებული იქნება მარცხნივ, ანუ 12-ს შევცვლით 13-ით, რადგან ის მარჯვნივ მდგომი ხის უკიდურესი მარცხენა ელემენტია, 13-ს შეიძლება მარცხენა ელემენტი 11 გააჩნდეს, რაც ასევე კარგი შემცვლელი იქნება, იგივე ლოგიკით უნდა მიუდგეთ მარჯვენა ხესაც, თუ ვშლით 5-ს, მისი იდეალური შემცვლელია მარცხნივ მდგომი ხის ყველაზე დიდი ელემენტი, ანუ 4, ყველაზე დიდი ელემენტი განლაგებულია ხელ-მარჯვნივ ყოველთვის. საკმაოდ მარტივი გამოსავალი ვნახეთ, ამის შემდგომ გასათვალისწინებელია 2 რამ, 1. შეცვლის მერე უნდა წავშალოთ 4 ან 13 ხიდან. 2 წაშლის დროს უნდა გადავამოწმოთ 4-ს ან 13 ხომ არ ყავს შვილობილი, ვინაიდან 13 მარცხენა უკიდურესია ვიცით რომ მას მარცხნივ კვანძი არ ეყოლება მაგრამ გადასამოწმებელია მარჯნივ ყავს თუ არა რამე, იგივე ლოგიკით უნდა მიუდგეთ 4-საც, ვიცით რომ მარჯვენა უკიდურესია, გადავაწმებთ ყავს თუ არა მარცხენა კვანძი. თუ დაფიქრდებით ამ სიმარტივემ ერთი რამ გვასწავლა,  ხეში ვიცით როგორ უნდა მოვნახოთ ყველაზე დიდი ან პატარა ელემენტი.

კოდი ამ ოპერაციის :

მარცხენა ხე:

ვამოწმებთ ელემენტს თუ ყავს 2 კვანძი და ელემენტი თუ უდრის იმ ელემენტს, რომელსაც ვეძებთ, რის შემდგომაც გადავდივართ ოპერაციაზე. If ველზე ვამოწმებთ მარცხენა ხეს ყავს თუ არა მარჯვენა უკიდურესი კვანძი, ვამოწმებთ რადგან შეიძლება არ ყავდეს, ამ შემთხვევაში მოგვიწევს წასაშლელი ელემენტის მარცხენა კვანძით შეცვლა. მაგალითად ვშლით 15, რომელსაც ყავს 2 შვილობილი, და რომელიც უნდა შეიცვალოს მარცხენა შვილობილი კვანძის მარჯვენა უკიდურესი კვანძით, 15-ის მარცხნივ დგას 14, რომელსაც არ ყავს მარჯვენა კვანძი, მაშინ დროებით ცვლადში ვინახავთ 15--ის მარჯვენა კვანძს, 14 გადმოგვაქ 15-ის ადგილზე და მშობელ კვაძს ვეუბნებით რომ 14 მარჯვენა კვანძი/ები არის დროენით კვანძში შენახული ღირებულებები. მარცხენა კვანძები ავტომატურად მოყვება 14-ს, მათი მიბმა არ არის საჭირო. Else  ველზე, ვიცით, რომ მარცხნივ მდგომ ხეს ყავს მარჯვენა უკიდურესი კვანძი, შესაბამისად, ვახდენთ მის ტრევერსირებას, შემდეგი მეთოდის დახმარებით:

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

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

მაშ ასე დაგვრჩა ერთი ოპერაცია, Root ელენენტის წაშლა, როგორც წესი მის წაშლას მშობელი კვანძის წაშლა ითავსებს მაგრამ მაგალითისთვის და უკეთ გააზრებისთვის ცალკე დავწერე,

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

მაშ ასე, ბინარული ხის ყველა მნიშვნელოვან ოპერაციებს გავეცანით, add, search, delete. ალბათ delete მეთოდის ნახვის შემდგომ არც ისე რთულად გეჩვენებათ add და search მეთოდები. ამის შემდგომ ვნახავთ სასარგებლო მეთოდებს და ალგორითმებს, რომელსაც ბინარულ ხეში იყენებენ ან რომელსაც შეიძლება გასაუბრებაზე შეხვდეთ. მაგალითად ხის ბალანსის შემოწმება, სიმაღლის, სასურველი ქვე-ხის ტრევერსირება, სასურველ ლეველზე ტრევერსირება, დიდი და პატარა ელემენტების ძიება, complete, full და perfect თანმიმდევრობებზე გადამოწმება (complete, full და perfect აგების მაგალითებს არ ნახავთ, რადგან მათ RBT & AVL Tree-ზე საუბრის დროს განვიხილავთ)

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

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

თუ ხე ცარიელია ვაბრუნებთ 0-ს თუ არა და დავაბრუნებთ ორ ქვე ხეს შორის ყველაზე დიდი ხის სიდიდეს +1-ს. +1-ს რატომაც ვაბრუნებთ ხვდებით ალბათ, ძიებას პირდაპირ ქვე ხეებში ვიწყებთ, შესაბამისად ვტოვებთ root ელემენტს ძიების გარეთ, ამიტომაც მისი Level დაემატება +1-ით.

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

კომპილირების შემდგომ:

ამ ხეს თუ დავამატებთ ერთ კვანძს მარჯვენა ხეში მაშინ ხის ბალანსი დაირღვევა:

კომპილირების შემდგომ:

შემდეგ მაგალითზე ნახავთ მეთოდს, რომელიც გვითვლის რამდენი External(Leaf) კვანძია ხეში:

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

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

კომპილირების შემდგომ:

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

მეთოდი კომპილირების შემდგომ:

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

მეთოდი დაგვიბრუნეს სიას კვანძებისა რომელიც განლაგებულია მშობელი კვანძიდან სასურველ კვანძამდე. ნახეთ მისი მაგალითი კომპილირების შემდგომ:

იგივე ლოგიკით შესაძლებელია უმოკლესი მანძილის მონახვა 2 კვანძს შორის. უკეთ წარმოდგენისთვის ხეს დავამატე რამოდენიმე ელემენტი:

 

ორ კვანძს შორის უმოკლეს მანძილს კი მოგვინახავს შემდეგი მეთოდი.

ერთი და იგივე რომ არ ვწეროთ ვიყენებთ მეთოდს, რომელიც ეძებს მანძილს მშობელი კვანძიდან ნებისმიერი კვანზამდე, ჯერ ვპოულობთ ერთ ელემენტს, შემდგომ მეორეს, მოძიება რომ დასრულდება პირველი სიის რევერსირეაბს ვახდენთ რათა ბოლო ელემენტიდან დაიწყოს კონზოლში გამოტანა და არა Root ელემენტიდან. რევერსირების აუცილებლობას მხოლოდ მარცხენა ხე წარმოადგენს ან მხოლოდ მარჯვენა, გააჩნია რა თანმიმდევრობით გადავაწოდებთ ელემენტებს მეთოდს. ამის შემდგომ 3 რამ არის გასატვალისწინებელი:

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

2. ელემენტები რომლესაც გადავაწოდებთ მეთოდს შესაძლებელია მოთავსებულ იქნენ მარჯვენა ხეში,

3.     ელემენტები რომელსაც გადავაწოდებთ მეთოდს იმყოფებიან სხვა და სხვა ხეში.

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

პირველ ამოცანას. შემდეგი ველი გაართმევს თავს.

თუ პირველი სია შეიცავს ელემენტებს მეორე სიიდან, რომელიც მასივშია მოთავსებული, მაშინ სიას უნდა მოვაცილოთ დუბლირებული ელემენტები. სხვა დანარჩენი კი დავამატოთ, ამის შემდგომ ცალკე ვაცლით Root კვანძს და ოპერაცია მზად არის. ამ ოპერაციის გაცილებით მცირე კოდით შესრულებაც შეიძლება, თუმცა ასე უფრო წაკითხვადი და მარტივად გასააზრბელი მგონია. იგივე ოპერაციას გავიმეორებთ მარცხენა ხეში, ბოლო ოპერაცია თუ ელემენტები ცალ-ცალკე ხესია მოთავსებული დააკლდება for ველზე შესრულებული ოპერაცია. როგორც წესი ამ მეთოდის დაწერა ხდება რეკურსიულად რაც ნიშნავს იმას რომ სასურველი მიზნის მისაღწევად ყველა კვანძის წაკითხვა გვიწევს ხეში, რაც O(n) ალგორითმის მატარებელია. ჩემი აზრით ამ სახით იმპლემენტაცია გაცილებით სწრაფია რადგან ვკითხულობთ მხოლოდ იმ კვანძებს რომელიც გვჭირდება და არა მთლიან ხეს. მართალია ესეც O(n) ალგორითმის მატარებელია რამოდენიმე იტერაციის გამო რომელიც მეთოდში გვხვდება მაგრამ წასაკითხი ელემენტების ოდენობა გაცილებით ნაკლებია, შესაბამისად მისი ალგორითმი გაცილებით სწრაფია.

კომპილირების შემდგომ:

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

ამით ბინარულ ხეზე საუბარს მოვრჩით. დანარჩენ მაგალითებს ნახავთ GitHub-ზე. შემდეგი ბლოგები იქნება AVL, RBT, Heap და სხვა რამოდენიმე მნიშვნელოვან ხეზე, რომელებიც მოიცავენ Complete, full, Perfect, Balanced ხეების აგების მაგალითებს. ბალანსირებული ხის ბინარულად აგება ახლაც შეგვეძლო, თუმცა ჯობია ამ თავში გამოვტოვოთ, საკმაოდ მოცულობითი იმფორმაციის მატარებელია ბლოგი. ხეზე საუბარს რო მოვრჩებით, შემდგომ ვისაუბრებთ HashTable-ზე და მხოლოდ ამის შემდგომ განვიხილავთ Set & Map სტრუკტურებს, რაგან ეს 2 სტრუკტურა მოიცავს ხეს და ჰეშირებულ მაგიდას. მე ამით დაგემშვიდობებით, მომავალ შეხვედრამდე. 

კოდის სრულად სანახავად გადადით შემდეგ ბმულზე