ორობითი საძიებო ხის განხორციელება

2024 ავტორი: Angel Austin | [email protected]. ბოლოს შეცვლილი: 2023-12-17 05:32

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

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

ზოგადი თეორია და ტერმინოლოგია

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

ხის ტერმინოლოგია:

1. კვანძის სიღრმე არის ფესვიდან მასამდე განსაზღვრული კიდეების რაოდენობა.
2. კვანძის სიმაღლე არის მისგან ყველაზე ღრმა ფოთლამდე განსაზღვრული კიდეების რაოდენობა.
3. ხის სიმაღლე განისაზღვრება ფესვის სიმაღლით.
4. ორობითი საძიებო ხე არის სპეციალური დიზაინი, ის უზრუნველყოფს სიმაღლისა და კვანძების რაოდენობის საუკეთესო თანაფარდობას.
5. სიმაღლე h N კვანძით მაქსიმუმ O (ლოგი N).

ეს მარტივად შეგიძლიათ დაამტკიცოთ კვანძების დათვლით თითოეულ დონეზე, დაწყებული ფესვიდან, იმ ვარაუდით, რომ ის შეიცავს მათ ყველაზე დიდ რაოდენობას: n=1 + 2 + 4 + … + 2 სთ-1 + 2 სთ.=2 სთ + 1 - 1 ამის ამოხსნა h-ისთვის იძლევა h=O (log n).

ხის სარგებელი:

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

ძიების მეთოდი

ზოგადად, იმის დასადგენად, არის თუ არა მნიშვნელობა BST-ში, დაიწყეთ ბინარული საძიებო ხე მისი ფესვიდან და დაადგინეთ, აკმაყოფილებს თუ არა ის მოთხოვნებს:

• იყავი ძირში;
• იყავით ფესვის მარცხენა ქვეხეში;
• ძირის მარჯვენა ქვეხეში.

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

1. ხე ცარიელია - დააბრუნეთ ყალბი.
2. მნიშვნელობა არის ძირეულ კვანძში - დააბრუნეთ true.

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

სხვა სიტყვებით რომ ვთქვათ, არსებობს კავშირი BST-ში კვანძების რაოდენობასა და ხის სიმაღლეს შორის, მისი "ფორმის" მიხედვით. უარეს შემთხვევაში, კვანძებს ჰყავთ მხოლოდ ერთი შვილი და დაბალანსებული ორობითი საძიებო ხე არსებითად არის დაკავშირებული სია. მაგალითად:

50

/

10

15

30

/

20

ამ ხეს აქვს 5 კვანძი და სიმაღლე=5. მნიშვნელობების პოვნა 16-19 და 21-29 დიაპაზონში დასჭირდება შემდეგ გზას ფესვიდან ფოთლამდე (კვანძი, რომელიც შეიცავს მნიშვნელობას 20), ე.ი., დრო დასჭირდება კვანძების რაოდენობის პროპორციულად. საუკეთესო შემთხვევაში, მათ ყველას 2 შვილი ჰყავთ და ფოთლები ერთსა და იმავე სიღრმეზეა განთავსებული.

ამ ბინარულ საძიებო ხეს აქვს 7 კვანძი და სიმაღლე=3. ზოგადად, მსგავს ხეს (სრულ ხეს) ექნება სიმაღლე დაახლოებით log 2 (N), სადაც N არის კვანძების რაოდენობა ხეში.. ჟურნალი 2-ის (N) მნიშვნელობა არის რამდენჯერმე (2), რომელიც N შეიძლება გაიყოს ნულის მიღწევამდე.

შეჯამება: BST-ში ძიების ყველაზე ცუდი დრო არის O (ხის სიმაღლე). ყველაზე უარესი "წრფივი" ხე არის O(N), სადაც N არის კვანძების რაოდენობა ხეში. საუკეთესო შემთხვევაში, "სრული" ხე არის O(log N).

BST ორობითი ჩასმა

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

1. დუბლიკატები დაუშვებელია, დუბლიკატი მნიშვნელობის ჩასმის მცდელობა გამოიწვევს გამონაკლისს.
2. საჯარო ჩასმის მეთოდი იყენებს დამხმარე რეკურსიულ "დამხმარე" მეთოდს რეალურად ჩასართავად.
3. ახალი მნიშვნელობის შემცველი კვანძი ყოველთვის ჩასმულია როგორც ფოთოლი BST-ში.
4. საჯარო ჩასმის მეთოდი აბრუნებს void, მაგრამ დამხმარე მეთოდი აბრუნებს BSTnode-ს. ის ამას აკეთებს იმ შემთხვევისთვის, როდესაც მასზე გადაცემული კვანძი არის null.

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

წაშლა ბინარულ ალგორითმში

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

1. BST იყენებს დამხმარე, გადატვირთულ წაშლის მეთოდს. თუ ელემენტი, რომელსაც თქვენ ეძებთ, არ არის ხეში, მაშინ დამხმარე მეთოდი საბოლოოდ გამოიძახება n==null-ით. ეს არ ითვლება შეცდომად, ხე უბრალოდ არ იცვლება ამ შემთხვევაში. წაშლის დამხმარე მეთოდი აბრუნებს მნიშვნელობას - მაჩვენებელს განახლებულ ხეზე.
2. როდესაც ფოთოლი ამოღებულია, ორობითი საძიებო ხიდან ამოღება აყენებს მისი მშობლის შესაბამის შვილო მაჩვენებელს ნულზე, ან ფესვს ნულზე, თუ წაშლილი არისკვანძი არის ფესვი და არ ჰყავს შვილები.
3. გაითვალისწინეთ, რომ წაშლის ზარი უნდა იყოს ერთ-ერთი შემდეგი: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), გასაღები)). ამრიგად, სამივე შემთხვევაში სწორია, რომ წაშლის მეთოდი უბრალოდ აბრუნებს null.
4. როდესაც წაშლილი მნიშვნელობის შემცველი კვანძის ძიება წარმატებულია, არსებობს სამი ვარიანტი: წასაშლელი კვანძი არის ფოთოლი (შვილები არ ჰყავს), წასაშლელი კვანძს ჰყავს ერთი შვილი, მას ჰყავს ორი. ბავშვები.
5. როდესაც ამოღებულ კვანძს ჰყავს ერთი შვილი, შეგიძლიათ უბრალოდ შეცვალოთ ის ბავშვით, დააბრუნოთ მაჩვენებელი ბავშვს.
6. თუ წასაშლელი კვანძს ჰყავს ნული ან 1 შვილი, მაშინ წაშლის მეთოდი "მიჰყვება გზას" ძირიდან ამ კვანძამდე. ასე რომ, ყველაზე ცუდი დრო ხის სიმაღლის პროპორციულია, როგორც საძიებლად, ასევე ჩასართავად.

თუ ამოსაღებ კვანძს ორი შვილი ჰყავს, გადაიდგმება შემდეგი ნაბიჯები:

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

ტრავერსიების რიგი

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

• გადაკვეთის სიღრმე;
• პირველი საშვი.

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

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

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

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

1. წინასწარი შეკვეთა - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. მიმდევრობით - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. გამოქვეყნების შეკვეთა - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. დონის ორდერი - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

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

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

ნავიგაცია და გამართვა

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

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

ფუნქცია Konsolenausgabe

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

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

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

ასლი კონსტრუქტორი და დესტრუქტორი

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

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

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

ბინარული საძიებო ხის შექმნა

ოპტიმალური ორობითი საძიებო ხეები წარმოუდგენლად ეფექტურია, თუ სწორად იმართება. ორობითი საძიებო ხეების რამდენიმე წესი:

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

მაივი, რომელიც გამოყენებული იქნება ორობითი საძიებო ხის შესაქმნელად:

1. შვიდი მნიშვნელობის საბაზისო მთელი მასივი დაუხარისხებელი თანმიმდევრობით.
2. მასივის პირველი მნიშვნელობა არის 10, ასე რომ, ხის აგების პირველი ნაბიჯი არის 10 ძირიანი კვანძის შექმნა, როგორც ეს ნაჩვენებია აქ.
3. root კვანძების ნაკრებით, ყველა სხვა მნიშვნელობა იქნება ამ კვანძის შვილი. წესების გათვალისწინებით, პირველი ნაბიჯი, რომელიც უნდა გადაიდგას ხეზე 7-ის დასამატებლად არის მისი შედარება ფესვის კვანძთან.
4. თუ მნიშვნელობა 7 არის 10-ზე ნაკლები, ის გახდება მარცხენა ბავშვის კვანძი.
5. თუ მნიშვნელობა 7 მეტია ან ტოლია 10-ის, ის გადავა მარჯვნივ. ვინაიდან ცნობილია, რომ 7 არის 10-ზე ნაკლები, ის აღინიშნება, როგორც მარცხენა ბავშვის კვანძი.
6. რეკურსიულად შეასრულეთ შედარება თითოეული ელემენტისთვის.
7. იგივე ნიმუშის შემდეგ, შეასრულეთ იგივე შედარება მასივის მე-14 მნიშვნელობის წინააღმდეგ.
8. 14 მნიშვნელობის შედარება ძირეულ კვანძთან 10, იმის ცოდნა, რომ 14 არის სწორი შვილი.
9. გასეირნება მასივში,მოდი 20-მდე.
10. დაიწყეთ მასივის 10-ის შედარებით, რომელი უფრო დიდია. ასე რომ, გადადით მარჯვნივ და შეადარე 14-ს, ის 14 წელს გადაცილებულია და მარჯვნივ შვილი არ ჰყავს.
11. ახლა არის 1-ის მნიშვნელობა. მიჰყევით იმავე შაბლონს, როგორც სხვა მნიშვნელობები, შეადარეთ 1-დან 10-მდე, გადაადგილდით მარცხნივ და შეადარეთ 7-ს და ბოლოს მე-7 კვანძის 1 მარცხენა შვილს.
12. თუ მნიშვნელობა არის 5, შეადარეთ ის 10-ს. ვინაიდან 5 არის 10-ზე ნაკლები, გადადით მარცხნივ და შეადარეთ 7-ს.
13. იცოდით, რომ 5 არის 7-ზე ნაკლები, გააგრძელეთ ხეზე და შეადარეთ 5 1 მნიშვნელობით.
14. თუ 1-ს არ ჰყავს შვილი და 5 არის 1-ზე მეტი, მაშინ 5 არის 1 კვანძის სწორი შვილი.
15. ბოლოს ჩადეთ მნიშვნელობა 8 ხეში.
16. როდესაც 8 არის 10-ზე ნაკლები, გადაიტანეთ იგი მარცხნივ და შეადარე 7-ს, 8 მეტია 7-ზე, ამიტომ გადაიტანეთ იგი მარჯვნივ და შეავსეთ ხე, რათა 8 იყოს 7-ის სათანადო შვილი.

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

ორობითი ძიების პოტენციური პრობლემები

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

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

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

ორობითი ძიების გაანგარიშების მაგალითები

ჩვენ უნდა განვსაზღვროთ რა სახის ხე იქნება, თუ 25 ჩასმული იქნება ორობითი საძიებო ხეში:

10

/

/

5 15

/ /

/ /

2 12 20

X-ის ჩასმისას T ხეში, რომელიც ჯერ არ შეიცავს x-ს, გასაღები x ყოველთვის მოთავსებულია ახალ ფურცელში. ამასთან დაკავშირებით ახალი ხე ასე გამოიყურება:

10

/

/

5 15

/ /

/ /

2 12 20

25

რა სახის ხეს მიიღებდით, თუ 7-ს ჩასვამდით შემდეგ ბინარულ საძიებო ხეში?

10

/

/

5 15

/ /

/ /

2 12 20

პასუხი:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

ორობითი საძიებო ხე შეიძლება გამოყენებულ იქნას ნებისმიერი ობიექტის შესანახად. ორობითი საძიებო ხის გამოყენების უპირატესობა დაკავშირებული სიის ნაცვლად არის ის, რომ თუ ხე გონივრულად დაბალანსებულია და უფრო ჰგავს "სრულ" ხეს, ვიდრე "წრფივ", ჩასმა, ძიება და ყველა წაშლის ოპერაციები შეიძლება განხორციელდეს გასაშვებად. O(log N) დრო.