ตารางการเปรียบเทียบระหว่าง
Heap กับ Binary Search Tree กับ AVL tree
| Heap | Binary Search Tree | AVL Tree | |
|---|---|---|---|
|
Structure |
Complete Binary Tree |
Binary Tree |
BST + Balanced Structure |
|
Organization |
Parent dominance |
Sorted (left BST < ROOT < right BST) |
Sorted (left BST < ROOT < right BST) |
|
|
Parent > children = MAX Heap Parent < children = MIN Heap |
|
|
|
Insert |
|
Create new node |
1. Insert to BST 2. Check Balance 3. if NOT BALANCE => ROTATION |
|
Delete |
|
|
1. Search 2. Delete value 3. Check balance 4. if NOT BALANCE => ROTATION |
ตัวอย่าง AVL Tree
จะสังเกตเห็นได้ว่า ตัวที่น้อยกว่า ROOT ทุกตัวจะถูกชี้ลงทางด้านซ้าย แต่หากมากกว่า ROOT จะชี้ลงทางด้านขวา ทำต่อกันไปเรื่อย ๆ โดยในตอนที่นำข้อมูลเข้าจะมีการตรวจสอบย้อนกลับว่ามีความผิดปกติ (หนักซ้าย / ขวา) และทำการ rotation ให้มีความ Balance กันระหว่างซ้ายกับขวา การหมุนสามารถมีการหมุนครั้งเดียว (single rotation) จะมีการหมุนแบบ left rotation หรือ right rotation และการหมุน 2 ครั้ง (double rotation) โดยจะหมุนแบบ right-left-rotation หรือ left-right-rotation
