Dictionary และ Binary Search Tree
เมื่อ Implement Abstract Data Type Dictionary โหนดจะเชื่อมโยงกับค่า (Values) Dictionary คือเซตของ Keys ที่มี Total Ordering อาจมีข้อมูลเพิ่มเติมเชื่อมกับแต่ละ Key
ถ้าใช้ Tree Implement: แต่ละโหนดเก็บ Unique Keys สำหรับโหนด u ในต้นไม้ ทุก Key ใน u.left < u.key และทุก Key ใน u.right > u.key เรียกว่า Binary Search Tree
ข้อได้เปรียบ
Sorted List ของ Keys หาได้ใน Linear Time ด้วย In-order Traversal นิยามแบบ Recursive: ถ้า Tree ว่าง ไม่ทำอะไร ไม่งั้น Recur Left Subtree ก่อน แล้ว Visit Root แล้ว Recur Right Subtree
Searching ขึ้นอยู่กับความสูงของต้นไม้ การค้นหาเป็น Operation สำคัญที่สุด
