Melaksanakan Kaedah padam

Memadamkan elemen daripada pokok AVL adalah sama seperti memadamkannya daripada BST, kecuali pokok itu mungkin perlu diseimbangkan semula. Seperti yang dibincangkan dalam Bahagian, Memadam Elemen daripada BST, untuk memadamkan elemen daripada pokok binari, algoritma mula-mula mencari nod yang mengandungi elemen. Biarkan arus menghala ke nod yang mengandungi elemen dalam pepohon binari dan induk menghala ke induk nod semasa. Nod semasa mungkin anak kiri atau anak kanan nod ibu bapa.
Dua kes timbul apabila memadamkan elemen.

Kes 1: Nod semasa tidak mempunyai anak kiri, seperti yang ditunjukkan dalam Rajah di bawah (a). Untuk memadamkan nod semasa, hanya sambungkan nod induk dengan anak kanan nod semasa, seperti ditunjukkan dalam Rajah di bawah (b). Ketinggian nod di sepanjang laluan dari nod induk sehingga akar mungkin telah berkurangan. Untuk memastikan pokok itu seimbang, mohon

balancePath(parent.element);

Kes 2: Nod semasa mempunyai anak kiri. Biarkan rightMost menghala ke nod yang mengandungi elemen terbesar dalam subpokok kiri nod semasa dan parentOfRightMost menghala ke nod induk rightMost nod, seperti yang ditunjukkan dalam Rajah di bawah (a). Nod Paling kanan tidak boleh mempunyai anak kanan tetapi mungkin mempunyai anak kiri. Gantikan nilai elemen dalam nod semasa dengan satu dalam nod rightMost, sambungkan nod parentOfRightMost dengan anak kiri rightMost nod, dan padamkan nod rightMost, seperti ditunjukkan dalam Rajah di bawah (b).

Ketinggian nod di sepanjang laluan dari parentOfRightMost sehingga ke akar mungkin telah berkurangan. Untuk memastikan pokok itu seimbang, mohon

balancePath(parentOfRightMost);

Atas ialah kandungan terperinci Melaksanakan Kaedah padam. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!