Logo hy.boatexistence.com

Ինչպե՞ս է աշխատում kd ծառը:

Բովանդակություն:

Ինչպե՞ս է աշխատում kd ծառը:
Ինչպե՞ս է աշխատում kd ծառը:

Video: Ինչպե՞ս է աշխատում kd ծառը:

Video: Ինչպե՞ս է աշխատում kd ծառը:
Video: Տավուշում կաճեցնեն Պավլովնիա ծառը 2024, Մայիս
Anonim

A K-D ծառը (որը նաև կոչվում է K-Dimensional Tree) երկուական որոնման ծառ է, որտեղ յուրաքանչյուր հանգույցի տվյալները K- Չափային կետ տարածության մեջ … Կետերը դեպի ձախ այս տարածությունը ներկայացված է այդ հանգույցի ձախ ենթածառով, իսկ տարածության աջ կողմի կետերը ներկայացված են աջ ենթածառով:

Արդյո՞ք KD Tree-ը ճշգրիտ է:

Տվյալների կետերը յուրաքանչյուր հանգույցում բաժանվում են երկու խմբի: Ինչպես նախորդ ալգորիթմը, KD Tree-ը նույնպես երկուական ծառի ալգորիթմ է, որը միշտ ավարտվում է առավելագույնը երկու հանգույցով… Ստորև նկարի աջ կողմում կարող եք տեսնել ստորև նշված պատկերի ճշգրիտ դիրքը: տվյալների կետեր, ձախ կողմում՝ դրանց տարածական դիրքը։

Ինչպե՞ս եք պատրաստում KD ծառ:

Շենք KD-Tree

  1. Առաջին տեղադրված կետը դառնում է ծառի արմատը:
  2. Ընտրեք առանցքը՝ հիմնվելով խորության վրա, որպեսզի առանցքը անցնի բոլոր վավեր արժեքների միջով: …
  3. Տեսակավորեք կետերի ցանկն ըստ առանցքի և որպես առանցքային տարր ընտրեք միջինը: …
  4. Անցեք ծառը մինչև հանգույցը դատարկվի, այնուհետև միավոր նշանակեք հանգույցին:
  5. Կրկնեք 2-4-րդ քայլը ռեկուրսիվ, մինչև բոլոր կետերը մշակվեն:

Ինչու ենք մենք օգտագործում kd ծառ:

KD-ծառերը հատուկ տվյալների կառուցվածք են մեր տվյալները արդյունավետ կերպով ներկայացնելու համար Մասնավորապես, KD-ծառերը օգնում են կազմակերպել և բաժանել տվյալների կետերը՝ հիմնված հատուկ պայմանների վրա: Այժմ մենք կկատարենք առանցքներով հավասարեցված հատումներ և կպահպանենք կետերի ցուցակները, որոնք ընկնում են այս տարբեր աղբարկղերից յուրաքանչյուրում:

Օկտրին ծառ է kd?

Յուրաքանչյուր տերևային հանգույցի տվյալները octree-ում կազմում են տեղական KD ծառը: Օկտրիում հանգույցները պահպանում են միայն սահմանափակող տուփի մասին իրենց տեղեկատվությունը: Յուրաքանչյուր տերևային հանգույցին տրվում է ինդեքսի արժեք՝ հետազոտության հարմարության համար:

Խորհուրդ ենք տալիս: