คำชี้แจงปัญหา
เมื่อพิจารณาจากความสูงของต้นไม้ AVL ภารกิจคือการค้นหาจำนวนโหนดขั้นต่ำที่ต้นไม้สามารถมีได้
หากความสูง =0 แผนผัง AVL สามารถมีได้ 1 โหนด หากความสูง =5 แผนผัง AVL จะมีโหนดขั้นต่ำ 20 โหนด
อัลกอริทึม
ในแผนผัง AVL เราต้องรักษาคุณสมบัติความสมดุลของความสูง กล่าวคือ ความแตกต่างในความสูงของต้นไม้ย่อยด้านซ้ายและด้านขวาต้องไม่เกิน -1, 0 หรือ 1 สำหรับแต่ละโหนด การใช้คุณสมบัตินี้ เราสามารถสร้างความสัมพันธ์ที่เกิดซ้ำด้านล่าง -
<ก่อน>1. หากความสูง =0 ให้คืนค่า 12 หากความสูง =1 ให้คืนค่า 23 หากความสูง> 1 ให้คืนค่า (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))ตัวอย่าง
#includeใช้เนมสเปซ std;int getMinAVLNodes(int h){ if (h <0) { return 0; } if (h ==0 || h ==1) { ส่งคืน h + 1; } ส่งคืน 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2);}int main(){ int h =5; cout <<"โหนดขั้นต่ำสำหรับ" <
