Melaksanakan Putaran

Pokok yang tidak seimbang menjadi seimbang dengan melakukan operasi putaran yang sesuai. Bahagian, Pokok Pengimbangan Semula, menggambarkan cara melakukan putaran pada nod. Kod di bawah memberikan algoritma untuk putaran LL, seperti yang digambarkan dalam Rajah di bawah.

1 bakiLL(TreeNode A, TreeNode parentOfA) {
2 Biarkan B anak kiri A.
3
4 jika (A ialah punca)
5 Biarkan B menjadi punca baharu
6 lagi {
7 jika (A ialah anak kiri parentOfA)
8 Biarkan B menjadi anak kiri parentOfA;
9 lagi
10 Biarkan B menjadi anak yang betul kepada parentOfA;
11 }
12
13 Jadikan T2 subpokok kiri A dengan memberikan B.kanan kepada A.kiri;
14 Jadikan A anak kanan B dengan memberikan A kepada B.right;
15 Kemas kini ketinggian nod A dan nod B;
16 } // Tamat kaedah

Perhatikan bahawa ketinggian nod A dan B boleh ditukar, tetapi ketinggian nod lain dalam pokok tidak diubah. Anda boleh melaksanakan putaran RR, LR dan RL dengan cara yang sama.

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