![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/langfa-640px-Point_quadtree.svg.png&w=640&q=50)
چاردرخت
From Wikipedia, the free encyclopedia
چاردرخت یک داده ساختار درختی است که در آن هر گره داخلی دقیقاً چهار فرزند دارد. این دادهساختار معمولاً برای افراز یک فضای دوبعدی به صورت بازگشتی به تعدادی ناحیه (چارک) استفاده میشود. این ناحیهها ممکن است مربع، مستطیل یا به هر شکل دیگری باشند. در سال ۱۹۷۴، Raphael Finkel و J.L. Bentley این دادهساختار را quadtree نامیدند. چنین افرازی Q-tree نیز خوانده میشود. همۀ انواع چاردرخت، در تعدادی ویژگی مشترکند:
- فضا را به تعدادی ناحیه تقسیم میکنند.
- هر ناحیه (یا سطل) یک ظرفیت دارد. وقتی ظرفیت یک ناحیه پر شود، آن ناحیه تکه میشود.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/320px-Point_quadtree.svg.png)