Leftist Tree

Leftist Tree adalah varian dari heap yang dapat menemukan elemen terkecil atau terbesar pada tree.
Dalam sebuah leftist tree dapat dikatakan jika nilai node internal di sebelah kiri lebih besar atau sama dengan internal node di sebelah kanan.

Leftist tree terbagi menjadi 2 yaitu:
-terdiri dari min tree atau max tree

Keuntungan menggunakan leftist tree
-leftist tree dapat menggabungkan 2 tree
-leftist tree lebih mudah diimplementasikan dengan link list

Sifat-sifat dari leftist tree

1. s value pada leftist tree selalu lebih besar pada node bagian kiri.
2. pada leftist max tree node teratas bernilai paling besar
3. pada leftist min tree node teratas bernilai paling kecil

Extended tree adalah metode untuk menghitung s(x) dari leftist tree.Dalam extended tree terdapat yang disebut external node. External node adalah node bernailai NULL yang ditambahkan dalam setiap node yang tidak memiliki anak atau anak yang complit.

S(x) atau s value adalah nilai s dari tiap node yang dihitung berdasarkan external node terdekat.

Insertion
Buatlah leftist tree baru yang mengandung node tunggal, masukkan node baru, lalu gabungkan dengan leftist tree yang sudah ada.

Node baru yang baru masuk di tempatkan di sebelah kanan. Setelah dimasukkan node baru, bandingkan setiap s(x) value dari setiap node. Jika s(x) value node yang kiri lebih kecil daripada s(x) value yag kanan, maka lakukan swap pada node tersebut beserta anak-anaknya.

Combine
Operasi utama leftist tree adalah menggabungkan 2 pohon(tree) menjadi satu pohon(tree).

Kedua root dari pohon(tree) tersebut dibandingkan terlebih dahulu. Jika ini leftist mix tree,
root dari pohon yang baru haruslah nilai terkecil dari kedua root yang harus digabungkan.
Jika ini leftist max tree,root dari pohon yang baru haruslah nilai terbesar dari kedua root yang harus digabungkan.



Deletion
Delete pada leftist tree hanya dapat dilakukan pada root. Seletah melakukan melakuka delete pada root, gabunglah kedua roots anak sub tree kiri dengan roots anak sub-pohon kanan dan mendapatkan leftist free baru.