شجرة m -ary

في نظرية المخططات ، تُعرف الشجرة من الرتبة m (حيث m عدد صحيح غير سالب ) (وتُعرف أيضًا بالشجرة من الرتبة n أو k أو k - way أو الشجرة العامة ) بأنها شجرة متفرعة (أو، كما يسميها بعض الباحثين، شجرة مرتبة ) ^{[ 1 ] [ 2 ]} لا يزيد عدد الأبناء في كل عقدة فيها عن m . تُعد الشجرة الثنائية حالة مهمة حيث m = 2؛ وبالمثل، تُعد الشجرة الثلاثية حالة حيث m = 3. 

• الشجرة الكاملة من الرتبة m هي شجرة من الرتبة m حيث تحتوي كل عقدة في كل مستوى على 0 أو m من الأبناء.
• الشجرة الكاملة من النوع m ^{[ 3 ] [ 4 ]} (أو، بشكل أقل شيوعًا، الشجرة المثالية من النوع m ^{[ 5 ]} ) هي شجرة كاملة من النوع m تكون فيها جميع العقد الورقية على نفس العمق.

• بالنسبة لشجرة من الرتبة m ذات ارتفاع h ، فإن الحد الأعلى لأقصى عدد من الأوراق هو${\displaystyle m^{h}}$.
• لا يشمل ارتفاع الشجرة m - ary العقدة الجذرية، حيث أن الشجرة التي تحتوي على عقدة جذرية فقط يكون ارتفاعها  0.
• ارتفاع الشجرة يساوي أقصى عمق D لأي عقدة في الشجرة.
• إجمالي عدد العقد${\displaystyle N}$في شجرة كاملة من الرتبة m يكون${\textstyle \sum _{i=0}^{h}m^{i}={\frac {m^{h+1}-1}{m-1}}}$بينما الارتفاع h هو

$$\begin{aligned} \begin{aligned} \frac{m^{h+1}-1}{m-1} \geq N > \frac{m^{h}-1}{m-1} \begin{aligned ...$$بحسب تعريف Big-Ω، فإن أقصى عمق $${\displaystyle D=h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m).}$$

• ارتفاع شجرة كاملة من الرتبة m ذات n عقدة هو${\textstyle \lfloor \log _{m}((m-1)\cdot n)\rfloor }$.
• العدد الإجمالي للأشجار الممكنة من الرتبة m ذات n عقدة هو${\textstyle C_{n}={\frac {1}{(m-1)n+1}}\cdot {\binom {m\cdot n}{n}}}$ (وهو رقم كاتالوني ). ^{[ 6 ]}

يُشبه اجتياز شجرة من الرتبة m اجتياز شجرة ثنائية. في الترتيب المسبق، ينتقل الاجتياز إلى العقدة الأب، ثم الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى. أما في الترتيب اللاحق، فينتقل الاجتياز إلى الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى، ثم العقدة الأب. وللاجتياز بالترتيب الداخلي، ولأن عدد الأبناء لكل عقدة يزيد عن اثنين (حيث m > 2) ، يجب تحديد مفهومي الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى . إحدى الطرق الشائعة لإنشاء الشجرتين الفرعيتين هي تقسيم قائمة العقد الأبناء إلى مجموعتين. بتحديد ترتيب للأبناء m لعقدة ما، فإن أولًا ${\textstyle \{1,\dots ,\lfloor {\frac {m}{2}}\rfloor \}}$ستشكل العقد الشجرة الفرعية اليسرى و${\textstyle \{\lceil {\frac {m}{2}}\rceil ,\dots ,m\}}$ستشكل العقد الشجرة الفرعية اليمنى.

يُعدّ استخدام المصفوفة لتمثيل شجرة متعددة الفروع غير فعال، لأن معظم العقد في التطبيقات العملية تحتوي على أقل من m فرع. ونتيجةً لذلك، ينتج عن هذه الحقيقة مصفوفة متفرقة ذات مساحة كبيرة غير مستخدمة في الذاكرة. إن تحويل أي شجرة متعددة الفروع إلى شجرة ثنائية لن يؤدي إلا إلى زيادة ارتفاع الشجرة بمعامل ثابت، ولن يؤثر على تعقيد الوقت الإجمالي في أسوأ الحالات. بعبارة أخرى،${\textstyle O(\log _{m}n)\equiv O(\log _{2}n)}$منذ${\textstyle \log _{2}m\cdot \log _{m}n={\frac {\log m}{\log 2}}\cdot {\frac {\log n}{\log m}}=\log _{2}n}$.

أولًا، نربط جميع العقد الفرعية المباشرة لعقدة أب معينة معًا لتكوين قائمة روابط. ثم نحتفظ بالرابط من الأب إلى الابن الأول (أي الأيسر) ونزيل جميع الروابط الأخرى إلى بقية الأبناء. نكرر هذه العملية لجميع الأبناء (إن وجدوا) حتى ننتهي من معالجة جميع العقد الداخلية وندير الشجرة 45 درجة باتجاه عقارب الساعة. الشجرة الناتجة هي الشجرة الثنائية المطلوبة المستخرجة من الشجرة m -ary المعطاة.

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

تكمن مشكلة هذا التمثيل في أن سرد جميع سلاسل البتات بترتيب معجمي يعني أن سلسلتين متتاليتين قد تمثلان شجرتين مختلفتين معجميًا بشكل كبير. لذلك، فإن تعداد السلاسل الثنائية لا يؤدي بالضرورة إلى توليد مرتب لجميع الأشجار متعددة الحدود. ^{[ 7 ]} يعتمد التمثيل الأفضل على سلسلة أعداد صحيحة تشير إلى عدد الأصفار بين كل واحد متتالٍ، والمعروفة باسم متتالية الأصفار البسيطة .${\textstyle S=s_{1},s_{2},\dots ,s_{n-1}}$هو تسلسل أصفار بسيط يتوافق مع تسلسل البتات${\textstyle 10^{s_{1}}10^{s_{2}}\ldots 10^{s_{n-1}}10^{j}}$حيث يمثل j عدد الأصفار اللازمة في نهاية التسلسل لجعل السلسلة ذات الطول المناسب. على سبيل المثال،${\displaystyle 1110000100010001000\equiv 10^{0}10^{0}10^{4}10^{4}10^{3}\equiv 00433}$يمثل الشكل أعلاه تمثيلاً بسيطاً لتسلسل الأصفار. أما التمثيل الأكثر اختصاراً للرقم 00433 فهو${\displaystyle 0^{2}4^{1}3^{2}}$وهذا ما يُسمى بالتسلسل الصفري ، حيث لا يمكن أن تكون القواعد المكررة متجاورة. يسمح هذا التمثيل الجديد بإنشاء تسلسل صالح تالٍ في${\displaystyle O(1)}$تكون متتالية الأصفار البسيطة صالحة إذا $${\displaystyle \sum _{i=1}^{i=j}s_{i}\leq (m-1)j\qquad \forall j\leq n-1.}$$بمعنى آخر، لا يمكن أن يتجاوز عدد الأصفار في تسلسل البتات لشجرة من الرتبة m العدد الإجمالي للمؤشرات الفارغة (أي المؤشرات التي لا ترتبط بها أي عقدة فرعية). هذا الجمع يفرض قيدًا على${\displaystyle n-1}$العقد بحيث يكون هناك مجال لإضافة${\displaystyle n^{t}h}$دون إنشاء بنية غير صالحة (أي وجود مؤشر فارغ متاح لربط العقدة الأخيرة به).

يوضح الجدول أدناه قائمة بجميع متواليات الصفر البسيطة الصالحة لجميع الأشجار الثلاثية ذات 4 عقد:

ابتداءً من أسفل يمين الجدول (أي "000")، يوجد قالب أساسي يتحكم في إنشاء الأشجار المرتبة الممكنة بدءًا من "000" إلى "006". يظهر أدناه القالب الأساسي لهذه المجموعة ("00X")، حيث تمت إضافة عقدة إضافية في المواضع المُشار إليها بـ "x".

بمجرد استنفاد جميع المواضع الممكنة في قالب العمود الفقري، سيتم إنشاء قالب جديد عن طريق تحريك العقدة الثالثة موضعًا واحدًا إلى اليمين كما هو موضح أدناه، وسيحدث نفس التعداد حتى يتم استنفاد جميع المواضع الممكنة التي تحمل علامة "X".

بالعودة إلى جدول تعداد جميع الأشجار من الرتبة m ، حيث${\displaystyle m=3}$و${\displaystyle n=4}$يمكننا بسهولة ملاحظة القفزة الواضحة من "006" إلى "010" والتي يمكن تفسيرها بشكل بسيط بطريقة حسابية كما هو موضح أدناه:

يُعطى أدناه الكود الزائف لهذا التعداد: ^{[ 7 ]}

الإجراء NEXT( s1 , s2 , …, sn - 1 ) إذا كان si = 0 لجميع قيم i ، فإن انتهى وإلا فإن i ← max { i | s i > 0}، و s i ← s i − 1. إذا كان i < n − 1، فإن s i ← ( i + 1) ⋅ ( m − 1) − sum( s j ). نهاية الشرط. من أجل j ← i + 2، i + 3، …، n − 1 ، فإن s j ← k − 1. نهاية الشرط .

التعداد بدون حلقات

خوارزمية توليد تأخذ${\displaystyle O(1)}$يُطلق على أسوأ حالات الوقت اسم "الوقت غير الحلقي" لأن تعقيد الوقت لا يتضمن حلقة أو استدعاء ذاتي. ويُقال إن تعداد الأشجار من الرتبة m غير حلقي إذا كان، بعد التهيئة، يُولّد كائنات شجرية متتالية في${\displaystyle O(1)}$بالنسبة لشجرة m- ary معينة T مع${\displaystyle a}$كونها إحدى عقدها و${\displaystyle d}$إنه${\displaystyle t}$الطفل رقم -th، دوران يساري عند${\displaystyle a}$يتم ذلك عن طريق صنع${\displaystyle d}$العقدة الجذرية، وجعل ${\displaystyle b}$وجميع فروعها هي أبناء لـ${\displaystyle a}$بالإضافة إلى ذلك، نقوم بتعيين${\displaystyle m-1}$ترك معظم أطفال${\displaystyle d}$ل${\displaystyle a}$والطفل الأكثر يمينًا من${\displaystyle d}$يبقى ملتصقاً به بينما${\displaystyle d}$تمت ترقيته إلى الجذر، كما هو موضح أدناه:

حوّل شجرة من الرتبة m إلى شجرة يسارية من أجل i = 1... n : من أجل t = 2... m : طالما أن t ابن للعقدة عند العمق i ≠ 1: دوران Lt عند العقد على عمق i نهاية بينما نهاية ل نهاية ل

الدوران t -right عند النقطة d هو عكس هذه العملية. السلسلة اليسرى من T هي سلسلة من${\displaystyle x_{1},x_{2},\dots ,x_{n}}$العقد بحيث${\displaystyle x_{1}}$هو الجذر وجميع العقد باستثناء${\displaystyle x_{n}}$يكون لديهم طفل واحد متصل بأقصى اليسار (أي،${\displaystyle m[1]}$مؤشر ) يمكن تحويل أي شجرة متعددة الفروع إلى شجرة سلسلة يسارية باستخدام سلسلة من عمليات الدوران اليسارية المحدودة من t ، حيث t من 2 إلى m . وبالتحديد، يمكن القيام بذلك عن طريق إجراء عمليات دوران يسارية على كل عقدة.${\displaystyle x_{i}}$حتى كل${\displaystyle m-1}$تصبح الشجرة الفرعية فارغة عند كل عمق. ثم، يُشار إلى تسلسل عدد عمليات الدوران اليسرى-t التي تُجرى عند العمق i بـ${\displaystyle c_{i}}$يحدد كلمة رمزية لشجرة m- ary يمكن استعادتها عن طريق إجراء نفس تسلسل عمليات الدوران من اليمين إلى اليمين.

دع${\displaystyle m-1}$مجموعة من${\displaystyle c_{1},c_{2},\dots ,c_{m-1}}$يمثل عدد دورات L-2 ، ودورات L-3 ، ...، ودورات Lm التي حدثت عند الجذر (أي، i = 1). ثم،${\displaystyle c_{(i-1)(m-1)+t-1}}$يمثل عدد دورات Lt المطلوبة عند العمق i .

يُعدّ حساب عدد الدورانات اليسارية عند كل عمق طريقةً لترميز شجرة من الرتبة m . وبالتالي، فإنّ حصر جميع الترميزات القانونية الممكنة يُساعدنا على توليد جميع أشجار الرتبة m لقيم m و n مُعطاة . ولكن، ليس كل${\displaystyle c_{i}}$تمثل متواليات من m أعداد صحيحة غير سالبة شجرةً صالحةً من الرتبة m. متوالية من${\displaystyle (n-1)\cdot (m-1)+1}$الأعداد الصحيحة غير السالبة تمثل تمثيلاً صحيحاً لشجرة متعددة الفروع إذا وفقط إذا ^{[ 8 ]}$${\displaystyle \sum _{i=j}^{n}\sum _{t=2}^{m}c_{(i-1)(m-1)+t-1}\qquad \leq n-j,\qquad \forall j\in 0\dots n.}$$

أصغر تمثيل معجمي للكلمة المشفرة لـ m-ary مع n عقدة هو جميع الأصفار وأكبرها هو n −1 واحد متبوعًا بـ m −1 صفر على يمينه.

تهيئة c[i] إلى الصفر لجميع قيم i من 1 إلى n ⋅( k − 1) يتم تعيين p[i] إلى n − 1 لـ i من 1 إلى n، ويكون المجموع ← 0، ويكون j ← m − 1 شرط الإنهاء: يتم الإنهاء عندما يكون c[1] = n − 1 الإجراء التالي [ 8 ] المجموع ← المجموع + 1 − ج [ ج + 1] ج [ج] ← ج [ ج ] + 1 إذا كان ص [ ق [ ج ]] > ص [ ق [ ج + 1]] + 1 فإن ص [ ق [ ج ]] ← ص [ ق [ ج + 1]] + 1 نهاية إذا ص [ ق [ ج + ج [ ج ] ]] ← ص [ ق [ ج ]] ج [ ج + 1] ← 0 إذا كان المجموع = ص [ ق [ ج ]] فإن ج ← ج − 1 وإلا فإن ص [ ن ] ← المجموع ج ← م − 1 نهاية إذا نهاية

من تطبيقات الشجرة متعددة السلاسل (m -ary tree) إنشاء قاموس للتحقق من صحة السلاسل النصية المقبولة. وللقيام بذلك، نفرض أن m يساوي عدد الأحرف الأبجدية الصحيحة (مثل عدد أحرف الأبجدية الإنجليزية )، وأن جذر الشجرة يمثل نقطة البداية. وبالمثل، يمكن أن يحتوي كل فرع من فروع الشجرة على m فرعًا يمثل كل منها الحرف التالي المحتمل في السلسلة النصية. وبالتالي، يمكن للأحرف على طول المسارات أن تمثل مفاتيح صحيحة بتحديد الحرف الأخير من المفاتيح كعقدة طرفية. على سبيل المثال، في المثال أدناه، "at" و"and" هما سلسلتان نصيتان صحيحتان، حيث تم تحديد "t" و"d" كعقد طرفية. يمكن للعقد الطرفية تخزين معلومات إضافية تُربط بمفتاح معين. توجد طرق مشابهة لإنشاء مثل هذا القاموس باستخدام شجرة B ، أو شجرة ثمانية (Octree) ، أو شجرة ثلاثية (Trie) .

• عامل التفرع
• شجرة ثنائية الابن الأيسر والأخ الأيمن
• الشجرة الثنائية

• ستورر، جيمس أ. (2001). مقدمة في هياكل البيانات والخوارزميات . بيركهاوزر بوسطن. ISBN 3-7643-4253-6.

• الأشجار N -ary، برونو ر. بريس، دكتوراه، P.Eng.