დაბალანსებული ხეები და set / map

ჩვეულებრივ ძებნის ხეს დალაგებული მონაცემები მიაწოდე და ის ჩუმად ბმულ სიად იქცევა. დაბალანსებული ხეები O(log n)-ს ნებისმიერ შემავალ მონაცემებზე გვპირდება და ყოველ ჯერზე, როცა std::set-ს ან std::map-ს წერ, სწორედ მათ იყენებ.

საშუალო⏱ 10 წთ

←ეყრდნობა

5ძებნის ორობითი ხეძებნის ხე O(n)-მდე ეცემა, როცა ჯაჭვად იზრდება; ბალანსი h = O(log n)-ს ინარჩუნებს.1ჰეშ-ცხრილები: set და mapstd::set და std::map არის unordered_set-ისა და unordered_map-ის დალაგებული ვერსიები.

გზას უხსნის→

10ერთგანზომილებიანი დპ: მონეტები და LISO(n log n) LIS საუკეთესო ბოლოებს დალაგებულად ინახავს და ადგილს lower_bound-ით პოულობს, როგორც std::set-ში.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ფორმა განსაზღვრავს ღირებულებას

ძებნის ხის ყოველი ოპერაცია O(h) ღირს, h კი მხოლოდ ჩასმის რიგზეა დამოკიდებული. ჩასვი 1, 2, 3, 4, 5, 6, 7 და ყოველი გასაღები წინას მარჯვნივ ებმება: 6 სიმაღლის ჯაჭვი, search(7) კი შვიდივე გასაღებს ამოწმებს. ჩასვი იგივე გასაღებები რიგით 4, 2, 6, 1, 3, 5, 7 და მიიღებ 2 სიმაღლის იდეალურ ხეს: სამი შედარება.

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

გვჭირდება ხე, რომელიც თავად ინარჩუნებს მცირე სიმაღლეს ჩასმის რიგის მიუხედავად: n გასაღებისთვის h = O(log n). დაბალანსება ძებნის ხის არსს არ ცვლის; ის მხოლოდ მცირე შეკეთებას ამატებს ყოველი ჩასმისა და წაშლის შემდეგ.

02ბრუნვა: შეკეთების ინსტრუმენტი

ყოველი დაბალანსებული ხე თავს ბრუნვებით (rotation) ისწორებს. მარჯვნივ ბრუნვა y-ზე იღებს მის მარცხენა შვილს x-ს და ზემოთ სწევს: x ხდება ამ ქვეხის სათავე, y ხდება x-ის მარჯვენა შვილი, x-ის ძველი მარჯვენა ქვეხე B კი y-ის მარცხენა ქვეხე ხდება. მარცხნივ ბრუნვა მისი სარკისებური ასახვაა.

იცვლება მხოლოდ სამი მიმთითებელი, ამიტომ ბრუნვა O(1) ღირს. და ის ძებნის ხის წესს არასდროს არღვევს: მანამდეც და მერეც INORDER მიმდევრობაა A, x, B, y, C. იცვლება მხოლოდ ფორმა: ერთი მხარე ერთი დონით მოკლდება, მეორე ერთით იზრდება.

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

იცვლება მხოლოდ x-ის, y-ის და B ქვეხის მშობლები.

03AVL და წითელ-შავი ხეები

ორი რეცეპტი დომინირებს:

AVL ხე: ყოველი წვერო თავის სიმაღლეს ინახავს და მისი ორი ქვეხის სიმაღლეები ერთმანეთისგან მაქსიმუმ 1-ით შეიძლება განსხვავდებოდეს. ჩასმის ან წაშლის შემდეგ ზემოთ ვბრუნდებით და სადაც სხვაობა 2 გახდება, ვაბრუნებთ. სიმაღლე დაახლოებით 1.44·log₂ n-ს არ აღემატება.
წითელ-შავი ხე: ყოველი წვერო წითელია ან შავი; წითელ წვეროს წითელი შვილი არასდროს ჰყავს, და სათავიდან ნებისმიერ NULL მიმთითებლამდე ყველა გზაზე შავი წვეროების რაოდენობა ერთნაირია. წესები უფრო თავისუფალია, ამიტომ ბრუნვა უფრო იშვიათად სჭირდება; სიმაღლე 2·log₂(n + 1)-ს არ აღემატება.

ხელით მათ იშვიათად წერენ. მთავარი გარანტიაა: ძებნა, ჩასმა და წაშლა O(log n)-ში ყველაზე ცუდ შემთხვევაშიც, პლუს ყველაფერი, რასაც ჩვეულებრივი ძებნის ხე გვაძლევს: დალაგებული შემოვლა, მინიმუმი, მაქსიმუმი, წინა და მომდევნო ელემენტი. Treap და splay ხეები მსგავს შეფასებებს შემთხვევითობით ან ამორტიზებული ანალიზით აღწევს.

04std::set და std::map პრაქტიკაში

C++-ში დაბალანსებული ხე მზად გვაქვს: std::set, std::map, std::multiset და std::multimap წითელ-შავი ხეებია. გამოიყენე ისინი, როცა გჭირდება დალაგებული კოლექცია, რომელიც მუდმივად იცვლება:

s.insert(x), s.erase(x), s.count(x): O(log n);
s.lower_bound(x): პირველი გასაღები, რომელიც ≥ x, ასევე O(log n): ზუსტად ნახაზზე ნაჩვენები სვლა;
*s.begin() და *s.rbegin() მინიმუმი და მაქსიმუმია; range-for ციკლი გასაღებებს დალაგებულად შემოივლის.

std::map<K, V> იგივე ხეა, სადაც ყოველ გასაღებს მნიშვნელობა ახლავს. თუ მხოლოდ იმას კითხულობ, „არის თუ არა x?“, და რიგი არ გჭირდება, std::unordered_set (ჰეშ-ცხრილი) საშუალოდ უფრო სწრაფია. ხე აირჩიე, როცა რიგი მნიშვნელოვანია: უახლოესი გასაღები, ყველაფერი შუალედში, უმცირესი თავისუფალი ადგილი. Java-ში იგივე როლს TreeSet და TreeMap ასრულებს; Python-ში ჩაშენებული ვარიანტი არ არის, ამიტომ დალაგებულ სიაზე bisect-ს ან sortedcontainers პაკეტს იყენებენ.

lower_bound(15) დაბალანსებულ ხეში სათავიდან ფოთლამდე ერთი სვლაა.

ფასი ერთი შეხედვით

ძებნა / ჩასმა / წაშლა (დაბალანსებული)O(log n)

lower_bound / upper_boundO(log n)

ერთი ბრუნვაO(1)

დალაგებული შემოვლაO(n)

დაიმახსოვრე

ჩვეულებრივი ძებნის ხის სიმაღლე ჩასმის რიგზეა დამოკიდებული; დალაგებული შემავალი მონაცემები მას O(n) ოპერაციებიან ჯაჭვად აქცევს.
ბრუნვა ქვეხის ფორმას O(1)-ში ცვლის ძებნის ხის რიგის დარღვევის გარეშე, დაბალანსებული ხეები კი მისი საშუალებით ინარჩუნებენ h = O(log n)-ს.
პრაქტიკაში, როცა დალაგებული და ცვალებადი კოლექცია გჭირდება, აიღე std::set / std::map (წითელ-შავი ხეები).

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: შეადარე ორი აგება: იგივე შვიდი გასაღები, 6 სიმაღლის ჯაჭვი და 2 სიმაღლის ხე. დაითვალე search(7)-ის შედარებები.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

გადაგვარებული BST (ჩასმა ზრდადობით) · სიმაღლე: 1 · search(7) შედარებები: 0

ჩავსვათ 1. რადგან გასაღებები ზრდადობით მოდის, თითო წინას მარჯვნივ ებმის და ხე სწორ ჯაჭვად იზრდება.

ფსევდოკოდი

 1 insert keys one by one into a BST 2   each key walks down to a leaf slot 3 search cost = number of nodes on the path = O(height) 4 balanced trees (AVL, red-black) rotate to keep height O(log n)

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

მარჯვნივ ბრუნვა y-ზე (მარცხენა შვილი x; ქვეხეები A და B x-ის ქვეშ, C y-ის ქვეშ). რომელი ქვეხე იცვლის მშობელს?

№2

რიცხვები უნდა დაამატო, წაშალო და ბევრჯერ უპასუხო კითხვას „უმცირესი რიცხვი, რომელიც ≥ q“. საუკეთესო ინსტრუმენტი?

№3

რომელ წესს ინარჩუნებს AVL ხე?

ივარჯიშე

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

LeetCodeBalanced Binary Tree დამწყები↗LeetCodeConvert Sorted Array to Binary Search Tree დამწყები↗CSESConcert Tickets საშუალო↗LeetCodeMy Calendar I საშუალო↗CSESTraffic Lights საშუალო↗