Saya telah memikirkan hal berikut:

  1. Degenerasi pohon menjadi daftar tertaut, dan saat merosot, buat array dinamis dengan objek simpul dan indeksnya di daftar tertaut

Ini akan terlihat seperti ini

def treeDegenerator(self):
    self.valList = []
    currentNode = self
    self.totalNodes = 0 
    self.nodes = 0
    while currentNode:
        while currentNode.getLeftChild():
            currentNode.rotate_root_right()
        self.valList.append(currentNode)
        currentNode = currentNode.getRightChild()
        self.totalNodes += 1
  1. gunakan array dinamis, dereferensi semua anak kiri dan anak kanan dan ubah pohon yang terdegenerasi menjadi pohon lengkap dengan menggunakan (nilai indeks)*2+1 untuk mendapatkan anak kiri, tambahkan 1 lagi untuk kanan.
def completeTree():
    for node in self.valList:
        node.left = None
        node.right = None
        
    for i in range(len(self.valList)):
        self.valList[i].left = self.valList[(i)*2+1]
        self.valList[i].right = a.valList[(i)*2+2]
  1. Berubah menjadi heap dengan menggeser nilai dengan membandingkan anak-anak untuk setiap node, level demi level, mulai dari bawah.

Ini adalah masalah di mana siswa harus membuat kode tanpa referensi pada ujian sebelumnya. Masalah dengan metode saya adalah, hampir tidak mungkin bagi saya untuk menulis semua kode itu dalam 30 menit dengan benar, dan mungkin bisa dilakukan jika saya menghafal beberapa kode sebelumnya. Saya bertanya-tanya apakah ada solusi yang lebih mudah, lebih layak, dan elegan untuk mengubah pohon biner apa pun menjadi tumpukan di tempat?

0
Harsh Dua 26 Mei 2021, 01:31

2 jawaban

Jawaban Terbaik

Secara konseptual Anda dapat membagi tugas ini menjadi dua langkah:

  1. Bangun kembali pohon menjadi BST yang seimbang sempurna dengan baris bawah diisi dari kiri ke kanan. Anda dapat melakukannya menggunakan versi modifikasi dari Hari- Algoritma Stout-Warren.
  2. Jalankan algoritme heapify untuk mengonversi pohon Anda menjadi heap biner. Ini dapat dilakukan dengan sangat indah secara rekursif; lihat di bawah untuk detailnya.

Algoritma Day-Stout-Warren bekerja dengan merotasi pohon menjadi single-linked list, kemudian dari sana menerapkan serangkaian rotasi untuk mengubahnya menjadi pohon yang seimbang sempurna. Saya tidak ingat dari atas kepala saya apakah algoritma DSW secara khusus akan menempatkan semua node yang tersisa di lapisan bawah pohon di paling kiri, seperti yang diperlukan oleh tumpukan biner. Jika tidak, Anda dapat memperbaikinya dengan melakukan pembersihan: jika pohon tidak memiliki jumlah simpul yang merupakan pangkat dua, hapus semua simpul dari lapisan bawah pohon, lalu ulangi pohon dengan inorder traversal untuk menempatkan mereka di paling kiri.

Adapun algoritma heapify: cara ini biasanya dilakukan dengan mengunjungi lapisan pohon dari bawah ke atas. Untuk setiap simpul, Anda berulang kali menukar simpul itu dengan turunannya yang lebih kecil hingga lebih kecil dari semua turunannya. Dengan struktur pohon eksplisit, ini dapat dilakukan dengan strategi rekursif yang elegan:

  • Jika pohon itu tidak memiliki anak, berhentilah.
  • Jika tidak, susun subpohon kiri dan kanan secara rekursif, lalu lakukan pass "bubble-down" berulang kali menukar nilai root dengan nilai anaknya yang lebih kecil hingga berada di tempat yang tepat.

Keseluruhan ini membutuhkan waktu O(n) dan hanya menggunakan ruang penyimpanan tambahan O(log n), yang merupakan ruang yang Anda perlukan untuk bingkai tumpukan untuk mengimplementasikan kedua algoritme.

[Editorializing] Meskipun demikian - ini sepertinya pertanyaan pengkodean yang sangat buruk untuk dimasukkan ke dalam ujian berjangka waktu 30 menit. Anda dapat memiliki perintah yang bagus tentang algoritme dan cara mengkodekannya, namun tidak mengingat semua langkah yang terlibat dalam dua sublangkah di sini. Meminta ini dalam setengah jam pada dasarnya menguji "apakah Anda telah menghafal implementasi berbagai algoritme yang tidak terkait dengan sangat rinci?", yang sepertinya bukan tujuan yang baik.

2
templatetypedef 26 Mei 2021, 00:07
  1. Saya pertama-tama akan menciutkan pohon menjadi daftar tertaut yang dipesan di node.right.

  2. Saya berasumsi kita mulai dengan BST yang dipesan. Jika tidak, maka urutkan daftarnya. Jika Anda menginginkan max-heap alih-alih min-heap, maka balikkan daftar pada titik ini juga.

  3. Hitung node dan hitung kedalaman pohon lengkap terbesar yang terkandung dalam solusi

  4. Lakukan traversal preorder rekursif dari pohon lengkap, mengisi setiap node dari kepala daftar saat Anda pergi.

  5. Lakukan traversal pre-order dari pohon yang baru saja Anda buat, isi daun dari node daftar hingga Anda habis

Langkah 4 akan dilakukan secara rekursif seperti ini:

root = list
fillChildren(root, list.right, levels-1)


fillChildren(root, list, levels) {
    if (levels < 1) {
        root.left = root.right = null
        return list
    }
    root.left = list
    list = fillChildren(root.left, list.right, levels-1)
    root.right = list
    list = fillChildren(root.right, list.right, levels-1)
    return list
}

Trik untuk ini, tentu saja, adalah bahwa pemetaan node untuk traversal pra-pesanan memenuhi properti heap.

Ini juga cukup mudah untuk menggabungkan langkah 4 dan 5 hanya dengan melacak indeks setiap node dalam tumpukan array imajiner.

Hanya untuk bersenang-senang, inilah seluruh pekerjaan:

treeToHeap(root) {

    if (root == null) {
        return null
    }

    // Convert tree to list

    while(root.left != null) {
        root = rotateRight(root)
    }
    for (n = root; n.right != null; n=n.right) {
        while (n.right.left != null) {
            n.right = rotateRight(n.right)
        }
    }

    // Count nodes
    count = 0
    for (n = root; n!=null; n=n.right) {
        count+=1
    }

    // Build min-heap
    
    list = root.right
    // root's index in imaginary array heap is 0
    
    if (count>1) {
        root.left = list
        list = fillNodes(root.left, list.right, 1, count)
    } else {
        root.left = null
    }
    if (count>2) {
        root.right = list
        list = fillNodes(root.right, list.right, 2, count)
    } else {
        root.right = null
    }
    return root
}

fillNodes(root, list, heapIndex, heapSize) {
    heapIndex = heapIndex*2+1
    if (heapIndex < heapSize) {
        root.left = list
        list = fillNodes(root.left, list.right, heapIndex, heapSize)
    } else {
        root.left = null
    }
    heapIndex += 1
    if (heapIndex < heapSize) {
        root.right = list
        list = fillNodes(root.right, list.right, heapIndex, heapSize)
    } else {
        root.right = null
    }
    return list
}

Jadi itu memakan waktu 15 menit (dan saya tidak repot-repot menulis rotateRight), dan itu setelah mencari tahu bagaimana melakukannya. Dan saya kembali beberapa kali untuk memperbaiki bug.

Untuk ujian 30 menit, itu cukup sulit... TAPI mungkin ujiannya tidak benar-benar membutuhkan heap yang seimbang. Jika ini hanya masalah penerapan heapify di tempat, maka itu cukup masuk akal.

0
Matt Timmermans 26 Mei 2021, 01:32