RB-ხის დაბალანსების ალგორითმი

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

ჰიბრიდული მონაცემთა სტრუქტურა ძალიან მჭიდრო კავშირშია დაბალანსების არსებულ ალგორითმებთან. ჰიბრიდული RB-ხე ნიშნავს, რომ გარკვეულ შემთხვევებში, დროებით, ფერის ველს ვანიჭებთ სხვა დატვირთვას, რაც მოგვცემს იმ უნარებს, რაც არ გააჩნია RB-ხეს. თუმცა, კვანძის სტრუქტურა უცვლელი რჩება. RB-ხის ოპერაციები სრულდება გარანტირებულ ლოგარითმულ დროში, თუმცა ძებნის ოპერაციები შედარებით ნელია AVL ხესთან შედარებით. თუ პრაქტიკულ გამოყენებებსი იქნება სიტუაცია, როდესაც სრულდება კვანძების ჩამატება-წაშლების გრძელი სერია, შემდეგ ძებნის ოპერაციების გრძელი სერია, და ა.შ., მაშინ მიზანშეწონლილია ძებნის ოპერაციების სერიის წინ RB-ხე გარდავქმნათ AVL ხედ და აუცილებლობის შემთხვევაში განვახორციელოთ შებრუნებლი გარდაქმნა. AVL ხედ გარდაქმნა მოხდება საწყისი ხის inorder სტილში შემოვლით და კვანძების ზრდადი რიგით ამოღება RB-ხიდან და იგივე რიგით ჩამატება AVL -ხეში. ფაქტიურად, RB-ხის ხელახალი დაბალანსებისთვის დეის ალგორითმის გამოყენება თითქმის იგივეა რაც AVL ხედ გარდაქმნა (იმპლემენტაციის დეტალების სიზუსტით). ტექნიკურად არავითარი დაბრკოლება არ ჩნდება, რადგან პროგრამულად ყველაფერი კეთდება ერთი კლასის ფარგლებში, რომელსაც ემატება ერთი - რეჟიმის (mode) ველი. კვანძის სტრუქტურა უცვლელი რჩება. გვაქვს ორი fixup ჩამატებისთვის და ორიც წაშლისთვის- რეჟიმის მიხედვით. RB-ხე და AVL ხე მხოლოდ ამ fixup -ებიტ განსხვავდება ერთმანეთისგან. გვაქვს აგრეთვე მატი ერთმანეთში გადაყვანის ალგორითმები, რომელთაგან ერთი ნიშნავს RB-ხის ხელახალ დაბალანსებას დეის ალგორითმით.

მიმაგრებული ფაილები:

BalancingRBT [ka]