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

                                                              Red Black Tree

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

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

1972 წელს რუდოლფ ბაიერმა შექმნა B-tree, რომელსაც Root კვანძიდან ფოთლამდე ქონდა ერთი და იგივე კვანზების ოდენობა, რაც ნიშნავს იმას რომ ხე გახლდათ Perfectly Balanced Tree, ბაიერმა მას Symmetric Binary B-Tree (B-Tree) უწოდა, თუმცა ის არ გახლდათ ბინარული ხე, მოგვიანებით ხეს სახელი შეეცვალა და დღეს ის ნაცნობია როგორც 2-3-4 Tree.

1978 წელს რობერტ სენდგევიკმა და ლეონიდას გულბასმა შექმნეს Symmetric Binary B-Tree-ზე დაყრდნობით ხე, რომელსაც Red Black Tree-ს სახელით იცნობს დღეს მსოფლიო და რომელიც ბინარული ხის სახეობაში ხვდება, მას გააჩნია Root კვანძი და ორი შვილობილი კვანძი, ელემენტები ხეში სიევე ხვდებიან როგორც ბინარულ ხეში, პატარა ელემენტები მარცხნივ , დიდი ელემენტები მარჯვნივ, რომელსაც ემატება ფერი (შავი ან წითელი) და რაზე დაყრდნობითაც  ის ახდენს ბალანსირებას. ბალანსირება რო ერთ-ერთი ყველაზე მნიშვნელოვანი (ყველაზე მნიშვნელოვანი თუ არა) ფუნქციონალიზმია ხის ამაზე ბინარულ ხეზე საუბრის დროს ვისაუბრე.  განსაკუთრებულობას მას ერთი უნარი ანიჭებს, მაგალითად ბინარული ხის ალგორითმია Average O(log n), Worst Case O(n), საშუალო და ყველაზე ცუდი სიტუაცია სადაც შეიძლება ჩვენი კოდი აღმოჩდეს, კარგი და იდეალური სიტუაციები არ გვაინტერესებს, Red Black Tree-ს ალგორითმია Average O(log n), Worst Case O(log n), რაც მეტყველებს ერთ რამეზე, Red Black Tree დეგენერაციას არ განიცდის, დროის რაღაც მონაკვეთში ელემენტების დამატების დროს შეიძლება მოხდეს ისე რო ელემენტები თანმიმდევრობით დაემატოს, როგორც დაკავშირებულ სიაში და რომლის საფრთხეც არსებობს ბინარულ ხეში, მაგრამ ის აუცილებლად მაოხდენს რებალანსირებას და Red Black Tree ხე დაუბრუნდება მისთვის ჩვეულ ალგორითმს. ეს პროცესი აგრეთვე მეტყველებს იმაზე რო Red Black Tree გახლავთ Height Balanced Tree, ბალანსირება ხის როგორც მოწმდება უკვე იცით, Height Balanced რატომ არის წესით ხვდებით.

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

წესი ნომერი:

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

2.     Root კვანძი არის ყოველთვის შავი:

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

3.      ყველა ახალი ელემენტი რომელიც ემატება სტრუკტურას არის ყოველთვის წითელი.

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

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

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

5.     არ არის ნებადართული იქონიოთ ორი წითელი კვანძი თანმიმდევრობით.

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

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

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

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

პირველი ალბათ საიდანაც უნდა დავიწყოთ ხის შექმნა ეს კვანძებია, ჩვეულებრივ ბინარულ ხეს 2 მიმთითებელი აქვს, Red Black Tree-ს სამი მიმთითებელი გააჩნია თუ Boolean ტიპით ვიმუშავებთ, ან 4 მიმთითებელი თუ რაიმე სახის კონსტანტით.  ამის შემდგომ მოგვიწევს საბაზისო მეთოდების შექმნა, ესენია Add(), Search(), Delete(), ძიების მეთოდს არაფერი განსხვავებული არ გააჩნია, ამიტომ განვიხილავთ დამატების და წაშლის მეთოდებს, რომლებიც საკმაოდ კომპლექსურები არიან. ვინაიდნ 6-ვე პუნტკის გათვალისწინება გვიწევს წერის დროს დაგვჭირდება რამოდენიმე , ან რამოდენიმე ათეული დამხმარე მეთოდების, რომლებიც ამ 2 მეთოდს დაეხმარებიან ფუნქციონირებაში. მათ სათითაოდ ვერ ვნახავთ, ყველას ერთად ნახავთ Github-ზე. 

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

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

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

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

როტაციის შემდგომ:

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

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

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

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

1.     მარცხენა კვანძის როტაცია.

RightRotation ვახდენთ მაშინ თუ წესის დარღვევა ხება მარცხენა კვანძ-ზე, რომელსაც ყავს მარცხენა მშობელი კვანძი, როტაცია როგორც წესი დიდი მშობელი(ბაბუა/ბებია) კვანძის ირგვლივ ხდება.  RightRotation შეცდომა არ გეგონოთ, როცა დარღვევა ხდება მარცხენა ხეში როტაციას ვახდენთ მარჯვნივ, ადვილად დასამახსოვრებელია, მარცხენა დარღვევა = მარჯვენა როტაციას.  ფოტოზე მოცემულ შემთხვევაში ნომერი 3 არის დიდი მშობელი კვანძი, მარჯვნივ როტაციის შემდგომ მშობელი კვანძი გახდება კვანძი ნომერი 2, მარჯვენა შვილობილი კვანძი 3 და მარცხენა შვილობილი კვანძი 1. როდესაც მოვრჩებით როტაციას მეთოდი, რომელიც ახდენს ამ ოპერაციის წარმოებას რეკურსიულად გამოიძახებს მშობელ კვანძს და გადამოწმებს დარღვევებზე, რეკურსია გაგრძელდება მანამ სანამ მიმთითებელი არ მივა Root კვანძამდე, ანუ ნებისმიერი როტაციის თუ ფერის ცვალების შემდგომ ვამოწმებთ მთლიან  ხეს ნაბიჯ-ნაბიჯ.

2.     მარჯვენა კვანძის როტაცია:

როდესაც დარღვევა გვაქ მარჯვენა ხეში ვახდენთ LeftRotation-ს. მარცხნივ როტაცია ხდება დიდი მშობელი კვანძის (კვანძი ნომერი 3) ირგვლივ.

3.     მარცხენა-მარჯვენა კვანძის როტაცია.

LeftRightRotation ვიყენებთ მაშინ როცა კვანძი რომელიც წესებს არღვევს არის მარცხენა კვანძის მარჯვენა შვილობილი. წესი აქაც იგივეა, როტაცია ხდება დიდი მშობელის ირგვლივ, თვითონ LeftRightRotation 2 ოპერაციისგან შედგება და ამას სახელიდანაც მიხვდით ალბათ, ჯერ ვახდენთ მარცხენა როტაციას და მერე მარჯვენა როტაციას. თუ წარმოვიდგნეთ ზემოთ მოყვანილ სურათზე ელემენტებს : დაუშვათ კვანძი ნომერი 3 არის 6, კვანძი ნომერი 2 არის 4 და კვანძი ნომერი ერთი არის 5. გამოგვივა 6 >> მარცხენა 4 >> მარჯვენა 5. ჯერ მოვახდენთ მარცხნივ როტაციას, დიდი მშობელის მარცხენა კვანძის,  შემდგომ კი მოვახდენთ მარჯვენა როტაციას დიდი მშობელის. 

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

4.     მარჯვენა-მარცხენა როტაცია.

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

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

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

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

3.     როტაცია ხდება დიდი მშობელი კვანძის ირგვლივ.

4.     არსებობს 4 სახის როტაცია, LeftLeft, RightRight, LeftRight, RightLeft Rotations.

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

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

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

ნახეთ ფოტო დამატების მეთოდის, დამხმარე მეთოდებთან ერთად.

Add()

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

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

Add მეთოდის დამხმარე მეთოდი ასე გამოიყურება:

მეთოდი არის რეკურსიული და ის საკუთარ თავს გამოიძახებს მანამ სანამ არ მიუახლოვდება სიცარიელეს ან Root ელემენტს. ამ მეთოდს ეხმარება correctTree მეთოდი, რომელსაც რამოდენიმე ათეული დამხმარე მეთოდი ყავს..

ფოტოზე ხედავთ მარცხენა ქვე-ხის მაგალითს, მარჯვენა ხის კოდი იდენტურია. როგორც ატყობთ მხოლოდ მეთოდებით მიმდინარეობს ოპერაციები. flipColor, GrandPArentNode, ParentNod, Rotates, isRed, IsBlack და ასე შემდეგ.

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

როგორც იცით ელემენტის დამატების დროს ორიენტირებას დეიდა/ბიძა კვანძზე დაყრდნობით ვახდენთ, თუ ის წითელია ვახდენთ გადაფერადებას, თუ ის შავია ვახდენთ როტაციას, ამას ვაკეთებთ მაშინ როცა ხეში ორი წითელი კვანძი გვხვდება თანმიმდევრობით, ანუ ყველა ჩამოთვლილი წესიდან 2 წესის გამოყოფა შეიძლება, რომლებზე დაყრდნობითაც ვიცავთ ყველა სხვა დანარჩენ წეს,  მშობელი კვანძის მონათესავე კვანძის ფერი და ორი წითელი კვანძი თანმიმდევრობით. წასშლასაც დაახლოებით იგივე ამომავალი წერტილები აქვს, უბრალოდ წაშლის დროს ვითვალისწინებთ მონათესავე კვანძის ფერს და არა მშობელი კვანძის მონათესავე კვანძის ფერს და დისბალანსი ხემ წაშლის დროს მხოლოდ მაშინ შეიძლება განიცადოს როცა ვშლით შავს კვანძს, როგორც 6 საბაზისო წესი გვეუბნება, ყველა შავი კვანძის ოდენობა მშობელი კვანძიდან ნებისმიერ ფოთლამდე არის ერთი და იგივე ოდენობს, წაშლის დროს ეს ბალანსი ხშირად იღვევა. მაშ ასე კიდევ ერთხელ გავიმეორებ ძირითად წესებს. დამატების დროს ვითვალისწინებთ მშობელი კვანძის მონათესავე კვანძის ფერს და ხის ბალანსირებას ვახდენთ თუ ხეში გვხვდება ორი წითელი კვანძი თანმიმდევრობით. პროგრამისტები ამ პრობლემას Double Red Problem-ს ეძახიან.  წაშლის დროს ვითვალისწინებთ წასაშლელი კვანძის მონათესავე კვანძის ფერს და შავი კვანძის დისბალანს წაშლის შემდგომ, ამ პრობლემასაც აქვს სახელი და მას Double Black Problem-ს ეძახიან ხოლმე. ამ წესების გარდა წაშლას აქვს 8 დამატებითი წესი, საბაზსი 3 წესი  + მესამე წეს გააჩნია 6 დამატებითი წესი. რაც საერთო ჯამში გვაძლევს 8 წეს.

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

მაგალითად თუ გვაქ შემდეგი ფორმის ხე:

ელემენტი ნომერი 20-ის წაშლა არანაირ ზეგავლენას არ იქონიებს ხეზე, მისი წაშლა სესაძლებელია პირდაპირ:

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

ელემენტ ნომერ 65-ს გადავიტანთ 60-ის ადგილზე და 65 წავშლით ისევ როგორც ფოთოლს.

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

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

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

 

და გვინდა კვანძი ნომერი 30--ის წაშლა, ის ფოთოლი კვანძია და პირდაპირ წავშლით, თუმცა წაშლის შემდგომ მოხდება ხის დისბალანსი, რადგან ხის მარჯვენა მხარეს შავი კვანძების ოდენობა უდრის 3-ს. და მარცხენა მხარეს უდრის ორს, 6 საბაზისო წესი გვეუბნება რომ მშობელი კვანძიდან ფოთოლ კვანძამდე შავი კვანძების ოდენობა არის ერთი და იგივე, მსგავს სიტუაციაში როცა ვხვდებით გვაქ 6 წესი რომელიც ხის დაბალანსებაში გვეხმარება. მესამე წეს დავარქვათ Double Black Problem:

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

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

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

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

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

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

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

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

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

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

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

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

6. გაიმეორეთ ეს ყველაფერი მანამ სანამ არ მიაღწევთ Root ელემენტამდე.

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