That Is Erwanda Liao: algorithm

"Teachers open the door, but you must enter by yourself." Chinese Proverb

Hari ini saya akan mencoba membahas tentang leftist tree. Nama leftist tree datang dari fakta bahwa subtree kiri biasanya lebih tinggi dari subtree kanan. Leftist tree ditemukan oleh Clark Allan Crane dan menggunakan struktur heap. Leftist tree sangat berguna karena kemampuannya untuk menggabungkan tree (merge) dengan cepat.

Leftist Tree

Sebuah priority queue yang diimplementasikan dengan varian dari sebuah binary tree. Setiap node mempunyai sebuah hitungan yang merupakan jarak ke leaf terdekat. Sebagai tambahan terhadap heap property, leftist tree dijaga supaya descendant kanan dari setiap node mempunyai jarak lebih pendek ke sebuah leaf.
"

Leftist tree mempunyai operasi yang sama dengan heap dan dalam asymptotic complexity yang sama:

a. insert
b. remove min atau max
c. initialize (inisialisasi)

Leftist tree memerlukan kompleksitas waktu O(log n) untuk meld (menggabungkan), insert, dan delete max/min.

Extended Binary Tree

Mulailah dengan sebuah binary tree dan tambahkan external node di manapun terdapat subtree kosong. Hal ini akan menghasilkan extended binary tree.

Binary Tree

Extended Binary Tree

: Simbol external "dummy" node

Leftist tree didefinisikan menggunakan konsep extended binary tree. Oleh karena itu, semua node-node yang mempunyai elemen disebut internal node, sedangkan node-node artifisial yang terdapat di luar internal node disebut external node. Jumlah dari external node-nya dapat dihitung dengan n+1; n = jumlah (internal) node.

S-Value

Pada leftist tree kita mengenal istilah s-value atau s()—fungsi s(). S-value dari sebuah node adalah jarak dari node tersebut ke leaf terdekat dari extended binary tree. Cara mencari s-value tiap node adalah:

s(x) = min {s (leftChild(x)), s (rightChild(x))} + 1

s(x), x adalah external node dengan s(x) = 0
s(x), x adalah leaf, maka s(x) = min {s(leftChild(x)), s(rightChild(x))} + 1.
s(x) = min{s(external node), s(external node)} + 1.
s(x) = min{0, 0} + 1.
s(x) = 0 + 1.
s(x) = 1.

Pada height-biased leftist tree s-value dari sebuah left child dari sebuah node tidak lebih kecil dari s-value dari right child dari node tersebut.

Asumsikan x sebagai root dari sebuah leftist tree yang mempunyai n (internal) node, maka:

n ≥ [2 ^ {shortest(x)}] – 1

Path dari root paling kanan ke path external node adalah path root ke external node paling pendek. Panjangnya adalah shortest(x).

Bias

Height-biased leftist tree (HBLT) adalah leftist tree yang umumnya digunakan. Namun terdapat jenis bias yang lain, yakni weight-biased leftist tree (WBLT) yang ditemukan olehSeonghun Cho danSartaj Sahni.

w(x) = 1 + w(Left Child x) + w(Right Child x)

Weight-biased leftist tree adalah w(Left Child) root ≥ w(Right Child) root secara rekursif.

Height-biased leftist tree lebih sering digunakan, oleh karena itu operasi-operasi yang dijelaskan adalah operasi pada height-biased leftist tree.

Min Leftist Tree dan Max Leftist Tree

Seperti heap, leftist tree juga biasanya mempunyai dua variasi bentuk:

Min leftist tree, yakni leftist tree yang node-node paling atas mempunyai nilai yang lebih kecil dari node-node di bawahnya (children). Jadi, root adalah node dengan nilai terkecil.
Contoh min leftist tree:
Max leftist tree, yakni leftist tree yang node-node paling atas mempunyai nilai yang lebih besar dari node-node di bawahnya (children). Jadi, root adalah node dengan nilai terbesar.
Contoh max leftist tree:

Combining (Kombinasi) pada Leftist Tree

Kita dapat menggabungkan dua leftist tree dalam waktu O(log n).
Kombinasi pada min leftist tree:

Misalkan kita mempunyai 2 buah min leftist tree yang disebut tree a dan tree b.
Bandingkan root a dan root b. Root yang lebih kecil akan menjadi root yang baru untuk leftist tree yang kombinasi, left subtree dari leftist tree tersebut turut dibawa dan kombinasikan right subtree-nya dengan tree yang lain secara rekursif.
Contohnya, asumsikan bahwa root a lebih kecil dari root b. Biarkan left subtree dari tree tersebut dan kombinasikan right subtree dari tree a dengan semua binary tree b secara rekursif.
Perbaharui s-value dari setiap node yang telah digabungkan.
Konversikan tree kombinasi tersebut ke dalam leftist tree dengan saling mengubah posisi left dan right subtree-nya yang me-violate kesamaan leftist tree, yakni s-value subtree kiri lebih besar sama dengan s-value subtree kanannya—s(L(x)) ≥ s(R(x)).

Contoh min leftist tree:

2 < 5; jadi, tree dengan root 5 pasti menjadi right subtree dari tree dengan root 2

50 > 5; jadi, subtree dengan root 50 akan menjadi right subtree dari tree dengan root 5.

8 < 50; subtree dengan root 50 akan menjadi right subtree dari subtree dengan root 8.

Menukar posisi node untuk membentuk leftist tree

Bentuk akhir:

Contoh max leftist tree:

Untuk max leftist tree caranya hampir sama, root dengan nilai yang lebih besar akan menjadi root kombinasi leftist tree dan tree dengan root yang lebih kecil akan menjadi right subtree.

60 lebih besar, jadi kita akan me-merge subtree dengan root 48 dengan tree dengan root 45.

48 lebih besar, jadi kita akan me-merge subtree dengan root 30 dengan tree dengan root 45.

Sekarang 45 lebih besar, maka kita me-merge tree dengan root 40 dengan node 30.

Sekarang, 40 lebih besar, jadi kita akan me-merge root 30 dengan root 5.

Sekarang kita dapat menghubungkan 5 sebagai right subtree dari 30.

Sekarang kita harus menukar posisinya.

Inilah s-value akhir dari tree tersebut:

Insertion dan Deletion pada Leftist Tree

Insertion dan deletion di leftist tree mempunyai kesinambungan kinerja seperti pada combining (merging).

Insertion: anggap saja tree utama dengan tree a dan node yang ingin di-insert dengan tree b yang hanya berisi satu node. Kombinasikan tree a dengan tree b.

Deletion: deletion hanya terjadi pada root (delete min atau delete max). Pisahkan right subtree dari root dan left subtree-nya menjadi tree yang berbeda masing-masing, sebut saja left subtree sebagai tree a dan right subtree sebagai tree b. Hapus root lalu kombinasikan tree a dengan tree b.

Contoh insertion:

10; 13; 18; 12; 15

Insert (10)