რვაობითი ხე არის ისეთი ხე, რომლის თითოეულ შიდა კვანძს ჰყავს მაქსიმუმ 8 შვილობილი კვანძი, რომლებიც მიიღება მშობელი კვანძის შესაბამისი შემომსაზღვრელი ყუთის, x, y და z ღერძების მიმართ,
სივრცულად შუაზე გაყოფის შედეგად. რვაობითი ხის აგება შეგვიძლია რამოდენიმე გზით, ერთ-ერთი ასეთი გზა ხის აგებას ახდენს ზემოდან ქვემოთ, რაც იმას გულისხმობს, რომ პირველ ეტაპზე, როდესაც მოცემული გვაქვს პრიმიტივების სია, ვახდენთ შემომსაზღვრელი ყუთის დადგენას და ვქმნით ხის ძირს, რომელშიც ვათავსებთ ყველა პრიმიტივს. ამის შემდგომ შევდივართ კვანძში, ვქმნით მის შვილობილ 8 კვანძს, საკოორდინატო ღერძების მიმართ, სივრცულად, შუაზე გაყოფის გზით და პრიმიტივებს ვანაწილებთ შვილობილ კვანძებში. შემდგომ ისევ ჩავდივართ თითოეულ კვანძში და ამ პროცესს ვიმეორებთ რეკურსიულად, სანამ არ ავაგებთ სასურველ ხეს. როგორც ზემოთ აღინიშნა, პრიმიტივების შვილობილ კვანძებში გადანაწილების დროს ერთი პრიმიტივი შესაძლოა მოხვდეს რამოდენიმე შვილში ერთდროულად, ასევე შესაძლოა ზოგიერთ შვილში არცერთი პრიმიტივი არ მოხვდეს. ასეთ დროს ხის აგება ამ მიმართულებით აღარ გრძელდება. სწორედ სივრცულად დაყოფის გამო, რვაობითი ხე არის არაბალანსირებული
აქვე უნდა აღინიშნოს, რომ რვაობით ხეში შვილობილი კვანძების შესაბამისი შემომსაზღვრელი ყუთები არაა მინიმალური და შესაბამისად მასში არსებულ პრიმიტივებს მჭიდროდ არ ეკვრის, რაც მასზე სხივის მოხვედრის ალბათობას ზრდის. ეს საბოლოოდ დამატებით, ტყუილ(ტყუილი შემოწმებას ვეძახით ისეთ შემოწმებას როდესაც სხივი ხვდება შემომსაზღვრელ ფიგურას, უმცა სცდება პრიმიტივს) შემოწმებებს იწვევს, რაც ერთისმხრიც ავმირებს მის ეფექტურობას, თუმცა იმის გამო, რომ კვანძების მდებარეობა სივრცეში წინასწარ განსაზღვრულია მისი მეხსიერებაში შენახვა შემომსაზღვრელი ყუთების სახით არაა აუცილებელი. ამ ინფორმაციის აღდგენა მარტივად შეიძლება ძებნის პროცესში, როდესაც ჩავდივართ სიღრმეში, მშობელი კვანძიდან შვილობილი კვანძების მიმართულებით.
Comments
Post a Comment