Წითელი შავი ხეები: მიმოხილვა, მახასიათებლები

Rudolph Bayer შეიმუშავა სისტემა "წითელი-შავი ხე" 1970. სახელი ამ მას გადაეცა Gimpas L. და რ Sedgewick.

რა წითელი-შავი ხეები

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

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

გაჩენის ტერმინი

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

პროგრამა

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

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

მახასიათებლები

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

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

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

რატომ წითელი შავი ხეები

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

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

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

პროცესები

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

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

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

უფრო ჩვენი ქმედებები პირდაპირ არის განპირობებული ფერის მიმდებარე კვანძების. ტერმინი "ბიძა" გამოიყენება მათ. პირდაპირი ანალოგიით ოჯახის ხე. ამიტომ:

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

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

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