A K-D ծառը (որը նաև կոչվում է K-Dimensional Tree) երկուական որոնման ծառ է, որտեղ յուրաքանչյուր հանգույցի տվյալները K- Չափային կետ տարածության մեջ … Կետերը դեպի ձախ այս տարածությունը ներկայացված է այդ հանգույցի ձախ ենթածառով, իսկ տարածության աջ կողմի կետերը ներկայացված են աջ ենթածառով:
Արդյո՞ք KD Tree-ը ճշգրիտ է:
Տվյալների կետերը յուրաքանչյուր հանգույցում բաժանվում են երկու խմբի: Ինչպես նախորդ ալգորիթմը, KD Tree-ը նույնպես երկուական ծառի ալգորիթմ է, որը միշտ ավարտվում է առավելագույնը երկու հանգույցով… Ստորև նկարի աջ կողմում կարող եք տեսնել ստորև նշված պատկերի ճշգրիտ դիրքը: տվյալների կետեր, ձախ կողմում՝ դրանց տարածական դիրքը։
Ինչպե՞ս եք պատրաստում KD ծառ:
Շենք KD-Tree
- Առաջին տեղադրված կետը դառնում է ծառի արմատը:
- Ընտրեք առանցքը՝ հիմնվելով խորության վրա, որպեսզի առանցքը անցնի բոլոր վավեր արժեքների միջով: …
- Տեսակավորեք կետերի ցանկն ըստ առանցքի և որպես առանցքային տարր ընտրեք միջինը: …
- Անցեք ծառը մինչև հանգույցը դատարկվի, այնուհետև միավոր նշանակեք հանգույցին:
- Կրկնեք 2-4-րդ քայլը ռեկուրսիվ, մինչև բոլոր կետերը մշակվեն:
Ինչու ենք մենք օգտագործում kd ծառ:
KD-ծառերը հատուկ տվյալների կառուցվածք են մեր տվյալները արդյունավետ կերպով ներկայացնելու համար Մասնավորապես, KD-ծառերը օգնում են կազմակերպել և բաժանել տվյալների կետերը՝ հիմնված հատուկ պայմանների վրա: Այժմ մենք կկատարենք առանցքներով հավասարեցված հատումներ և կպահպանենք կետերի ցուցակները, որոնք ընկնում են այս տարբեր աղբարկղերից յուրաքանչյուրում:
Օկտրին ծառ է kd?
Յուրաքանչյուր տերևային հանգույցի տվյալները octree-ում կազմում են տեղական KD ծառը: Օկտրիում հանգույցները պահպանում են միայն սահմանափակող տուփի մասին իրենց տեղեկատվությունը: Յուրաքանչյուր տերևային հանգույցին տրվում է ինդեքսի արժեք՝ հետազոտության հարմարության համար:
