در علوم کامپیوتر، از ساختمان دادهٔ درخت بازه ها∗ برای ذخیره کردن بازه ها استفاده می شود. این ساختمان داده امکان یافتن بازهٔ مربوط به یک نقطهٔ داده شده را فراهم می کند. می توان هر گره از درخت در با پیچیدگی زمانی ( o ( log n تغییر داد.
درخت ها قسمت بزرگی از داده ساختارهای علم کامپیوتر را پوشش می دهند. درخت در حالت کلی به گراف هم بندی گفته می شود که دور ندارد.
درخت ریشه دار درختی است، که در آن بین رأس ها رابطهٔ پدر و فرزندی وجود دارد ( ساختاری شبیه شجره نامه دارد ) .
درخت بازه ها، درختی ریشه دار است که هر رأس غیر برگ∗ آن دقیقاً دو فرزند دارد. در این درخت هر رأس نشان دهندهٔ یک بازه است. برگ ها در این درخت نشان دهندهٔ بازه هایی به طول یک هستند. رئوس غیر برگ همگی دو فرزند دارند؛ اگر بازهٔ نسبت داده شده به فرزندان چپ و راست به ترتیب [ a , b ) و [ b , c ) باشد، بازهٔ این رأس [ a , c ) است. طول بازهٔ نسبت داده شده به هر رأس توانی از ۲ است ( در صورتی که تعداد برگ ها توانی از ۲ باشد ) . در نتیجه اگر رأسی نشان دهندهٔ بازهٔ [ p , q ) باشد؛ فرزند سمت چپ نشان دهندهٔ بازهٔ [ p , ( p + q ) / 2 ) و فرزند راست نشان دهندهٔ بازهٔ [ ( p + q ) / 2 , q ) است. این درخت اغلب در مورد سؤال هایی به کار می رود که عملیاتی روی بازه ها انجام می شود یا در هر مرحله به ما دستوری می دهند و باید تصمیم درست را در هر مرحله بگیریم.
اردر همهٔ کارها در این داده ساختار ( l o g ( n است که n طول بازه ای است که ریشه نشان می دهد. چرا که اگر در حال جستجوی بازهٔ [ p , q ) ، در رأس x باشیم ( x نمایندهٔ بازهٔ [ P , Q ) است ) ؛
m i d = ( P + Q ) / 2
۱ - اگر p برابر P و q برابر Q باشد بازه پیدا شده و عمل مورد نظر را انجام بده ( پایان جستجو ) .
۲ - اگر بازهٔ مورد نظر با هر دو فرزند تداخل داشت: به دنبال [ p , m i d ) در [ P , m i d ) و [ m i d , q ) در [ m i d , Q ) بگرد.
۳ - اگر بازهٔ مورد نظر فقط با یکی از فرزندان تداخل داشت: به دنبال [ p , q ) در فرزند مذکور بگرد.
به نظر می رسد ممکن است حالت دوم تکرار شود و تمام رئوس را پیمایش کنیم، در صورتی که به سادگی می توان دریافت اگر یک بار حالت دوم رخ دهد ( هر دو فرزند را پیمایش کنیم ) آنگاه در هیچ مرحلهٔ دیگری لازم نیست هر دو انتهای بازه را بررسی کنیم. چرا که از یک طرف بازهٔ ما به ابتدا یا انتها چسبیده و اگر دو قسمت را بررسی کنیم یکی از دو قسمت درجا به شرط پایان می رسد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدرخت ها قسمت بزرگی از داده ساختارهای علم کامپیوتر را پوشش می دهند. درخت در حالت کلی به گراف هم بندی گفته می شود که دور ندارد.
درخت ریشه دار درختی است، که در آن بین رأس ها رابطهٔ پدر و فرزندی وجود دارد ( ساختاری شبیه شجره نامه دارد ) .
درخت بازه ها، درختی ریشه دار است که هر رأس غیر برگ∗ آن دقیقاً دو فرزند دارد. در این درخت هر رأس نشان دهندهٔ یک بازه است. برگ ها در این درخت نشان دهندهٔ بازه هایی به طول یک هستند. رئوس غیر برگ همگی دو فرزند دارند؛ اگر بازهٔ نسبت داده شده به فرزندان چپ و راست به ترتیب [ a , b ) و [ b , c ) باشد، بازهٔ این رأس [ a , c ) است. طول بازهٔ نسبت داده شده به هر رأس توانی از ۲ است ( در صورتی که تعداد برگ ها توانی از ۲ باشد ) . در نتیجه اگر رأسی نشان دهندهٔ بازهٔ [ p , q ) باشد؛ فرزند سمت چپ نشان دهندهٔ بازهٔ [ p , ( p + q ) / 2 ) و فرزند راست نشان دهندهٔ بازهٔ [ ( p + q ) / 2 , q ) است. این درخت اغلب در مورد سؤال هایی به کار می رود که عملیاتی روی بازه ها انجام می شود یا در هر مرحله به ما دستوری می دهند و باید تصمیم درست را در هر مرحله بگیریم.
اردر همهٔ کارها در این داده ساختار ( l o g ( n است که n طول بازه ای است که ریشه نشان می دهد. چرا که اگر در حال جستجوی بازهٔ [ p , q ) ، در رأس x باشیم ( x نمایندهٔ بازهٔ [ P , Q ) است ) ؛
m i d = ( P + Q ) / 2
۱ - اگر p برابر P و q برابر Q باشد بازه پیدا شده و عمل مورد نظر را انجام بده ( پایان جستجو ) .
۲ - اگر بازهٔ مورد نظر با هر دو فرزند تداخل داشت: به دنبال [ p , m i d ) در [ P , m i d ) و [ m i d , q ) در [ m i d , Q ) بگرد.
۳ - اگر بازهٔ مورد نظر فقط با یکی از فرزندان تداخل داشت: به دنبال [ p , q ) در فرزند مذکور بگرد.
به نظر می رسد ممکن است حالت دوم تکرار شود و تمام رئوس را پیمایش کنیم، در صورتی که به سادگی می توان دریافت اگر یک بار حالت دوم رخ دهد ( هر دو فرزند را پیمایش کنیم ) آنگاه در هیچ مرحلهٔ دیگری لازم نیست هر دو انتهای بازه را بررسی کنیم. چرا که از یک طرف بازهٔ ما به ابتدا یا انتها چسبیده و اگر دو قسمت را بررسی کنیم یکی از دو قسمت درجا به شرط پایان می رسد.
wiki: درخت بازه ها