binary-tree - شجرة - هياكل البيانات الشجرية




الفرق بين الشجرة الثنائية وشجرة البحث الثنائية (8)

الشجرة الثنائية هي شجرة لا يزيد أبناؤها على أكثر من شخصين. تتبع شجرة البحث الثنائية النموذج الثابت الذي يجب أن يكون للطفل الأيسر قيمة أصغر من مفتاح عقدة الجذر ، بينما يجب أن يكون للطفل الصحيح قيمة أكبر من مفتاح العقدة الجذرية.

هل يمكن لأي شخص أن يفسر الفرق بين شجرة البحث الثنائية وشجرة البحث الثنائية مع مثال ؟


ترمز Binary Tree إلى بنية بيانات تتكون من العقد التي يمكن أن تحتوي على مرجعين للأطفال فقط .

ومن ناحية أخرى ، فإن شجرة البحث الثنائية ( BST ) هي شكل خاص من بنية بيانات الشجرة الثنائية حيث يكون لكل عقدة قيمة مماثلة ، وأطفال أصغر قيمة مرتبطين بالأطفال اليساريين وأكبر قيمة مرتبطين باليمين.

وبالتالي ، فإن كل BST هي شجرة ثنائية ، ومع ذلك فإن بعض الشجرة الثنائية قد تكون أيضًا BST . يخطر أن BST هو مجموعة فرعية من شجرة ثنائية .

لذا ، فإن Binary Tree هي بنية بيانات عامة أكثر من Binary Search Tree . وعليك أيضًا أن تخطر بأن شجرة البحث الثنائية هي شجرة مرتبة بينما لا توجد مجموعة من القواعد لهذه الشجرة الثنائية العامة.

شجرة ثنائية

A Binary Tree وهو ليس BST ؛

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

شجرة البحث الثنائي (شجرة مرتبة)

A Binary Search Tree وهي شجرة ثنائية

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

خاصية عقدة شجرة البحث الثنائي

أخطر أيضًا أنه لأي عقدة رئيسية في BST ؛

  • تحتوي جميع العقد اليسرى على قيمة أصغر من قيمة العقدة الرئيسية. في المثال العلوي ، تكون النقاط ذات القيم {20 ، 25 ، 30} والتي تقع جميعها على اليسار ( أحفاد اليسار ) من 50 ، أصغر من 50.

  • جميع العقد الصحيحة لها قيمة أكبر من قيمة العقدة الرئيسية. في المثال العلوي ، تكون العُقد ذات القيم {70 ، 75 ، 80} والتي تقع جميعها على اليمين ( أحفاد اليمين ) من 50 ، أكبر من 50.

لا يوجد مثل هذه القاعدة لثنائي شجرة عقدة. القاعدة الوحيدة لـ " عقدة شجرة ثنائية" هي وجود طفلين بحيث تفسر نفسها بنفسها ولهذا السبب يطلق عليها اسم " ثنائي" .


شجرة البحث الثنائية هي نوع خاص من الشجرة الثنائية التي تعرض الخاصية التالية: لأي عقدة n ، تكون قيمة كل عقدة سلالية في الشجرة الفرعية اليسرى من n أقل من قيمة n ، وكل قيمة عقدة سلالية في الشجرة الفرعية الصحيحة هي أكبر من قيمة ن.


شجرة ثنائية: شجرة حيث كل عقدة لديها ما يصل إلى اثنين من الأوراق

  1
 / \
2   3

شجرة البحث الثنائية: تستخدم للبحث . شجرة ثنائية حيث يحتوي الطفل الأيسر على عقد فقط بقيم أقل من العقدة الرئيسية ، وحيث يحتوي الطفل الأيمن فقط على عقد ذات قيم أكبر من أو يساوي الأصل.

  2
 / \
1   3

كما أوضح الجميع أعلاه حول الفرق بين شجرة البحث الثنائية وشجرة البحث الثنائية ، أنا فقط إضافة كيفية اختبار ما إذا كانت شجرة ثنائية معينة هي شجرة البحث الثنائية.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

أتمنى أنها تساعدك. آسف إذا كنت أتحرك من الموضوع كما شعرت أنه من الجدير بالذكر هنا.


للتحقق من wheather أو عدم وجود Binary Tree معينة ، فإن Binary Search Tree عبارة عن نهج بديل.

Traerse Tree In Inorder Fashion (أي الطفلة اليسرى -> الوالد -> الطفل الأيمن) ، مخزن Traversed Node البيانات في متغير مؤقت يتيح لك نطق درجة الحرارة ، قبل تخزينها في درجة الحرارة مؤقتًا ، راجع البيانات الحالية للعقدة الحالية أعلى من السابق أو لا . ثم فقط كسرها ، شجرة ليست شجرة بحث ثنائي آخر عبور نهاية نقود.

فيما يلي مثال على Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

الحفاظ على درجة الحرارة متغير خارج


تتكون الشجرة الثنائية من العقد ، حيث تحتوي كل عقدة على مؤشر "يسار" ، ومؤشر "اليمين" ، وعنصر البيانات. يشير مؤشر "الجذر" إلى العقدة الأعلى في الشجرة. تشير مؤشرات اليمين واليسار بشكل متكرر إلى "أحجار فرعية" أصغر على كلا الجانبين. يمثل المؤشر الفارغ شجرة ثنائية بدون عناصر - الشجرة الفارغة. التعريف التعودي الرسمي هو: الشجرة الثنائية إما فارغة (يتم تمثيلها بمؤشر فارغ) ، أو تكون مصنوعة من عقدة واحدة ، حيث يشير كل من المؤشرات اليسرى واليمنى (تعريف متكرر للأمام) إلى شجرة ثنائية.

شجرة البحث الثنائية (BST) أو "الشجرة الثنائية المطلوبة" هي نوع من الشجرة الثنائية حيث يتم ترتيب العقد بالترتيب: لكل عقدة ، تكون جميع العناصر في الشجرة الفرعية اليسرى أقل للعقدة (<) ، وكل العناصر في الشجرة الفرعية الصحيحة أكبر من العقدة (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

الشجرة الموضحة أعلاه هي شجرة بحث ثنائية - العقدة "الجذر" هي 5 ، ونقاط الشجرة الفرعية اليسرى (1 ، 3 ، 4) هي <5 ، ونقاط الشجرة الفرعية الصحيحة (6 ، 9) هي> 5. متكرر ، يجب على كل من الأشجار الفرعية أيضًا أن تلتزم بقيد شجرة البحث الثنائي: في الشجرة الفرعية (1 ، 3 ، 4) ، يكون 3 هو الجذر ، 1 <3 و 4> 3.

احترس من الصياغة الدقيقة في المشاكل - "شجرة البحث الثنائية" تختلف عن "الشجرة الثنائية".


شجرة ثنائية

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

على سبيل المثال ، شجرة ثنائية مصنفة من الحجم 9 والارتفاع 3 ، مع عقدة جذر قيمتها 2. شجرة غير متوازن ولا يتم فرزها . https://en.wikipedia.org/wiki/Binary_tree

على سبيل المثال ، في الشجرة على اليسار ، لدى A الأطفال الستة {B، C، D، E، F، G}. يمكن تحويلها إلى شجرة ثنائية على اليمين.

بحث ثنائي

البحث الثنائي عبارة عن تقنية / خوارزمية يتم استخدامها للعثور على عنصر محدد في سلسلة العقد. يعمل البحث الثنائي على صفائف مصنفة .

يقارن البحث الثنائي القيمة المستهدفة بالعنصر الأوسط للمصفوفة ؛ إذا كانت غير متساوية ، فإن النصف الذي لا يكمن الهدف فيه يتم القضاء عليه ويستمر البحث على النصف المتبقي حتى ينجح أو النصف المتبقي فارغ. https://en.wikipedia.org/wiki/Binary_search_algorithm

شجرة تمثل البحث الثنائي . المصفوفة التي يتم البحث عنها هنا هي [20 ، 30 ، 40 ، 50 ، 90 ، 100] ، والقيمة المستهدفة هي 40.

شجرة البحث الثنائية

هذا أحد تطبيقات شجرة ثنائية. هذا هو متخصص للبحث .

تستند شجرة البحث الثنائية وشكل بيانات B-tree على البحث الثنائي .

أشجار البحث الثنائي (BST) ، التي تسمى أحيانًا أشجار ثنائية مرتبة أو مرتبة ، هي نوع معين من الحاويات : هياكل البيانات التي تخزن "عناصر" (مثل الأرقام والأسماء وغيرها) في الذاكرة. https://en.wikipedia.org/wiki/Binary_search_tree

شجرة بحث ثنائية بحجم 9 والعمق 3 ، مع 8 في الجذر. لا يتم رسم الأوراق.

وأخيرًا مخططًا رائعًا لمقارنة الأداء بين هياكل البيانات المعروفة والخوارزميات المطبقة:

صورة مأخوذة من الخوارزميات (الطبعة الرابعة)