فرز الشجرة

خوارزمية فرز الشجرة هي خوارزمية فرز تبني شجرة بحث ثنائية من العناصر المراد فرزها، ثم تجتاز الشجرة ( بترتيب تصاعدي ) بحيث تظهر العناصر مرتبةً. ^{[ 1 ]} يُستخدم هذا النوع من الخوارزميات عادةً لفرز العناصر بشكل فوري : فبعد كل عملية إدخال، تكون مجموعة العناصر التي تمت رؤيتها حتى الآن متاحةً مرتبةً.

يمكن استخدام فرز الشجرة كفرز لمرة واحدة، ولكنه يُعادل الفرز السريع حيث يقوم كلاهما بتقسيم العناصر بشكل متكرر بناءً على عنصر محوري، ولأن الفرز السريع يتم في مكانه ويتميز بانخفاض الحمل الزائد، فإن فرز الشجرة لا يتمتع بمزايا تُذكر مقارنةً بالفرز السريع. يتميز فرز الشجرة بتعقيد أفضل في أسوأ الحالات عند استخدام شجرة متوازنة ذاتيًا، ولكنه يُحمّل النظام بحمل زائد أكبر.

إضافة عنصر واحد إلى شجرة بحث ثنائية تستغرق في المتوسط ​​O (log n ) (باستخدام ترميز Big O ). أما إضافة n عنصرًا فتستغرق O ( n log n ) ، مما يجعل فرز الشجرة عملية "فرز سريع". تتطلب إضافة عنصر إلى شجرة ثنائية غير متوازنة زمنًا قدره O ( n ) في أسوأ الحالات: عندما تشبه الشجرة قائمة مرتبطة ( شجرة متدهورة ). ينتج عن ذلك زمن أسوأ قدره O ( n² ) لخوارزمية الفرز هذه. تحدث هذه الحالة الأسوأ عندما تعمل الخوارزمية على مجموعة مرتبة مسبقًا، أو مجموعة شبه مرتبة، أو معكوسة، أو شبه معكوسة. مع ذلك، يمكن تحقيق زمن متوقع قدره O ( n log n ) عن طريق خلط المصفوفة، لكن هذا لا يُجدي نفعًا مع العناصر المتساوية.

يمكن تحسين أداء أسوأ الحالات باستخدام شجرة بحث ثنائية متوازنة ذاتيًا . باستخدام هذه الشجرة، يحقق الخوارزمية أداءً في أسوأ الحالات بزمن O ( n log n ) ، مما يجعلها مثالية من حيث درجة الترتيب في عملية الفرز المقارن . مع ذلك، تتطلب خوارزميات فرز الأشجار تخصيص ذاكرة منفصلة للشجرة، على عكس خوارزميات الفرز الموضعي مثل الفرز السريع أو فرز الكومة . في معظم المنصات الشائعة، يعني هذا ضرورة استخدام ذاكرة الكومة ، وهو ما يُؤثر سلبًا على الأداء بشكل ملحوظ مقارنةً بالفرز السريع وفرز الكومة . عند استخدام شجرة مائلة كشجرة بحث ثنائية، تتميز الخوارزمية الناتجة (المسماة فرز مائل ) بخاصية إضافية وهي أنها فرز تكيفي ، مما يعني أن زمن تشغيلها أسرع من O ( n log n ) للمدخلات شبه المرتبة.

تقبل خوارزمية فرز الشجرة التالية المكتوبة بلغة شبه رمزية مجموعة من العناصر القابلة للمقارنة وتُخرج العناصر بترتيب تصاعدي:

بنية BinaryTree BinaryTree : LeftSubTree Object : Node BinaryTree : RightSubTree إجراء Insert ( BinaryTree : searchTree , Object : item ) إذا كان searchTree . Node فارغًا، فقم بتعيين searchTree . Node إلى item ، وإلا إذا كان item أصغر من searchTree . Node ، فقم بإدراج ( searchTree . LeftSubTree , item ) ، وإلا فقم بإدراج ( searchTree . RightSubTree , item ) إجراء InOrder ( BinaryTree : searchTree ) إذا كان searchTree . Node فارغًا، فاخرج من الإجراء، وإلا فقم بإدراج ( searchTree . LeftSubTree ) وأصدر searchTree . إجراء فرز الشجرة ( المجموعة : العناصر ) الشجرة الثنائية : شجرة البحث لكل عنصر فردي في العناصر إدراج ( شجرة البحث ، العنصر الفردي ) بترتيب ( شجرة البحث )​

في شكل برمجة وظيفية بسيط ، ستبدو الخوارزمية (في لغة هاسكل ) على النحو التالي:

بيانات الشجرة أ = ورقة | عقدة ( الشجرة أ ) أ ( الشجرة أ )إدراج :: Ord a => a -> Tree a -> Tree a إدراج x ورقة = Node ورقة x ورقة إدراج x ( Node t y s ) | x <= y = Node ( إدراج x t ) y s | x > y = Node t y ( إدراج x s )تسطيح :: الشجرة أ -> [ أ ] تسطيح الورقة = [] تسطيح ( العقدة ت س س ) = تسطيح ت ++ [ س ] ++ تسطيح سفرز الأشجار :: Ord a => [ a ] ​​-> [ a ] ​​Treesort = flatten . مجلد إدراج ورقة

في التنفيذ المذكور أعلاه، فإن كل من خوارزمية الإدخال وخوارزمية الاسترجاع لديهما أسوأ سيناريوهات O ( n ²) .

• تطبيق جافا ثنائي الشجرة وشرحه على موقع Wayback Machine (تمت أرشفته في 29 نوفمبر 2016)
• ترتيب شجرة لقائمة مرتبطة في آلة Wayback Machine (تمت أرشفته في 10 أغسطس 2016)
• فرز الشجرة في لغة C++ على موقع Wayback Machine (تمت أرشفته في 21 يناير 2022)