Struktur Data - Rotasi Pohon

Oke kita lanjutkan materi kita tentang struktur pohon, ini masih ada kaitannya dengan materi sebelumnya, Red Black Tree. Sebelum memasuki pembahasan, kita recovery materi tentang BST. BST menarik karena mereka memiliki operasi yang cepat menguntungkan: penyisipan(inserting), pencarian(searching), dan penghapusan(deleting) yang 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; untuk struktur data pohon dengan properti penyeimbang diri ini pembahasan kita yang disebut sebagai AVL tree. Diberi nama AVL tree, sesuai dengan yang menemukan metode ini pertama kali, Adelson-Velsky dan E.M. Landis.

AVL tree ini adalah pohon pencarian biner BST dengan menyeimbangkan diri kondisi yang menyatakan bahwa perbedaan antara tinggi kiri dan kanan subpohon tidak boleh tidak lebih dari satu. Kondisi ini, dipulihkan setelah setiap modifikasi pohon, memaksa bentuk umum pohon AVL. Sebelum melanjutkan, mari kita fokus pada mengapa keseimbangan sangat penting. Pertimbangkan sebuah biner pohon pencarian diperoleh dengan memulai dengan pohon kosong dan memasukkan beberapa nilai dalam urutan berikut 1,2,3,4,5.

BST pada Gambar dibawah merupakan skenario terburuk di mana waktu berjalan dari semua operasi umum seperti pencarian, penyisipan dan penghapusan adalah O (n). Dengan menerapkan kondisi keseimbangan, kami memastikan bahwa waktu berjalan terburuk dari setiap operasi umum adalah O (log n). Ketinggian pohon AVL dengan n node adalah O (log n) terlepas dari urutan di mana nilai-nilai dimasukkan. Terlihat pada gambar ini terjadi BST yang tidak seimbang.

box1

Kondisi keseimbangan AVL, juga dikenal sebagai faktor keseimbangan node yang mewakili setiap bagian tambahan informasi yang disimpan untuk setiap node. Ini dikombinasikan dengan teknik yang secara efisien mengembalikan kondisi keseimbangan untuk pohon. Dalam pohon AVL, penemu menggunakan teknik yang disebut rotasi pohon atau Tree Rotation.

box1

Lihat disini dilakukan inserting dengan urutan 1,2,3,4,5. Oke, jadi Rotasi pohon adalah operasi waktu konstan pada pohon pencarian biner yang mengubah bentuk pohon sambil mempertahankan properti BST standar. Ada kiri dan rotasi kanan, keduanya menurunkan tinggi BST dengan memindahkan subpohon yang lebih kecil ke bawah dan subpohon yang lebih besar.

box1

Seperti halnya kasus yang terjadi di materi Red black tree, parent node berwarna merah dan saudara kandungnya berwarna hitam. Di keduanya, Anda harus melakukan rotasi. Dalam satu rotasi, Anda menggeser sekelompok simpul di sekitar dengan cara yang mengubah struktur pohon, tetapi bukan urutan simpul.

box1

Perlu diingat bahwa ini masih merupakan BST, jadi, kita perlu menjaga elemen-elemen kita dalam urutan yang ketat. Dalam kasus diatas, node merah dan parent merahnya tidak berada di sisi yang sama dari parent mereka. Node kita adalah children kanan dan parent-nya adalah child kiri. Di sini kita akan melakukan rotasi kiri karena node bergeser satu tempat ke kiri sambil mempertahankan urutan mereka. Pada titik ini, kita memiliki pengaturan yang terlihat persis seperti kasus gambar dibawah, di mana kedua node merah dan parent-nya yang merah berada di sisi yang sama dengan parent mereka., dibagian yang kiri.

box1

Kita akan melakukan rotasi kanan di sini, tetapi kali ini, melibatkan grandaparent dan kedua child.

box1

Kita perlu menukar warna kedua node ini juga. Hasilnya:

box1

Kita telah mengatur kembali node tanpa mengubah jumlah node hitam di jalur mana pun. Itu semua adalah kasus yang bisa muncul dalam inserting. Sekali lagi, kita hanya perlu melakukan pengaturan ulang agar bisa menjaga agar keseimbangan Red black tree dan properti BST terpenuhi. Dalam melakukan rotasi, kita mempertahankan satu sub pohon dari jauh lebih besar dari yang lain. Inserting, seperti juga searching dan deleting, adalah log dari n dalam kasus rata-rata dan terburuk. BST dimana O(n) merupakan kasus yang terburuk karena mereka bisa tidak seimbang. Karena kami berhati-hati agar tetap seimbang di sini, running time tidak akan sebesar itu. Algoritma rotasi kanan dan kiri simetris. Hanya pointer yang diubah oleh rotasi yang menghasilkan kompleksitas waktu proses O (1); bidang lain yang ada di node tidak berubah.