Pokok AVL

AVL Tree ialah pokok carian binari yang seimbang. Jawatan itu memperkenalkan pepohon carian binari. Masa carian, sisipan dan pemadaman untuk pokok binari bergantung pada ketinggian pokok itu. Dalam kes yang paling teruk, ketinggiannya ialah O(n). Jika pokok seimbang sempurna–iaitu pokok binari lengkap—tingginya ialah log n. Bolehkah kita mengekalkan pokok yang seimbang dengan sempurna? Ya, tetapi berbuat demikian akan memakan kos yang tinggi. Kompromi adalah untuk mengekalkan pokok yang seimbang—iaitu, ketinggian setiap dua subpokok nod adalah lebih kurang sama.

Pokok AVL adalah seimbang. Pokok AVL telah dicipta pada tahun 1962 oleh dua saintis komputer Rusia, G. M. Adelson-Velsky dan E. M. Landis (oleh itu dinamakan AVL). Dalam pepohon AVL, perbezaan antara ketinggian setiap dua subpokok nod ialah 0 atau 1. Ia boleh ditunjukkan bahawa ketinggian maksimum pokok AVL ialah O(log n).

Proses untuk memasukkan atau memadam elemen dalam pepohon AVL adalah sama seperti dalam pepohon carian binari biasa, kecuali anda mungkin perlu mengimbangi semula pepohon itu selepas operasi pemasukan atau pemadaman. faktor keseimbangan nod ialah ketinggian subpokok kanannya tolak ketinggian subpokok kirinya. Nod dikatakan seimbang jika faktor keseimbangannya ialah -1, 0 atau 1. Nod dianggap kiri-berat jika faktor keseimbangannya -1 dan kanan-berat jika faktor keseimbangannya +1 .

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