წითელ-შავი ხე შესავალი


Რთული ტური Hard
ხშირად ეკითხებიან Amazon CodeNation Facebook Google Uber
მონაცემთა მოწინავე სტრუქტურა ორობითი ძებნა ხე ორობითი ხე Მონაცემთა სტრუქტურა ხე

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

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

  1. ყველა კვანძი წარმოდგენილია როგორც წითელი, ასევე შავი.
  2. ძირეული კვანძი ყოველთვის შავია.
  3. წითელ კვანძს არ შეიძლება ჰქონდეს წითელი მშობელი ან წითელი შვილი (ანუ ორი წითელი კვანძი არ არის მომიჯნავე).
  4. ნებისმიერი გზა ნებისმიერი კვანძიდან მის NIL შთამომავლამდე უნდა შეიცავდეს თანაბარი რაოდენობის შავ კვანძებს.

წითელი და შავი ხის სწორი და არასწორი მაგალითები

წითელ-შავი ხე შესავალი

წითელ-შავი ხე შესავალი

დროის სირთულის ანალიზი

BST– ის ყველა ოპერაცია, როგორიცაა ძებნა, ჩასმა, წაშლა და ა.შ. შეიძლება შესრულდეს O (h) დროში, სადაც h არის წითელი – შავი ხის სიმაღლე, ხოლო დაბალანსებული BST– სთვის სიმაღლე ყოველთვის რიგისაა. ჟურნალი (n) [n-> კვანძების რაოდენობა].

Searching = O (ჟურნალი (n))
Insertion = O (ჟურნალი (n))
წაშლა = O (ჟურნალი (n))

შავი სიმაღლე წითელ-შავ ხეში

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

წითელ-შავი ხის სიმაღლე

განსხვავებით Avl ხე, სიმაღლის ბალანსი არც ისე მკაცრია, მაგრამ წითელ-შავ ხეებში ბრუნვების რაოდენობა AVL ხეებთან შედარებით ნაკლებია.
წითელ-შავი ხის სიმაღლე h <= 2 (ჟურნალი (n + 1)) {ჟურნალის ბაზა არის 2} დეტალური მტკიცებულება რატომ არის RB ხეების სიმაღლე <= 2 ჟურნალი (n + 1).

სიმაღლეში ბალანსის შესანარჩუნებლად წითელი შავი ხე იყენებს ფერის შეცვლას და რესტრუქტურიზაციას.

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

გახსენება

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

წითელ-შავი ხე შესავალი

 

რესტრუქტურიზაცია

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

  • მარჯვენა
  • მარცხენა
  • მარჯვენა-მარცხენა
  • Მარცხენა მარჯვენა

პროგრამები

  • რეალურ ბიბლიოთეკებში გამოიყენება თვითდაბალანსების BST– ების განსახორციელებლად.
  • გამოიყენება როგორც TreeSet და TreeMap in JAVA და Sets and Maps in C ++.

Searching

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