هل من الضروري تنفيذ BST مع كلا المفتاحين والقيم؟

Question

هل من الضروري تنفيذ بيت مع كلا المفتاحين والقيم؟ يمكنني تطبيق BST التي تحتوي على أسلوب مكالمات مثل ما يلي، حيث ستجعل المقارنة في كل عقدة عما إذا كان ينبغي أن تذهب اجتياز العقدة اليسرى أو العقدة اليمنى بناء على قيمة V:

public class BST<V>
{
    public void Insert(V value)
    {
        //implementation
    }

    public V Remove(V value)
    {
        //implementation
    }

    //other methods
}

أو، يمكنني تطبيق BST بحيث يحتوي على أسلوب مكالمات مثل ما يلي، حيث مفاتيح K هي تحديد المقارنة على ما إذا كان يجب اجتياز العقدة اليسرى أو العقدة اليمنى:

public class BST<K key, V value>
{
    public void Insert(K key, V value)
    {
        //implementation
    }

    //which of the following would then be the appropriate method signature?
    public V Remove(K key)
    {
        //implementation
    }
    //or?
    public V Remove(V Value)
    {
        //implementation
    }

    //other methods
}

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

مثال يمكنني التفكير في حيث يتم استخدام هذا هو في نواة ويندوز.