Struktur Data - Pencarian Biner

Pohon secara inheren tidak benar-benar teratur. Ketika kita menggunakan pohon, kita tahu seperti apa struktur keseluruhannya, tetapi kita tidak tahu di mana elemen tertentu akan berada. Ternyata kita dapat menambahkan beberapa aturan tentang pemesanan elemen ke pohon kita untuk menyelesaikan tugas tertentu dengan sangat cepat. Ada jenis pohon biner yang lebih spesifik yang disebut pohon pencarian biner. Pohon pencarian biner, atau BST, jelas merupakan pohon biner. Artinya, setiap parent node memiliki paling banyak dua children. Tetapi sebagai array hanyalah merupakan jenis list, BST hanyalah jenis pohon biner. Ada aturan khusus untuk bagaimana nilai-nilai terkait dengan setiap node diatur.

Apalagi pada Struktur data binary tree mendukung banyak operasi pengaturan dinamis, termasuk SEARCH, MINIMUM, MAKSIMAL, PREDECESSOR, SUCCESSOR, INSERT, dan DELETE. Dengan demikian, kita dapat menggunakan pohon pencarian baik sebagai dictionari dan sebagai queue prioritas.

Pohon pencarian biner diatur, seperti namanya, dalam pohon biner, seperti yang ditunjukkan pada gambar dibawah nanti. Kita dapat merepresentasikan pohon seperti itu dengan struktur data yang terhubung di mana setiap node adalah objek. Selain data kunci dan satelit, setiap node berisi atribut kiri, kanan, dan p yang mengarah ke simpul yang terkait dengan left child (anak kiri), right child (anak kanannya), dan parent, masing-masing. Jika child atau parent hilang, atribut yang sesuai berisi nilai NIL. Simpul akar adalah satu-satunya simpul di pohon yang induknya adalah NIL.

Pohon pencarian biner (BSTs) sangat mudah dimengerti. Kita mulai dengan root node dengan nilai x, di mana subtree kiri x berisi node dengan nilai < x dan subtree kanan berisi node yang nilainya adalah ≥ x. Setiap node mengikuti aturan yang sama sehubungan dengan node di subtrees kiri dan kanan mereka. BST diurutkan sehingga setiap nilai di sebelah kiri node tertentu lebih kecil dari itu dan setiap nilai di sebelah kanan node tertentu lebih besar dari itu. Karena BST memiliki struktur ini, kita dapat melakukan operasi seperti pencarian, menyisipkan, dan menghapus cukup cepat. BST menarik karena mereka memiliki operasi yang sangat cepat: penyisipan, mencari, dan penghapusan semua dapat dilakukan dalam waktu O (log n). Penting untuk dicatat bahwa waktu O (log n) untuk operasi ini hanya dapat dicapai jika BST cukup seimbang.

box1

Katakanlah kita ingin menemukan 7. Kita akan mulai dari akarnya. Kita melihat 7 lebih besar dari 5 sehingga kita pergi ke kanan berikutnya. Karena elemen kita berikutnya adalah 8, kita tahu langkah selanjutnya masih tersisa. Dan hanya dalam beberapa langkah kita menemukannya. Anda mungkin telah memperhatikan bahwa kita tidak membutuhkannya untuk mencari setiap elemen untuk mencari tahu

Anda mungkin telah memperhatikan bahwa kita tidak perlu mencari setiap elemen untuk mencari tahu di mana tempat pencarian kita. Kita hanya perlu melihat satu nilai di setiap tingkat pohon, dan kemudian i dapat membuat keputusan hanya dengan perbandingan dengan elemen. Itu berarti waktu proses pencarian pada BST hanyalah ketinggian pohon, yang kita buktikan adalah log (n) ketika kita belajar tentang Inserting

Inserting dalam pohon biner cukup banyak proses yang sama. Seperti yang disebutkan sebelumnya Inserting adalah operasi O (log n) asalkan pohon cukup seimbang. Anda mulai di bagian atas dan Anda dapat membuat keputusan cepat tentang tempat untuk melihat setiap langkah dengan membandingkan ke elemen yang ingin Anda tambahkan. Akhirnya Anda akan menekan titik terbuka di pohon. Selama Anda membandingkan elemen Anda dengan benar di setiap langkah, Anda dapat menempatkan elemen baru di sana dan tidak melanggar properti BST inti.

Algoritme penyisipan dibagi untuk alasan yang bagus. Algoritma pertama (non-rekursif) memeriksa kasus dasar inti - apakah pohon itu kosong atau tidak. Jika pohon kosong maka kita cukup membuat root node dan selesai. Dalam semua kasus lain kita memanggil algoritma InsertNode rekursif yang hanya memandu kita ke tempat pertama yang tepat di pohon untuk meletakkan nilai. Perhatikan bahwa pada setiap tahap kita melakukan pemotongan biner, kita memilih untuk mengulang ke subtree kiri atau kanan dengan membandingkan nilai baru dengan nilai simpul saat ini.

Deleting node dari BST cukup mudah, dengan empat kasus untuk dipertimbangkan:

  • nilai untuk dihapus adalah simpul daun atau leaf node; atau
  • nilai untuk menghapus memiliki subtree kanan, tetapi tidak ada subtree kiri; atau
  • nilai untuk dihapus memiliki subtree kiri, tetapi tidak ada subtree kanan; atau
  • nilai untuk menghapus memiliki baik subtree kiri dan kanan dalam hal mana kita mempromosikan nilai terbesar dalam subtree kiri.

Ada juga kasus kelima implisit dimana node yang akan dihapus adalah satu-satunya node di pohon. Kasus ini sudah ditutupi oleh yang pertama, tetapi harus dicatat sebagai kemungkinan. Tentu saja dalam nilai BST dapat terjadi lebih dari satu kali. Dalam kasus seperti itu, kejadian pertama dari nilai tersebut dalam BST akan dihapus.

box1

Searching BST bahkan lebih sederhana daripada Inserting. Pseudocode sudah cukup jelas tetapi kita akan melihat secara singkat premis algoritme. Kita telah berbicara sebelumnya tentang inserting, pergi ke kiri atau kanan dengan subtree kanan berisi nilai-nilai yang ≥ x di mana x adalah nilai dari node yang kita masukkan. Ketika mencari aturan dibuat sedikit lebih kecil lagi dan pada satu waktu kita memiliki empat kasus untuk dipertimbangkan:

  • root = Θ di mana nilai case tidak ada dalam BST; atau
  • root.Value = value in which case value is in the BST; or
  • nilai <root.Value, kita harus memeriksa sub-akar kiri dari akar untuk nilai; atau
  • value> root.Value, kita harus memeriksa subtree root yang tepat untuk nilai.

box1

Query di pohon pencarian biner. Untuk mencari kunci 13 di pohon, kami mengikuti jalur 15 → 6 → 7 –> 13 dari akarnya. Kunci minimum dalam pohon adalah 2, yang ditemukan dengan mengikuti pointer kiri dari root. Kunci maksimum 20 ditemukan dengan mengikuti pointer kanan dari root. Successor node dengan kunci 15 adalah node dengan kunci 17, karena itu adalah kunci minimum dalam subtree kanan 15. Node dengan kunci 13 tidak memiliki subtree yang tepat, dan dengan demikian penggantinya adalah ancestor (leluhurnya) yang terendah, yang left child juga merupakan ancestor. Dalam hal ini, node dengan kunci 15 adalah penggantinya.

Untuk menemukan nilai terkecil dalam BST, Anda cukup menelusuri simpul di subpohon kiri BST selalu ke kiri pada setiap pertemuan dengan node, mengakhiri ketika Anda menemukan node tanpa subtree kiri. Kebalikannya adalah kasus ketika menemukan nilai terbesar di BST. Kedua algoritma sangat sederhana, dan terdaftar hanya untuk kelengkapan. Kasus dasar di kedua FindMin, dan algoritma FindMax adalah ketika referensi node Left (FindMin), atau Right (FindMax) adalah; dalam hal ini kita telah mencapai node terakhir.

Find Minimum:

algorithm FindMin(root)
    Pre: root adalah node root dari BST
            root = Θ
        Post: nilai terkecil di BST berada
    if root.Left = Θ
            return root.Value
       end if
   FindMin(root.Left)
end FindMin

Find Maximum:

algorithm FindMax(root)
        Pre: root adalah node root dari BST
         root = Θ
        Post: nilai terbesar di BST berada
    if root.Right = Θ
         return root.Value
        end if
       FindMax(root.Right)
end FindMax