Membuat Pohon Biner Pemesanan Otomatis

20

Saya memiliki tugas di mana saya perlu menggunakan pohon pencarian biner dan mengubahnya menjadi memesan sendiri sehingga item yang paling banyak diakses (memiliki prioritas lebih tinggi) berada di bagian atas pohon, root menjadi simpul yang paling banyak diakses .

Profesor memberi saya BST dan node struct untuk dikerjakan, tetapi mencoba untuk membuat kepala saya di sekitar algoritma untuk memperbarui pohon ketika hal-hal yang dimasukkan membingungkan saya.

Saya tahu bahwa ketika penyisipan terjadi, ia memeriksa apakah data node saat ini kurang atau lebih besar dari node saat ini, kemudian secara rekursif berjalan ke arah yang benar sampai menemukan pointer nol dan memasukkannya sendiri di sana. dan setelah dimasukkan itu meningkatkan prioritas sebesar 1.

template <class Type>
void BinarySearchTree<Type> ::  insert( const Type & x, BinaryNode<Type> * & t )
{
    if( t == NULL )
        t = new BinaryNode<Type>( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++;  // Duplicate; do nothing for right now
}

Sekarang saya perlu mencari tahu kapan simpul itu sama, bagaimana cara memesan ulang pohon sehingga simpul saat ini (yang sama dengan simpul yang sudah ada) menemukan simpul yang ada, meningkatkan prioritas simpul itu, kemudian menggesernya ke atas jika root adalah prioritas yang lebih rendah.

Saya pikir saya punya ide bahwa logika AVL akan bekerja, dan ketika pergeseran akan terjadi, itu akan menjadi satu putaran kanan atau satu putaran kiri.

Di sinilah saya bingung, tidak benar-benar tahu harus mulai dari mana dengan membuat algoritma untuk menyelesaikan masalah. Karena algoritma AVL bekerja dengan melacak keseimbangan pohon, kemudian memutar simpul ke kiri atau ke kanan, pohon ini tidak perlu khawatir tentang keseimbangan, hanya saja simpul dengan prioritas tertinggi tidak memiliki anak dengan prioritas lebih tinggi .

OghmaOsiris
sumber

Jawaban:

12

Hanya dua petunjuk:

  1. Jika Anda benar-benar ingin menggabungkan ide antrian prioritas dan pohon pencarian biner, pikirkan tentang menggabungkan heap dan BST dalam satu struktur.
  2. Ada konsep daftar mengatur diri sendiri . Idenya adalah untuk memindahkan elemen yang baru-baru ini diakses ke (atau ke arah) ke depan untuk mempercepat akses di masa depan ke elemen yang sama, sehingga "mempelajari" distribusi elemen dari waktu ke waktu (dengan kualitas tergantung pada implementasi tertentu). Mungkin Anda bisa menyesuaikan ini dengan pohon?

Spoiler: Ikuti tautan di bawah ini hanya jika Anda belum dapat menemukan sesuatu sendiri.

1. Ini disebut treap .
2. Splay trees menerapkan ide ini.

Raphael
sumber
2

Lihatlah pohon merentang, mereka benar-benar yang Anda butuhkan. Anda harus memodifikasi fungsi splay, bukan untuk memindahkan setiap node yang diakses sampai ke pohon, tetapi perlahan ke atas

Bober02
sumber
2
Kenapa dia harus melakukan perubahan ini? Strategi mana pun bisa dijalankan , dan ada yang lain. Selain itu, ini adalah pertanyaan pekerjaan rumah sehingga petunjuk lebih disukai daripada solusi (tanpa komentar). Terakhir, jawaban ini tidak ada artinya; mungkin Anda bisa mengubahnya untuk memimpin OP menuju solusi yang Anda usulkan?
Raphael
Nah, beberapa petunjuk untuk Anda: 1. Lihatlah fungsi splay dan lihat fungsinya, bacalah pertanyaannya dan cari tahu, berdasarkan apa yang dikatakannya, apakah Anda memodifikasi fungsi splay atau tidak. Dan tidak, tidak semua strategi layak karena dia memiliki persyaratan tertentu untuk dipenuhi berdasarkan prioritas sehingga beralih ke depan sepanjang waktu tidak valid 2. Solusi yang tidak dikomando? Bagaimana jawaban saya dan solusi tanpa komentar? 3. "Redundant sebagaimana adanya" ... Saya tidak melihat bagaimana jawaban Anda, oops, sorry - hints adalah ultimate dan "solusi uncommented" membawa saya ke meja
Bober02