مرتب سازی درختی یک الگوریتم مرتب سازی می باشد که یک درخت جستجوی دودویی از کلیدهایی که باید مرتب شوند می سازد و آنگاه با پیمایش میان ترتیب درخت کلیدهای مرتب شده را به دست می آوریم.
معمولاً هنگامی از مرتب سازی درختی استفاده می شود که هدف مرتب سازی یک رشته ورودی از یک فایل باشد. در اغلب الگوریتم های مرتب سازی داده ها باید در یک ساختمان داده موقت ذخیره شوند و سپس عملیات مرتب سازی بر روی آن انجام شود. درحالی که در مرتب سازی درختی بارگذاری یک عنصر در ساختمان داده بر مرتب سازی آن است.
درج یک عنصر در یک درخت جستجوی دودویی به طور میانگین از مرتبه ( ( O ( log ( n است. [ ۱] بنابراین ساخت یک درخت جستجوی دودویی با n عضو از مرتبه ( ( O ( n log ( n می باشد که یک درخت جستجو می سازدو همچنین یک مرتب سازی بهینه است.
اضافه کردن ک عنصر جدید به یک درخت جستجوی دودویی از ( O ( n زمان می برد. یعنی هنگامی که درخت شبیه به یک لیست پیوندی ساده می شود باعث می شود که در بدترین حالت این الگوریتم از مرتبه ( O ( n۲ زمان می برد. البته با استفاده از گسترش هایی از درخت دودویی جستجو می توان رفتار بدترین حالت را بهبود داد و در بدترین حالت هم از ( ( O ( n log ( n باشد. پس مرتب سازی درختی به لحاظ تئوری هم بهینه است.
غالب پردازش در یک مرتب سازی درختی درج در درخت دودویی است با فرض اینکه زمان بازیابی اطلاعات ( O ( n باشد.
در زیر تکه برنامه سی پلاس پلاس را آورده ایم. multiset کلاسی در سی پلاس پلاس می باشد که در حقیقت یک درخت جستجوی دودویی خاص می باشد که این امکان را فراهم می سازد که در بدترین حالت هم درج بهینه در این داده ساختار از ( ( O ( log ( n داشته باشیم.
#include < set> // for multiset #include < algorithm> // for copy #include < iterator> // for iterator_traits template < typename Iterator> void binary_tree_sort ( Iterator begin, Iterator end ) { // C++' s multiset class is a self - balancing binary search tree that allows duplicates // Add each element in input range to the tree std::multiset< typename std::iterator_traits< Iterator> ::value_type> tree ( begin, end ) ; // Read elements in ascending order by simply traversing the tree. std::copy ( tree. begin ( ) , tree. end ( ) , begin ) ; } پانویس ↑ داده ساختارها و مبانی الگوریتم ها - محمد قدسی - ۱۳۸۸ ص۲۲۱ منابع قدسی، محمد. داده ساختارها و مبانی الگوریتم ها. موسسه فرهنگی فاطمی: نشر، ۱۳۸۸. کتاب CLRS مشارکت کنندگان ویکی پدیا. «Tree Sort». در دانشنامهٔ ویکی پدیای انگلیسی، بازبینی شده در ۴ آوریل ۲۰۱۰. http://www. google. com/url?sa=t& source=web& ct=res& cd=10& ved=0CDUQFjAJ& url=http://www. cs. sjsu. edu/~lee/cs146/24SpL8binarytree2. ppt& ei=h2rgS6atMYP48AaMnaSlBw& usg=AFQjCNG7QyTODSQHwsEagIMXQYTduDkyoQ
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمعمولاً هنگامی از مرتب سازی درختی استفاده می شود که هدف مرتب سازی یک رشته ورودی از یک فایل باشد. در اغلب الگوریتم های مرتب سازی داده ها باید در یک ساختمان داده موقت ذخیره شوند و سپس عملیات مرتب سازی بر روی آن انجام شود. درحالی که در مرتب سازی درختی بارگذاری یک عنصر در ساختمان داده بر مرتب سازی آن است.
درج یک عنصر در یک درخت جستجوی دودویی به طور میانگین از مرتبه ( ( O ( log ( n است. [ ۱] بنابراین ساخت یک درخت جستجوی دودویی با n عضو از مرتبه ( ( O ( n log ( n می باشد که یک درخت جستجو می سازدو همچنین یک مرتب سازی بهینه است.
اضافه کردن ک عنصر جدید به یک درخت جستجوی دودویی از ( O ( n زمان می برد. یعنی هنگامی که درخت شبیه به یک لیست پیوندی ساده می شود باعث می شود که در بدترین حالت این الگوریتم از مرتبه ( O ( n۲ زمان می برد. البته با استفاده از گسترش هایی از درخت دودویی جستجو می توان رفتار بدترین حالت را بهبود داد و در بدترین حالت هم از ( ( O ( n log ( n باشد. پس مرتب سازی درختی به لحاظ تئوری هم بهینه است.
غالب پردازش در یک مرتب سازی درختی درج در درخت دودویی است با فرض اینکه زمان بازیابی اطلاعات ( O ( n باشد.
در زیر تکه برنامه سی پلاس پلاس را آورده ایم. multiset کلاسی در سی پلاس پلاس می باشد که در حقیقت یک درخت جستجوی دودویی خاص می باشد که این امکان را فراهم می سازد که در بدترین حالت هم درج بهینه در این داده ساختار از ( ( O ( log ( n داشته باشیم.
#include < set> // for multiset #include < algorithm> // for copy #include < iterator> // for iterator_traits template < typename Iterator> void binary_tree_sort ( Iterator begin, Iterator end ) { // C++' s multiset class is a self - balancing binary search tree that allows duplicates // Add each element in input range to the tree std::multiset< typename std::iterator_traits< Iterator> ::value_type> tree ( begin, end ) ; // Read elements in ascending order by simply traversing the tree. std::copy ( tree. begin ( ) , tree. end ( ) , begin ) ; } پانویس ↑ داده ساختارها و مبانی الگوریتم ها - محمد قدسی - ۱۳۸۸ ص۲۲۱ منابع قدسی، محمد. داده ساختارها و مبانی الگوریتم ها. موسسه فرهنگی فاطمی: نشر، ۱۳۸۸. کتاب CLRS مشارکت کنندگان ویکی پدیا. «Tree Sort». در دانشنامهٔ ویکی پدیای انگلیسی، بازبینی شده در ۴ آوریل ۲۰۱۰. http://www. google. com/url?sa=t& source=web& ct=res& cd=10& ved=0CDUQFjAJ& url=http://www. cs. sjsu. edu/~lee/cs146/24SpL8binarytree2. ppt& ei=h2rgS6atMYP48AaMnaSlBw& usg=AFQjCNG7QyTODSQHwsEagIMXQYTduDkyoQ
wiki: مرتب سازی درختی