2-3-4 Tree

2-3-4 Tree

Sebuah pohon 2-3-4 (juga disebut pohon 2-4), dalam ilmu komputer, disebutkan sebagai struktur data  menyeimbangkan diri  yang umumnya digunakan untuk mengimplementasikan kamus.  2-3-4 pohon adalah pohon B-order  4; seperti B-pohon pada umumnya, mereka dapat mencari, menyisipkan dan menghapus dalam O  (log n) waktu. Satu properti sebuah pohon 2-3-4 adalah bahwa semua node eksternal berada pada kedalaman yang sama.

2-3-4 pohon adalah isometry  dari pohon hitam merah,  yang berarti bahwa mereka struktur data  setara. Dengan kata lain, untuk setiap 2-3-4 pohon, terdapat paling tidak satu pohon merah-hitam dengan elemen data dalam urutan yang sama. Selain itu, penyisipan dan penghapusan 2-3-4 operasinya pada pohon-pohon yang menyebabkan ekspansi simpul, perpecahan dan gabungan yang setara dengan warna-membalik dan rotasi pohon merah-hitam. Perkenalan ke merah-hitam biasanya pohon pohon 2-3-4 memperkenalkan pertama, karena mereka secara konseptual sederhana. Pohon 2-3-4 Namun, mungkin sulit untuk mengimplementasikan di kebanyakan bahasa pemrograman karena jumlah besar kasus khusus yang terlibat dalam operasi di pohon. Merah-pohon hitam  yang mudah untuk diterapkan, jadi cenderung untuk digunakan sebagai gantinya.

Insert

Untuk memasukkan nilai, kita mulai dari akar pohon 2-3-4:

1. Jika node saat ini adalah 4-node:

• Mendorong elemen tengah dari 4-node menjadi orangtua, meninggalkan 3-node.
• Split sisanya 3-simpul menjadi sepasang 2-node.
• Jika ini adalah akar simpul (yang dengan demikian tidak memiliki orang tua), nilai tengah menjadi akar baru 2-node dan tinggi pohon meningkat sebesar 1. Naik ke akar.
• Jika tidak, mendorong nilai tengah menjadi simpul orangtua. Naik ke simpul orangtua.

2. Menemukan anak yang mengandung nilai interval untuk dimasukkan.
3. Jika anak tersebut kosong, masukkan nilai ke dalam simpul saat ini dan selesai.

Jika tidak, turun ke anak dan ulangi dari langkah

Delete (Penghapusan)

Penghapusan adalah operasi yang lebih kompleks dan melibatkan banyak kasus khusus. Pertama elemen yang akan dihapus harus ditemukan. Elemen harus dalam sebuah simpul di bagian bawah pohon; sebaliknya, hal itu harus bertukar dengan elemen lain yang mendahului dalam in-order traversal (yang harus ada di node paling bawah) dan bahwa elemen dihapus saja.

Jika elemen yang akan dihapus dari suatu 2-node, maka sebuah simpul yang tidak memiliki unsur-unsur akan menghasilkan. Ini disebut underflow. Untuk memecahkan underflow, sebuah elemen ditarik dari orangtua simpul ke simpul di mana elemen dihapus dan kekosongan diciptakan dalam simpul ayah diganti dengan elemen dari simpul saudara. (Saudara node adalah mereka yang berbagi orang tua yang sama node.) Hal ini disebut transfer.

Jika saudara adalah 2-node sendiri, underflow masih terjadi, karena sekarang saudara tidak mempunyai elemen. Untuk mengatasi ini, dua saudara kandung node yang digabungkan bersama (setelah menarik elemen dari simpul orangtua).

Jika orangtua adalah 2-node, underflow akan terjadi pada node induk. Hal ini diselesaikan dengan menggunakan metode di atas. Ini dapat menyebabkan node orangtua yang berbeda untuk mempertahankan underflow sebagai pengganti penghapusan dan sedang dilakukan, yang disebut sebagai cascading underflow.

Penghapusan dalam pohon 2-3-4 adalah O (log n), sementara transfer dan fusi waktu konstan,

Read more

Red Black Tree

RED BLACK TREE

Red-Balck Tree (RBT) adalah sebuah BST (binary search tree) dimana tiap simpul memiliki atribut warna yang bernilai merah atau hitam.

            RBT juga berguna dalam pemrograman fungsional karena RBT merupakan salah satu struktur data yang paling “persistent”, digunakan untuk membuat associative array dan himpunan yang bhisa mengambil kembali versi sebelumnya setelah perubahan. Versi “persistent” dari RBT memerlukan tambahan ruang O(log n) untuk setiap insersi atau delesi, selain waktu.

RBT isometri dari pohon 2-3-4. Artinya, untuk setiap 2-3-4 pohon, terdapat paling sedikit satu satu RBT dengan elemen data yang berurutan sama. Operasi insersi dan delesi pada pohon 2-3-4 equivalen dengan color-flipping (pertukaran warna) dan rotasi pada RBT. Ini membuat pohon 2-3-4 alat yang penting untuk memahami logika dibalik RBT, hal ini pula yang membuat berbagai text algoritma memperkenalkan pohon 2-3-4 sebelum RBT walaupun pohon 2-3-4 lebih jarang digunakan.

Red Black Tree adalah suatu BST( Binary Search Tree) dimana node-node dan edge-edge memiliki warna merah atau hitam. Warna dari root selalu hitam. Warna dari edge yang menghubungkan ayah dengan anaknya selalu berwarna sama dengan warna node anak tersebut. Selain atribut yang dimiliki oleh BST, kita memerlukan persyaratan berikut untuk memnentukan

validitas RBT :

Aturan pada Red Black Tree :

1.      Setiap simpul/node adalah berwarna merah atau hitam

2.      Akar selalu berwarna hitam

3.      Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.

4.      Jika node berwarna merah, anaknya harus berwarna hitam

5.      Node berwarna merah secara berturut-turut tidak diperkenankan.

6.      Setiap path dari node yang menuju ke nil harus mengandung nilai yang sama dengan node yang berwarna hitam.

7.      Tree dikatakan setimbang jika selisih level dari anak kiri dan anak kanan maksimal dua.

8.      Node dibawah root yang berada pada level yang sama disebut sibling.

Aturan Insert pada Red Black Tree :

1.      Setiap node baru yang disisipkan  kedalam tree akan diberi warna merah.

2.      Jika kita memberi warna hitam  pada node baru yang  masuk, maka jumlah node dari root akan berbeda.

3.      Jika kita memasukkan node baru yang berwarna merah kedalam parent yang berwarna hitam tidak akan menjadi masalah, yang menjadi masalah adalah jika kita menyisipkan node baru ke dalam parent yang berwarna merah

4.      Jika parent berwarna merah kita akan membuat dua node merah yang berurutan, jadi kita harus melakukan rotasi atau pewarnaan ulang.

5.      Hal penting yang harus diingat adalah node yang tidak mempunyai daun harus berwarna hitam.

 

Insertion

Penyisipan dimulai dengan menambahkan node seperti penyisipan pohon pencarian biner  dilakukan dan dengan mewarnai merah. Sedangkan dalam pohon pencarian biner, kita selalu menambahkan daun, merah-hitam daun pohon tidak mengandung informasi, jadi kita tambahkan node interior merah, dengan dua daun hitam, di tempat yang ada daun hitam.

Apa yang terjadi berikutnya tergantung pada warna terdekat lain node. Paman (saudara parent) dalam istilah node akan digunakan untuk merujuk pada saudara kandung dari node orangtua, seperti dalam pohon keluarga manusia. Perhatikan bahwa:

Properti 3 (Semua daun yang hitam) selalu berlaku.

Properti 4 (Baik anak-anak dari setiap node merah hitam) terancam hanya dengan menambahkan simpul merah, mengecat node hitam merah, atau rotasi.

Properti 5 (Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam) terancam hanya dengan menambahkan node hitam, mengecat simpul merah hitam, atau rotasi.

Catatan: Label N akan digunakan untuk menunjukkan simpul sedang dimasukkan (berwarna merah); P akan menunjukkan N 's simpul ayah, G akan menyatakan N' s kakek-nenek, dan U akan menunjukkan N 's paman. Perhatikan bahwa di antara beberapa kasus, peran dan label simpul komunikasi, tetapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini.

Deleting (Penghapusan)

Dalam sebuah pohon pencarian biner yang normal, saat menghapus sebuah node dengan dua anak-anak non-daun, kita menemukan salah satu elemen maksimum dalam subtree kiri atau elemen minimum dalam subtree kanan, dan memindahkan nilainya ke dalam node yang dihapus . Kami kemudian menghapus simpul kita menyalin nilai dari, yang pasti kurang dari dua non-daun anak-anak. Karena hanya menyalin nilai tidak melanggar sifat merah-hitam, ini untuk mengurangi masalah menghapus sebuah node dengan paling banyak satu anak non-daun. Tidak peduli apakah simpul ini adalah simpul kami awalnya ingin menghapus atau simpul kita menyalin nilai dari.

Untuk masalah ini kita dapat mengasumsikan kita menghapus sebuah node dengan paling banyak satu daun non-anak, yang akan kita sebut dengan anak (jika ia hanya mempunyai anak-anak daun, membiarkan salah satu dari mereka menjadi para anak). Jika kita menghapus simpul merah, kita dapat dengan mudah menggantinya dengan anak, yang harus hitam. Semua jalan melalui node dihapus hanya akan melewati kurang satu simpul merah, dan kedua dihapus node orangtua dan anak harus hitam, jadi sifat 3 (Semua daun, termasuk null s, yang hitam) dan 4 (Kedua anak-anak dari setiap node merah hitam) masih terus. Lain kasus sederhana adalah ketika dihapus node anak hitam dan merah. Cukup menghapus simpul hitam bisa memecahkan Properti 4 (Baik anak-anak dari setiap node merah hitam) dan 5 (Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam), tetapi jika kita mengecat kembali dengan anak hitam, baik properti ini dipertahankan.

Kasus yang rumit adalah ketika kedua simpul untuk dihapus dan anak yang hitam. Kita mulai dengan mengganti node untuk dihapus dengan anak. Kami akan panggilan (atau label) anak ini (dalam posisi baru) N, dan saudara (orangtua baru anak lain) S. Dalam diagram di bawah ini, kita juga akan menggunakan P untuk N 's orangtua baru, S L untuk S' s anak kiri, dan S R untuk S 's anak kanan (dapat ditunjukkan bahwa S tidak bisa menjadi daun).

Catatan: Di antara beberapa kasus, saling bertukar peran dan label dari node, tapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini. Putih merupakan warna yang tidak diketahui (baik merah atau hitam).

Read more