Merekabentuk Kelas untuk Pokok AVL

Memandangkan pokok AVL ialah pokok carian binari, AVLTree direka bentuk sebagai subkelas BST. Pokok AVL ialah pokok binari, jadi anda boleh mentakrifkan kelas AVLTree untuk melanjutkan kelas BST, seperti ditunjukkan dalam Rajah di bawah. Kelas BST dan TreeNode ditakrifkan dalam Bahagian.

Untuk mengimbangi pokok, anda perlu mengetahui ketinggian setiap nod. Untuk kemudahan, simpan ketinggian setiap nod dalam AVLTreeNode dan takrifkan AVLTreeNode untuk menjadi subkelas BST.TreeNode. Ambil perhatian bahawa TreeNode ditakrifkan sebagai kelas dalaman statik dalam BST. AVLTreeNode akan ditakrifkan sebagai kelas dalaman statik dalam AVLTree. TreeNode mengandungi medan data elemen, kiri dan kanan, yang diwarisi oleh AVLTreeNode. Oleh itu, AVLTreeNode mengandungi empat medan data, seperti yang ditunjukkan dalam Rajah di bawah.

Dalam kelas BST, kaedah createNewNode() mencipta objek TreeNode. Kaedah ini ditindih dalam kelas AVLTree untuk mencipta AVLTreeNode. Ambil perhatian bahawa jenis pulangan kaedah createNewNode() dalam kelas BST ialah TreeNode, tetapi jenis kembalian createNewNode() kaedah dalam kelas AVLTree ialah AVLTreeNode. Ini baik, kerana AVLTreeNode ialah subkelas TreeNode.

Mencari elemen dalam AVLTree adalah sama seperti mencari dalam pokok binari biasa, jadi kaedah carian yang ditakrifkan dalam kelas BST juga berfungsi untuk AVLTree.

Kaedah masukkan dan padam ditindih untuk memasukkan dan memadam elemen dan melakukan operasi pengimbangan semula jika perlu untuk memastikan pokok itu seimbang.

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