شجرة الجذر

في علم الحاسوب ، تُعرف شجرة الجذر (وتُسمى أيضًا شجرة الجذر الثلاثية أو شجرة البادئة المضغوطة أو شجرة الجذر الثلاثية المُضغوطة ) بأنها بنية بيانات تُمثل شجرة ثلاثية مُحسّنة من حيث المساحة (شجرة بادئة)، حيث يتم دمج كل عقدة هي الابن الوحيد مع عقدتها الأب. لا يتجاوز عدد أبناء أي عقدة داخلية الجذر r لشجرة الجذر، حيث r = 2x ^لعدد صحيح x ≥ 1. وعلى عكس الأشجار العادية، يمكن تسمية الحواف بتسلسلات من العناصر بالإضافة إلى العناصر المفردة. وهذا ما يجعل أشجار الجذر أكثر كفاءة للمجموعات الصغيرة (خاصةً إذا كانت السلاسل طويلة) ولمجموعات السلاسل التي تشترك في بادئات طويلة.

على عكس الأشجار العادية (حيث تُقارن المفاتيح كاملةً دفعةً واحدةً من بدايتها حتى نقطة عدم المساواة)، تُقارن المفاتيح عند كل عقدة على حدة، حيث يُمثل عدد البتات في تلك العقدة أساس r لشجرة الأساس. عندما يكون r يساوي 2، تكون شجرة الأساس ثنائية (أي تُقارن بتة واحدة من المفتاح عند تلك العقدة)، مما يُقلل من التباعد على حساب زيادة عمق الشجرة - أي زيادة العمق حتى دمج سلاسل البتات غير المتباعدة في المفتاح. عندما يكون r ≥ 4 قوةً للعدد 2، تكون شجرة الأساس من نوع r -ary، مما يُقلل من عمق الشجرة على حساب احتمالية التباعد.

كتحسين، يمكن تخزين تسميات الحواف بحجم ثابت باستخدام مؤشرين إلى سلسلة نصية (للعنصر الأول والأخير). ^{[ 1 ]}

لاحظ أنه على الرغم من أن الأمثلة الواردة في هذه المقالة تُظهر السلاسل كتسلسلات من الأحرف، إلا أنه يمكن اختيار نوع عناصر السلسلة بشكل تعسفي؛ على سبيل المثال، كبت أو بايت من تمثيل السلسلة عند استخدام ترميزات الأحرف متعددة البايت أو Unicode .

تُعدّ أشجار الجذر مفيدةً لإنشاء مصفوفات ترابطية بمفاتيح يمكن التعبير عنها كسلاسل نصية. ولها تطبيقات خاصة في مجال توجيه بروتوكول الإنترنت (IP) ، ^{[ 2 ] [ 3 ] [ 4 ]} حيث تُناسب قدرتها على احتواء نطاقات واسعة من القيم، مع بعض الاستثناءات، التنظيم الهرمي لعناوين IP بشكلٍ خاص . ^{[ 5 ]} كما تُستخدم أيضًا للفهارس المعكوسة للمستندات النصية في استرجاع المعلومات .

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

ابحث عن

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

يفترض الكود الزائف التالي وجود هذه الطرق والأعضاء.

حافة

• العقدة الهدف
• ملصق سلسلة

العقدة

• مصفوفة من الحواف
• دالة isLeaf()

دالة البحث ( سلسلة نصية x) { // ابدأ من الجذر بدون العثور على أي عناصر Node traverseNode := root ; int elementsFound := 0; // استمر في التصفح حتى يتم العثور على ورقة أو يصبح من غير الممكن المتابعة بينما (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length) { // الحصول على الحافة التالية لاستكشافها بناءً على العناصر التي لم يتم العثور عليها بعد في x Edge nextEdge := select edge from traverseNode.edges where edge.label is a prefix of x.suffix(elementsFound) // x.suffix(elementsFound) returns the last (x.length - elementsFound) elements of x// هل تم العثور على حافة؟ إذا (الحافة التالية != فارغة ) { // حدد العقدة التالية للاستكشاف traverseNode := nextEdge.targetNode; // زيادة عدد العناصر التي تم العثور عليها بناءً على التسمية المخزنة على الحافة تم العثور على العناصر += طول تسمية الحافة التالية؛ } آخر { // إنهاء الحلقة traverseNode := null ; } } // يتم العثور على تطابق إذا وصلنا إلى عقدة طرفية واستخدمنا بالضبط x.length من العناصر. return (traverseNode != null && traverseNode.isLeaf() && elementsFound == x.length); }

تم اختراع بنية البيانات هذه في عام 1968 بواسطة دونالد ر. موريسون، ^{[ 6 ]} الذي ترتبط به بشكل أساسي، وجيرنوت جوينبيرجر. ^{[ 7 ]}

يُطلق دونالد كنوث ، في الصفحات 498-500 من المجلد الثالث من كتاب "فن برمجة الحاسوب" ، على هذه الأشجار اسم "أشجار باتريشيا"، ويُفترض أن ذلك مُستوحى من الاختصار الموجود في عنوان ورقة موريسون البحثية: "باتريشيا - خوارزمية عملية لاسترجاع المعلومات المُشفّرة أبجديًا رقميًا". واليوم، تُعتبر أشجار باتريشيا أشجارًا جذرية أساسها 2، مما يعني أنه تتم مقارنة كل بت من المفتاح على حدة، وأن كل عقدة تُمثل فرعًا ثنائي الاتجاه (أي، يسارًا أو يمينًا).

(في المقارنات التالية، يُفترض أن طول المفاتيح هو k وأن بنية البيانات تحتوي على n من الأعضاء.)

Unlike balanced trees, radix trees permit lookup, insertion, and deletion in O(k) time rather than O(log n). This does not seem like an advantage, since normally k ≥ log n, but in a balanced tree every comparison is a string comparison requiring O(k) worst-case time, many of which are slow in practice due to long common prefixes (in the case where comparisons begin at the start of the string). In a trie, all comparisons require constant time, but it takes m comparisons to look up a string of length m. Radix trees can perform these operations with fewer comparisons, and require many fewer nodes.

Radix trees also share the disadvantages of tries, however: as they can only be applied to strings of elements or elements with an efficiently reversible mapping to strings, they lack the full generality of balanced search trees, which apply to any data type with a total ordering. A reversible mapping to strings can be used to produce the required total ordering for balanced search trees, but not the other way around. This can also be problematic if a data type only provides a comparison operation, but not a (de)serialization operation.

Hash tables are commonly said to have expected O(1) insertion and deletion times, but this is only true when considering computation of the hash of the key to be a constant-time operation. When hashing the key is taken into account, hash tables have expected O(k) insertion and deletion times, but may take longer in the worst case depending on how collisions are handled. Radix trees have worst-case O(k) insertion and deletion. The successor/predecessor operations of radix trees are also not implemented by hash tables.

A common extension of radix trees uses two colors of nodes, "black" and "white". To check if a given string is stored in the tree, the search starts from the top and follows the edges of the input string until no further progress can be made. If the search string is consumed and the final node is a black node, the search has failed; if it is white, the search has succeeded. This makes possible to add a large range of strings with a common prefix to the tree, using white nodes, then remove a small set of "exceptions" in a space-efficient manner by inserting them using black nodes.

تُعدّ HAT -trie بنية بيانات مُراعية لذاكرة التخزين المؤقت، تعتمد على أشجار الجذر، وتُوفّر تخزينًا واسترجاعًا فعالين للسلاسل النصية، بالإضافة إلى تكرارات مُرتبة. ويُضاهي أداؤها، من حيث الوقت والمساحة، أداء جداول التجزئة المُراعية لذاكرة التخزين المؤقت . ^{[ 8 ] [ 9 ]}

شجرة باتريشيا هي نوع خاص من شجرة البحث الثنائية (الأساس 2)، حيث لا تُخزّن العقد كل بت من كل مفتاح بشكل صريح، بل تُخزّن فقط موضع البت الأول الذي يُميّز بين شجرتين فرعيتين. أثناء عملية الاجتياز، تفحص الخوارزمية البت المُفهرس لمفتاح البحث وتختار الشجرة الفرعية اليسرى أو اليمنى حسب الحاجة. من أبرز ميزات شجرة باتريشيا أنها لا تتطلب سوى إدخال عقدة واحدة لكل مفتاح فريد مُخزّن، مما يجعلها أكثر إحكامًا من شجرة البحث الثنائية القياسية. كذلك، بما أن المفاتيح الفعلية لم تعد تُخزّن بشكل صريح، فمن الضروري إجراء مقارنة كاملة للمفتاح على السجل المُفهرس لتأكيد التطابق. في هذا الصدد، تُشبه باتريشيا إلى حد ما الفهرسة باستخدام جدول التجزئة. ^{[ 6 ]}

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

من الممارسات الشائعة تخفيف معايير منع وجود عقدة أصلية لها ابن واحد فقط في الحالات التي تمثل فيها العقدة الأصلية مفتاحًا صالحًا في مجموعة البيانات. يحقق هذا النوع من أشجار الجذر كفاءةً أعلى في استخدام المساحة مقارنةً بالنوع الذي يسمح فقط بالعقد الداخلية التي لها ابنان على الأقل. ^{[ 13 ]}

• مواد بحثية ومراجعية حول الخوارزميات وهياكل البيانات: باتريشيا ، من تأليف لويد أليسون، جامعة موناش
• باتريشيا تري ، قاموس المعهد الوطني للمعايير والتكنولوجيا للخوارزميات وهياكل البيانات
• أشجار كريت-بت ، بقلم دانيال ج. بيرنشتاين
• واجهة برمجة تطبيقات شجرة الجذر في نواة لينكس ، بقلم جوناثان كوربيت
• كارت (شجرة جذر التغيير الرئيسية) ، بقلم بول جارك
• شجرة الجذر التكيفية: فهرسة ARTful لقواعد بيانات الذاكرة الرئيسية ، بقلم فيكتور ليس، وألفونس كيمبر ، وتوماس نيومان ، جامعة ميونخ التقنية