Trenery Tree

Pohon Ternary
Pohon terner sederhana berukuran 10 dan tinggi 2.
Dalam ilmu komputer , pohon terner adalah struktur data pohon dimana masing-masing node memiliki paling banyak tiga nodus anak , biasanya dibedakan sebagai "kiri", "pertengahan" dan "benar". Simpul dengan anak-anak adalah simpul induk, dan nodus anak mungkin berisi referensi kepada orang tua mereka. Di luar pohon, sering ada referensi ke "root" node (leluhur dari semua node), jika ada. Setiap simpul dalam struktur data dapat dicapai dengan memulai di simpul akar dan berulang kali mengikuti rujukan ke anak kiri, tengah, atau kanan.
Pohon Ternary digunakan untuk mengaplikasikan pohon pencarian Ternary dan tumpukan rumput Ternary .

Definisi 
Sutradara Edge - Tautan dari orang tua ke anak.
Akar - Simpul tanpa orang tua. Paling banyak ada satu simpul akar di pohon yang berakar.
Daun Node - Setiap node yang tidak memiliki anak.
Node Orangtua - Setiap simpul terhubung dengan ujung yang diarahkan ke anak atau anak-anaknya.
Child Node - Setiap node terhubung ke node induk oleh tepi yang diarahkan.
Kedalaman - Panjang jalur dari akar ke simpul. Himpunan semua node pada kedalaman tertentu terkadang disebut level pohon. Simpul akar berada pada kedalaman nol.
Tinggi - Panjang jalan dari akar ke simpul terdalam di pohon. Pohon berakar dengan hanya satu simpul (akar) memiliki tinggi nol. Pada contoh diagram, pohon memiliki tinggi 2.
Sibling - Node yang berbagi node induk yang sama.
- Sebuah simpul p adalah leluhur dari sebuah simpul q jika ada di jalan dari q ke akar. Simpul q kemudian disebut keturunan dari hlm.
- Ukuran simpul adalah jumlah keturunan yang dimilikinya sendiri.

Properti pohon terner 
Jumlah maksimum node
- Biarkan h menjadi tinggi dari pohon terner
- Biarkan M (h) menjadi jumlah maksimum node dalam pohon terner yang tinggi h
h    M ( h )
0       1
1       4
2       13
3       40

Operasi umum 
Penyisipan
Node dapat dimasukkan ke dalam pohon terner di antara tiga node lain atau ditambahkan setelah node eksternal . Di pohon Ternary, sebuah simpul yang dimasukkan ditentukan untuk mana anak itu.

Node eksternal 
Katakan bahwa simpul eksternal yang ditambahkan ke adalah simpul A. Untuk menambahkan simpul baru setelah simpul A, A menetapkan simpul baru sebagai salah satu dari anak-anaknya dan simpul baru menetapkan simpul A sebagai induknya.

Node internal 
Penyisipan pada node internal lebih kompleks daripada pada node eksternal. Katakan bahwa simpul internal adalah simpul A dan simpul B adalah anak A. (Jika sisipan tersebut menyisipkan anak yang tepat, maka B adalah anak yang tepat dari A, dan juga dengan sisipan anak kiri atau anak tengah.) A menugaskan anak ke simpul baru dan node baru menugaskan induknya ke A. Kemudian simpul baru menugaskan anaknya ke B dan B menugaskan induknya sebagai simpul baru.

Penghapusan 
Penghapusan adalah proses dimana sebuah simpul dihapus dari pohon. Hanya simpul tertentu di pohon terner yang dapat dihilangkan dengan jelas.
Node dengan nol atau satu anak
Katakan bahwa simpul yang akan dihapus adalah simpul A. Jika simpul tidak memiliki anak ( simpul eksternal ), penghapusan dilakukan dengan menetapkan anak dari orang tua A ke orang tua null dan A menjadi null. Jika memiliki satu anak, tetapkan induk anak A ke orang tua A dan tetapkan anak dari orang tua A ke anak A.

Perbandingan dengan pohon lainnya 
Gambar di bawah adalah pohon pencarian biner yang mewakili 12 kata dua huruf. Semua node pada anak kiri memiliki nilai lebih kecil, sementara semua node pada anak yang tepat memiliki nilai lebih besar untuk semua node. Pencarian dimulai dari akar. Untuk menemukan kata "ON", kita bandingkan dengan "IN" dan ambil cabang yang tepat. Setiap perbandingan bisa mengakses setiap karakter dari kedua kata tersebut.
        di
      / \
     dari
    / \ / \
   seperti pada atau
    \ \ \ / \
    pada dia di
Pencarian digital mencoba menyimpan karakter string dengan karakter. Gambar berikutnya adalah pohon yang mewakili 12 kata yang sama;
         _ _ _ _ _ _ _ _ _ _ _ _ _ _
        / / / \ \ \
       / / / \ \ \
      abhiot
     / \ / \ | / | \ / | \ |
    steyenstfnro
   seperti yang dia lakukan adalah pada atau di
setiap kata masukan ditunjukkan di bawah simpul yang mewakili itu. Dalam sebuah pohon yang mewakili kata-kata dari huruf kecil, masing-masing node memiliki bercabang 26 arah. Pencarian sangat cepat: Pencarian untuk "IS" dimulai dari root, mengambil cabang "I", lalu cabang "S", dan berakhir pada simpul yang diinginkan. Pada setiap node, satu mengakses elemen array, tes untuk null, dan mengambil cabang.
                    i
              / | \
             / | \
            bso
         / | \ / \ | \
        aehntnt
        | \ | / \ |
        syefro
         \
          t
Gambar di atas adalah pohon pencarian terner yang seimbang untuk kumpulan 12 kata yang sama. Petunjuk rendah dan tinggi ditunjukkan sebagai garis siku, sedangkan pointer yang sama ditunjukkan sebagai garis vertikal. Pencarian kata "IS" dimulai dari akar, turunkan anak yang sama ke simpul dengan nilai "S", dan berhenti di sana setelah dua perbandingan. Pencarian "AX" membuat tiga perbandingan dengan huruf pertama "A" dan dua perbandingan dengan huruf kedua "X" sebelum melaporkan bahwa kata tersebut tidak ada di pohon.
sib.stts.edu