ทฤษฎีและโครงงานที่เกี่ยวข้อง
โปรแกรมช่วยการศึกษาโครงสร้างต้นไม้AVL นี้ ผู้จัดทำได้ทำการศึกษาทฤษฎีและหลักการต่างๆ ที่เกี่ยวกับโครงงาน ได้แก่ ทฤษฎีของต้นไม้ค้นหาแบบทวิภาค ทฤษฎีของต้นไม้ AVL ซึ่งทั้งสองเป็นโครงสร้างต้นไม้แบบทวิภาค โดยโครงงานนี้ใช้ภาษาจาวาในการพัฒนาโครงงานให้มีลักษณะเป็นภาพเคลื่อนไหว โดยรายละเอียดทฤษฎีต่าง ๆ จะกล่าวเป็นลำดับต่อไป
ต้นไม้ (Tree)
ต้นไม้ประกอบด้วยสมาชิกที่เรียกว่าบัพ (node) และเส้นตรง(edge) ที่เชื่อมบัพในต้นไม้ ต้นไม้ที่ไม่มีบัพจะเรียกว่าต้นไม้ว่าง (empty tree) ส่วนต้นไม้ที่ไม่ว่าง บัพแรกในโครงสร้างต้นไม้จะเรียกว่า บัพรากของต้นไม้ (root tree) สำหรับบัพอื่นๆ ที่ไม่ใช่บัพรากจะแบ่งเป็นกลุ่ม ๆ โดยแต่ละกลุ่มไม่มีบัพร่วมกันเลย ซึ่งแต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน เรียกว่า ต้นไม้ย่อย (Subtree) T1, T2,….Tn (n ³ 0)
โครงสร้างต้นไม้ AVL (AVL Tree)
ต้นไม้ AVL เป็นต้นไม้ค้นหาแบบทวิภาคชนิดพิเศษ นั่นคือมีคุณสมบัติพื้นฐานเหมือนกับต้นไม้ค้นหาแบบทวิภาค แต่คุณสมบัติที่เพิ่มเข้ามาและทำให้ต้นไม้ AVL แตกต่างจาก ต้นไม้ค้นหาแบบทวิภาคคือความสูงของต้นไม้ย่อยทางซ้ายและความสูงของต้นไม้ย่อยทางขวาของแต่ละบัพ จะต้องมีค่าความสูงต่างกันไม่เกิน 1 เสมอ
แสดงได้ | HL – HR | £1
เมื่อ HL คือความสูงของต้นไม้ย่อยทางซ้าย
HR คือความสูงของต้นไม้ย่อยทางขวา
ดังนั้นค่าความแตกต่างของความสูงของต้นไม้ย่อยทางซ้ายกับต้นไม้ย่อยทางขวาที่ทำให้สมการเป็นจริงคือ 1 , 0 หรือ –1 เท่านั้น
เมื่อเราพิจารณาตัวอย่างของโครงสร้างต้นไม้ 2 รูป ในรูปที่ 2-4 เป็นรูปต้นไม้ทวิภาคสองต้น โดยทั้งสองต้นไม้มีข้อมูลเหมือนกัน
โครงสร้างต้นไม้ทวิภาค (Binary tree)
คือต้นไม้ที่แต่ละบัพไม่สามารถมีต้นไม้ย่อยได้มากกว่า 2 หรือกล่าวอีกนัยหนึ่งคือ บัพแต่ละบัพสามารถมีบัพลูกได้ 0, 1 หรือ 2 เท่านั้น โดยบัพลูกทางซ้ายจะเรียกว่าต้นไม้ย่อยทางซ้ายและบัพลูกทางขวาจะเรียกว่าต้นไม้ย่อยทางขวา
ถ้าหากต้นไม้ทวิภาคใดมีบัพในต้นไม้ย่อยทางซ้ายเท่ากับบัพในต้นไม้ย่อยทางขวาเราจะเรียกต้นไม้ทวิภาคนี้ว่า ต้นไม้ทวิภาคสมบูรณ์ (Complete binary tree)
