Analisis Kerumitan Masa Pokok AVL

Memandangkan ketinggian pokok AVL ialah O(log n), kerumitan masa carian, sisipan dan padam kaedah dalam AVLTree ialah O(log n). Kerumitan masa kaedah carian, masukkan dan padam dalam AVLTree bergantung pada ketinggian pokok. Kita boleh membuktikan bahawa ketinggian pokok itu ialah O(log n).

Biar G(h) menyatakan bilangan minimum nod dalam pokok AVL dengan ketinggian h. Jelas sekali, G(1) ialah 1 dan G(2) ialah 2. Bilangan minimum nod dalam pokok AVL dengan ketinggian h >= 3 mesti mempunyai dua subpokok minimum: satu dengan ketinggian h - 1 dan satu lagi dengan ketinggian h - 2. Oleh itu,

G(h) = G(h - 1) + G(h - 2) + 1

Ingat bahawa nombor Fibonacci pada indeks i boleh diterangkan menggunakan hubungan ulangan F(i) = F(i - 1) + F(i - 2). Oleh itu, fungsi G(h) pada asasnya adalah sama dengan F(i). Boleh dibuktikan bahawa

h < 1.4405 log(n + 2) - 1.3277

di mana n ialah bilangan nod dalam pokok. Oleh itu, ketinggian pokok AVL ialah O(log n).

Kaedah carian, masukkan dan padam hanya melibatkan nod di sepanjang laluan dalam pokok. Kaedah updateHeight dan balanceFactor dilaksanakan dalam masa yang tetap untuk setiap nod dalam laluan. Kaedah balancePath dilaksanakan dalam masa yang tetap untuk nod dalam laluan. Oleh itu, kerumitan masa untuk kaedah carian, masukkan dan padam ialah O(log n).

Atas ialah kandungan terperinci Analisis Kerumitan Masa Pokok AVL. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!