چاردرخت یک داده ساختار درختی است که در آن هر گره داخلی دقیقاً چهار فرزند دارد. این داده ساختار معمولاً برای افراز یک فضای دوبعدی به صورت بازگشتی به تعدادی ناحیه ( چارک ) استفاده می شود. این ناحیه ها ممکن است مربع، مستطیل یا به هر شکل دیگری باشند. در سال ۱۹۷۴، Raphael Finkel و J. L. Bentley این داده ساختار را quadtree نامیدند. چنین افرازی Q - tree نیز خوانده می شود. همۀ انواع چاردرخت، در تعدادی ویژگی مشترکند:
• فضا را به تعدادی ناحیه تقسیم می کنند.
• هر ناحیه ( یا سطل ) یک ظرفیت دارد. وقتی ظرفیت یک ناحیه پر شود، آن ناحیه تکه می شود.
چاردرخت ها را می توان بر اساس نوع داده ای که نمایش می دهند ( مثل سطح، نقطه، خط یا منحنی ) تقسیم بندی کرد. یک نحوۀ دیگر تقسیم بندی بر این اساس است که آیا شکل درخت ایجادشده مستقل از ترتیب پردازش داده ها است یا خیر. تعدادی از چاردرخت های متداول عبارتند از:
این نوع چاردرخت، نمایشگر افرازی از یک صفحۀ دوبعدی است که در آن افراز، صفحۀ دوبعدی به چهار ناحیۀ برابر افراز شده و برخی ناحیه ها خود به چهار زیرناحیۀ برابر افراز شده اند و به همین ترتیب فرایند افراز می تواند ادامه پیدا کند. در چنین افرازی، هر گره، یا چهار فرزند دارد یا فرزندی ندارد ( برگ است ) . هر برگ از درخت مربوط به یکی از زیر ناحیه های افراز است و اطلاعات آن زیرناحیه در آن برگ ذخیره می شود. چاردرخت ناحیه ای یک نوع ترای است.
می توان از یک چاردرخت ناحیه ای با ارتفاع n برای نمایش یک تصویر با ابعاد 2n × 2n پیکسل ( که مقدار هر پیکسل ۰ یا ۱ است ) استفاده کرد. ریشۀ درخت، نمایشگر کل تصویر است. هر ناحیه ای که مقدار همۀ پیکسل هایش با هم برابر نیست، به ۴ زیرناحیه تقسیم می شود. در نهایت هر برگ از درخت، مجموعه ای مربع شکل از تعدادی پیکسل را نشان می دهد که همگی ۰ یا همگی ۱ هستند.
اگر چاردرخت ناحیه ای برای نمایش مجموعه ای از نقاط ( مثلاً تعدادی شهر که با طول و عرض جغرافیایی مشخص شده اند ) استفاده شود، ناحیه ها تا جایی تقسیم می شوند که هر زیرناحیه حداکثر یک نقطه را شامل شود.
چاردرخت نقطه ای تعمیمی از درخت دودویی است. از یک درخت دودویی می توان برای ذخیره تعدادی عدد ( از فضای یک بعدی ) استفاده کرد. ولی از چاردرخت نقطه ای می توان برای ذخیره تعدادی نقطه ( دوتایی مرتب ) از فضای دوبعدی استفاده کرد. این درخت، همۀ ویژگی های چاردرخت را دارد و یک درخت واقعی است. یعنی گره های درخت، خود نقاطی هستند که می خواهیم نمایش دهیم ( برخلاف چاردرخت ناحیه ای، وقتی که برای نمایش تعدادی نقطه مورد استفاده قرار بگیرد ) . شکل ناحیه های ایجاد شده به ترتیب اضافه کردن نقاط بستگی دارد ( درست مثل درخت دودویی جستجو ) . چاردرخت نقطه ای، معمولاً برای مقایسه بین مجموعه ای از نقاط در صفحۀ دوبعدی بسیار بهینه ( معمولاً از O ( log n ) ) عمل می کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف• فضا را به تعدادی ناحیه تقسیم می کنند.
• هر ناحیه ( یا سطل ) یک ظرفیت دارد. وقتی ظرفیت یک ناحیه پر شود، آن ناحیه تکه می شود.
چاردرخت ها را می توان بر اساس نوع داده ای که نمایش می دهند ( مثل سطح، نقطه، خط یا منحنی ) تقسیم بندی کرد. یک نحوۀ دیگر تقسیم بندی بر این اساس است که آیا شکل درخت ایجادشده مستقل از ترتیب پردازش داده ها است یا خیر. تعدادی از چاردرخت های متداول عبارتند از:
این نوع چاردرخت، نمایشگر افرازی از یک صفحۀ دوبعدی است که در آن افراز، صفحۀ دوبعدی به چهار ناحیۀ برابر افراز شده و برخی ناحیه ها خود به چهار زیرناحیۀ برابر افراز شده اند و به همین ترتیب فرایند افراز می تواند ادامه پیدا کند. در چنین افرازی، هر گره، یا چهار فرزند دارد یا فرزندی ندارد ( برگ است ) . هر برگ از درخت مربوط به یکی از زیر ناحیه های افراز است و اطلاعات آن زیرناحیه در آن برگ ذخیره می شود. چاردرخت ناحیه ای یک نوع ترای است.
می توان از یک چاردرخت ناحیه ای با ارتفاع n برای نمایش یک تصویر با ابعاد 2n × 2n پیکسل ( که مقدار هر پیکسل ۰ یا ۱ است ) استفاده کرد. ریشۀ درخت، نمایشگر کل تصویر است. هر ناحیه ای که مقدار همۀ پیکسل هایش با هم برابر نیست، به ۴ زیرناحیه تقسیم می شود. در نهایت هر برگ از درخت، مجموعه ای مربع شکل از تعدادی پیکسل را نشان می دهد که همگی ۰ یا همگی ۱ هستند.
اگر چاردرخت ناحیه ای برای نمایش مجموعه ای از نقاط ( مثلاً تعدادی شهر که با طول و عرض جغرافیایی مشخص شده اند ) استفاده شود، ناحیه ها تا جایی تقسیم می شوند که هر زیرناحیه حداکثر یک نقطه را شامل شود.
چاردرخت نقطه ای تعمیمی از درخت دودویی است. از یک درخت دودویی می توان برای ذخیره تعدادی عدد ( از فضای یک بعدی ) استفاده کرد. ولی از چاردرخت نقطه ای می توان برای ذخیره تعدادی نقطه ( دوتایی مرتب ) از فضای دوبعدی استفاده کرد. این درخت، همۀ ویژگی های چاردرخت را دارد و یک درخت واقعی است. یعنی گره های درخت، خود نقاطی هستند که می خواهیم نمایش دهیم ( برخلاف چاردرخت ناحیه ای، وقتی که برای نمایش تعدادی نقطه مورد استفاده قرار بگیرد ) . شکل ناحیه های ایجاد شده به ترتیب اضافه کردن نقاط بستگی دارد ( درست مثل درخت دودویی جستجو ) . چاردرخت نقطه ای، معمولاً برای مقایسه بین مجموعه ای از نقاط در صفحۀ دوبعدی بسیار بهینه ( معمولاً از O ( log n ) ) عمل می کند.
wiki: چاردرخت