K-D ხე (ასევე უწოდებენ K-განზომილებიანი ხე) არის ორობითი საძიებო ხე, სადაც მონაცემები თითოეულ კვანძში არის K- განზომილებიანი წერტილი სივრცეში … წერტილები მარცხნივ ამ სივრცის წარმოდგენილია ამ კვანძის მარცხენა ქვეხე და სივრცის მარჯვნივ წერტილები წარმოდგენილია მარჯვენა ქვეხის მიერ.
KD ხე ზუსტია?
მონაცემთა წერტილები იყოფა თითოეულ კვანძში ორ ნაწილად. წინა ალგორითმის მსგავსად, KD ხე ასევე არის ორობითი ხის ალგორითმი, რომელიც ყოველთვის მთავრდება მაქსიმუმ ორი კვანძით… ქვემოთ მოცემული სურათის მარჯვენა მხარეს შეგიძლიათ იხილოთ ზუსტი პოზიცია. მონაცემთა წერტილები, მარცხენა მხარეს მათი სივრცითი მდებარეობა.
როგორ ამზადებ KD ხეს?
შენება KD-Tree
- პირველი ჩასმული წერტილი ხდება ხის ფესვი.
- აირჩიეთ ღერძი სიღრმის მიხედვით ისე, რომ ღერძი შემოიფარგლოს ყველა მოქმედ მნიშვნელობაზე. …
- დაალაგეთ წერტილების სია ღერძების მიხედვით და აირჩიეთ მედიანა, როგორც საყრდენი ელემენტი. …
- გაიარეთ ხე, სანამ კვანძი არ დაცარიელდება, შემდეგ მიანიჭეთ წერტილი კვანძს.
- გაიმეორეთ ნაბიჯი 2-4 რეკურსიულად, სანამ ყველა ქულა არ დამუშავდება.
რატომ ვიყენებთ kd ხე?
KD-ხეები არის სპეციფიკური მონაცემთა სტრუქტურა ჩვენი მონაცემების ეფექტურად წარმოსადგენად კერძოდ, KD-ხეები ეხმარება მონაცემთა წერტილების ორგანიზებასა და დაყოფას კონკრეტულ პირობებზე დაყრდნობით. ახლა ჩვენ ვაპირებთ გავაკეთოთ ღერძებზე გასწორებული ჭრილები და შევინარჩუნოთ წერტილების სიები, რომლებიც ხვდება თითოეულ ამ სხვადასხვა ურნაში.
არის octree ხე kd?
მონაცემები თითოეული ფოთლის კვანძის ოქტში შეადგენს ადგილობრივ KD ხეს. octree-ში, კვანძები ინახავს მხოლოდ ინფორმაციას შეზღუდვის შესახებ. თითოეული ფოთლის კვანძს ენიჭება ინდექსის მნიშვნელობა კვლევის მოხერხებულობისთვის.
