ที่นี่เราจะเห็นต้นไม้การค้นหาและความแตกต่าง มีต้นไม้ค้นหาที่แตกต่างกันมากมาย มีลักษณะแตกต่างกัน โครงสร้างการค้นหาพื้นฐานคือ Binary Search Tree (BST) ต้นไม้การค้นหาอื่นๆ ได้แก่ ต้นไม้ AVL ต้นไม้ B ต้นไม้สีแดง-ดำ ต้นไม้กระจาย ฯลฯ
ต้นไม้เหล่านี้สามารถเปรียบเทียบได้ตามการดำเนินงาน เราจะเห็นความซับซ้อนของเวลาของต้นไม้เหล่านี้
| แผนผังการค้นหา | ตัวพิมพ์เฉลี่ย | ||
|---|---|---|---|
| | แทรก | ลบ | ค้นหา |
| แผนผังการค้นหาไบนารี | O(ล็อก n) | O(ล็อก n) | O(ล็อก n) |
| ต้นไม้ AVL | O(log2 น) | O(log2 น) | O(log2 น) |
| B Tree | O(ล็อก n) | O(ล็อก n) | O(ล็อก n) |
| ต้นไม้แดง-ดำ | O(ล็อก n) | O(ล็อก n) | O(ล็อก n) |
| Splay Tree | O(log2 น) | O(log2 น) | O(log2 น) |
| แผนผังการค้นหา | กรณีที่แย่ที่สุด | ||
|---|---|---|---|
| | แทรก | ลบ | ค้นหา |
| แผนผังการค้นหาไบนารี | O(n) | O(n) | O(n) |
| ต้นไม้ AVL | O(log2 น) | O(log2 น) | O(log2 น) |
| B Tree | O(ล็อก n) | O(ล็อก n) | O(ล็อก n) |
| ต้นไม้แดง-ดำ | O(ล็อก n) | O(ล็อก n) | O(ล็อก n) |
| Splay Tree | O(log2 น) | O(log2 น) | O(log2 น) |
