avl tree implementation

การใช้งานต้นไม้ AVL ใน C ++

การใช้งาน C ++ ของต้นไม้ AVL ซึ่งเป็นแผนผังไบนารีที่มีการปรับสมดุลด้วยตนเอง รหัสประกอบด้วยฟังก์ชั่นต่อไปนี้: แทรกลบค้นหาและพิมพ์ มันทำงานได้อย่างสมบูรณ์และมีความสามารถดี

สารบัญ

• การแนะนำ
• ฟังก์ชั่น
  • แทรก
  • ลบ
  • ค้นหา
  • พิมพ์

การแนะนำ

ต้นไม้ AVL เป็นต้นไม้ค้นหาไบนารีที่มีความสมดุลด้วยตนเองซึ่งความสูงของทรีทรีย่อยเด็กสองคนของทุกโหนดนั้นแตกต่างกันมากที่สุด การใช้งานนี้ให้วิธีการที่มีประสิทธิภาพสำหรับการแทรกลบการค้นหาและองค์ประกอบการพิมพ์ภายในต้นไม้

ฟังก์ชั่น

แทรก

ฟังก์ชั่น insert ช่วยให้คุณสามารถเพิ่มค่าใหม่ให้กับต้นไม้ AVL ในขณะที่ยังคงรักษาคุณสมบัติที่สมดุลไว้

 // Function
Node * insert (Node *node, int key);

// Example
AVLTree.insert(AVLTree.root, 19 );

ลบ

ฟังก์ชั่น deleteNode จะลบค่าออกจากต้นไม้ AVL หากมีอยู่ การดำเนินการนี้ยังช่วยให้มั่นใจได้ว่าต้นไม้ยังคงมีความสมดุล หากพบและลบค่าโครงสร้างของต้นไม้จะถูกปรับตาม

 // Function
Node * deleteNode (Node *root, int key);

// Example
AVLTree.deleteNode(AVLTree.root, 16 );

ค้นหา

ฟังก์ชั่น search พบค่าในต้นไม้ AVL และพิมพ์ตำแหน่งปัจจุบันผู้ปกครองและเด็ก (ถ้ามี) หากค่าอยู่ที่รูทมันจะระบุว่า

 // Function
static void search (Node *root, int key);

// Example
Tree::search (AVLTree.root, 32 );

เอาท์พุท

พิมพ์

ฟังก์ชั่น printTree ส่งออกองค์ประกอบของต้นไม้ AVL ตามลำดับที่เรียงลำดับ

 // Function
void printTree (Node *root, int space);

// Example
AVLTree.printTree(AVLTree.root, 0 );

เอาท์พุท