เราจะสามารถใช้ Tree แก้ปัญหาได้ คือ 1. เราจะสามารถเก็บข้อมูลของเราไว้ตรงไหนง่ายที่สุด 2. เราจะใช้ในการตัดสินใจในการหาคำตอบที่ต้องการ 3. ควรจะ Set Code ให้มีประสิทธิภาพได้อย่างไร

การทำ Searching จะมีความสำคัญมากในการทำงาน และเป็นผลที่เกิดจากการทำงานในวิทยาการคอม
เป้าหมายแรกของการทำ Searching คือ Algorithm ที่มีประสิทธิภาพมากที่สุด และเราจะสามารถใช้
Binary Search Trees ในการทำงานนั้นได้ Binary Tree จะประกอบด้วย Child ของ Vertex (จุดยอด)
ซึ่งจะมีทั้ง Child ฝั่งขวา และ ฝั่งซ้าย ถ้าไม่ใช่ Vertex ตัว Node ของ Child ฝั่งขวาจะมีค่ามากกว่า Node
ของ Child ฝั่งซ้าย
การสร้าง Binary Search Tree จะสร้างจากค่าของ Item ที่อ่านเข้ามาค่า Key ตัวแรกจะเป็น Root จากนั้น
ก็จะต่อเติมโหนดต่าง ๆ ถ้าค่า Key หรือ Item ที่เข้ามาใหม่มีค่าน้อยกว่าโหนดที่มีอยู่แล้ว ณ จุดนั้นก็ให้ต่อ
Key ตัวนั้นให้เป็น Left Child ของโหนดตัวนั้นหรือให้เลื่อนไปเปรียบเทียบกับ Left Child ที่มีอยู่แล้ว
ในกรณีที่ค่า Input ที่เข้ามามีค่าใหญ่กว่า โหนดที่มีอยู่แล้ว ณ จุดนั้นให้นำ Key ตัวนั้นไปต่อเป็น Right Child
ของโหนดนั้นหรือเลื่อนไปเรื่อยๆ จนกว่าจะหมด Input ที่เข้า
ยกตัวอย่างเช่น ให้ Input ที่เข้ามาคือ [Mathematics],[Physics],[Geography],[Zoology],[Meteorology],
[Geology],[Psychology] และ [Chemistry] โดยใช้หลัก Alphabetical Order(เรียงลำดับตามตัวอักษร)
วิธีทำ
ตัวที่เข้าตัวแรกจะเป็น Root หรือ Vertex ดังนั้น [Math] จะเป็นโหนดแรกดังรูป Key ตัวต่อไปที่เข้ามาคือ
[Physics] ซึ่ง > [Math] จึงอยู่ทางขวาของ [Math] Key ต่อไป คือ [Geography] ซึ่ง < [Math] จึงใส่ไว้ทาง
ซ้ายของโหนด ต่อไป Key ที่เข้ามาคือ [Zoology] ซึ่ง > [Math] จึงอยู่ทาง Child ฝั่งขวาเปรียบเทียบกับ Key
ตัวต่อไปคือ [Physics] ซึ่ง [Zoology] > [Physics] จึงใส่ไว้ทางขวาของโหนด [Physics] และทำการเปรียบเทียบ
เช่นนี้ไปเรื่อยๆจนหมด Input ที่เข้ามา ดังรูป

Binary Search Trees Algorithm

จาก Algorithm1 อธิบาย กำหนด T คือ Binary Search Tree , x คือ Item หรือ Input ที่เข้ามา , v คือ Root ของ Tree
เงื่อนไข ค่าของ v ต้องไม่เท่ากับ Null(ไม่มีค่า) และค่าของ v ต้องไม่เท่ากับ x
เริ่มต้น
ถ้า x < v แล้วถ้า Child ด้านซ้ายของ v ไม่เท่ากับ Null แล้ว ให้ใส่ค่า x นั้นไว้ที่ Left Child ของ v
แต่ถ้า Child ด้านซ้ายของ v เท่ากับ Null ให้นำค่า x ตั้งเป็นจุดยอดใหม่ใน Left Child ของ v
ถ้า x < v แล้วถ้า Child ด้านขวาของ v ไม่เท่ากับ Null แล้ว ให้ใส่ค่า x นั้นไว้ที่ Right Child ของ v
แต่ถ้า Child ด้านขวาของ v เท่ากับ Null ให้นำค่า x ตั้งเป็นจุดยอดใหม่เป็น Right Child ของ v
จบ Loop
ถ้า Root ของ T เท่ากับ Null แล้ว เพิ่ม r เป็น Vertex และ ค่าของ r คือ x
แต่ถ้า Root ของ T ไม่เท่ากับ Null และถ้าค่าของ v ไม่เท่ากับค่า x ค่า Vertex ตัวใหม่คือ x ( x คือ Root ตัวใหม่ )

ถ้า Binary Search Trees คือ Tree ที่ใช้เปรียบเทียบการวางตำแหน่งของ Input ที่เข้ามาแล้ว การที่เรานำ Tree ไปใช้
แก้ปัญหา โดยที่ Root คือ ปัญหาและเราจะหาทางแก้ปัญหาที่ดีที่สุดโดยใช้ Tree เข้าช่วยเราเรียกว่า Decision Tree เพื่อที่จะหาคำตอบที่เป็นไปได้ที่สอดคล้องกับปัญหา (Root)
ตัวอย่างเช่น ปัญหาคือ มีเหรียญทั้งหมด 8 เหรียญ แต่มี 7 เหรียญที่มีน้ำหนักเท่ากัน และมีหนึ่งเหรียญที่เป็นเหรียญปลอม
และมีน้ำหนักเบาที่สุด ให้หาเหรียญปลอมเหรียญนั้น โดยกำหนดให้ใช้เครื่องชั่งแบบ Balance
วิธีทำ
สุ่มแบ่งเหรียญเป็น 3 กอง กองละ 3 , 3 , 2 เหรียญตามลำดับ จากนั้นนำเหรียญกองที่มี 3 เหรียญ 2 กองมาชั่ง
ผลลัพธ์จะมี 3 กรณีคือ
1. เหรียญ 2 กองมีน้ำหนักเท่ากัน
2. กองฝั่งซ้ายเบากว่า
3. กองฝั่งขวาเบากว่า
เราจะพิจารณาทีละกรณี
กรณีที่1 -ถ้าเหรียญ 2 กองมีน้ำหนักเท่ากัน แสดงว่าไม่มีเหรียญที่เบากว่า(เหรียญปลอม)อยู่ใน2กองนี้ เพราะฉะนั้น
จะเหลือกองที่มี 2 เหรียญ ถ้านำมาชั่งเปรียบเทียบกันจะรู้ว่าเหรียญปลอมคือเหรียญใด จากข้างที่มีน้ำหนักเบากว่า
กรณีที่2 - ถ้ากองฝั่งซ้ายเบากว่า แสดงว่ากองฝั่งขวาและกองที่มี2เหรียญเป็นเหรียญจริง เพราะเหรียญปลอมที่มี
น้ำหนักเบาอยู่กองฝั่งซ้าย เราจะคิดเฉพาะกองฝั่งซ้ายให้สุ่มเลือกเหรียญ 2 เหรียญออกมาจากกองแล้วนำไปชั่ง
เปรียบเทียบกัน ถ้ามีน้ำหนักเท่ากันแลดงว่าเหรียญที่เหลือ 1 เหรียญที่ไม่ได้นำมาชั่งเป็นเหรียญปลอม แต่ถ้าไม่เท่ากันเหรียญข้างที่เบากว่าคือ เหรียญปลอม
กรณีที่3 - ถ้ากองฝั่งขวาเบากว่า กรณีนี้จะคล้ายกรณีที่2คือ แสดงว่ากองฝั่งซ้ายและกองที่มี2เหรียญเป็นเหรียญจริง
เพราะเหรียญปลอมที่มีน้ำหนักเบาอยู่กองฝั่งขวา เราจะคิดเฉพาะกองฝั่งขวา ให้สุ่มเลือกเหรียญ 2 เหรียญออกมา
จากกองแล้วนำไปชั่งเปรียบเทียบกัน ถ้ามีน้ำหนักเท่ากันแลดงว่าเหรียญที่เหลือ 1 เหรียญที่ไม่ได้นำมาชั่งเป็น
เหรียญปลอม แต่ถ้าไม่เท่ากันเหรียญข้างที่เบากว่าคือ เหรียญปลอม
จากการแก้ปัญหาที่ผ่านมาเราสามารถใช้ Decision Tree ในการแก้ปัญหาได้อย่างมีประสิทธิภาพโดยแสดงได้ดังรูป

เมื่อเราพิจรณาปัญหาเรื่องการแปลง Bit เป็นตัวอักษรภาษาอังกฤษ (โดยไม่แบ่งแยกระหว่างตัวอักษรเล็กกับใหญ่)
เราสามารถแทนตัวอักษรเหล่านี้ได้ด้วย Bit 5 หลัก จึงทำให้จำนวน Bit ที่ใช้ในการแปลงจะเป็น 5 เท่าของตัวอักษร
ในข้อความนั้นๆ(ยาวไป)
เป็นไปได้หรือไม่ที่จะหาหลักการแปลง Bit โดยให้มีจำนวน Bit น้อยกว่านี้ ? ถ้าทำได้เราจะสามารถประหยัด
Memory และเวลาในการแปลงไปได้มาก
เราสามารถทำได้โดยพิจรณาที่การใช้ Bit ซึ่งมีจำนวนหลักแตกต่างกันในการแปลงตัวอักษรโดยที่ตัวอักษรที่ต้องใช้
บ่อยๆเราก็จะใช้จำนวน Bit สั้นๆและใช้จำนวน Bit ยาวๆสำหรับอักษรที่ไม่ค่อยได้ใช้ แต่จะเกิดปัญหาขึ้นเมื่อเราแปลง
ตัวอักษรเนื่องจากเราจะไม่มีทางรู้ได้ว่า Bit ในช่วงหนึ่งๆจะเป็นตัวอักษรอะไร ตัวอย่างเช่น ให้ 0 แทนอักษร e , 1 แทน a
และ 01 แทน t เมื่อเราเจอ Bit ในลักษณะ 0101 ทำให้มันมีความหมายมากมายคือ eat , tea ,eaea หรือ tt
การที่จะทำให้ Bit เหล่านี้มีความหมายเดียว จะต้องทำให้ Bit ของอักษรตัวหนึ่งต้องไม่เหมือนกับ Bit แรกของ
ตัวอักษรอื่นๆ วิธีการนี้เรียกว่า Prefix Codes
ตัวอย่าง
ให้ 0 แทนอักษร e , 10 แทน a และ 11 แทน t แบบนี้จึงเป็น Prefix Codes และสามารถแปลงออกมาได้เป็นข้อความเดียว
กันเท่านั้น เช่น 10110 คือ ate อย่างเดียวไม่สามารถเป็นคำอื่นๆได้ จะเห็นได้ว่า Bit ในแต่ละตัวอักษรจะไม่เหมือนกับ
Bit แรกของกันและกัน (เช่น 10 จะไม่ปรากฎอยู่ใน 2 Bit แรกของตัวอักษรอื่น)
Prefix Codes สามารถเขียนอยู่ในรูปของ Binary Tree ได้โดนให้ตัวอักษรแต่ละตัวอยู่ที่ Leaf แต่ละ Leaf ของ Tree นั้น
โดนให้ด้านของ Tree ที่เชื่อมกับ Left Child เป็น 0 และที่เชื่อมกับ Right Child เป็น 1 จะทำให้เราสามารถแปลงตัวอักษร
เป็น Bit หรือแปลง Bit เป็นตัวอักษรได้โดยเริ่มต้นที่ Root ของ Tree ทุกครั้ง
ตัวอย่าง
ให้ อักษร e แทน 0 , a แทน 10 , t แทน 110 , n แทน 1110 , s แทน 1111 จะเขียนเป็น Tree ได้ดังรูป

เมื่อเราต้องการแปลง Bit เป็นตัวอักษรจาก Code 11111011100 เริ่มต้นดูที่ Root ของ Tree แล้วก็ไล่ลงมาตาม
ด้านที่ตรงกับตัวเลขถัดไปดังนี้ ที่ Root ไล่ไปตามด้าน 1 จะพบกับจุดแยกก็ให้ไล่ต่อไปตาม Bit ตัวถัดมา
จะได้ว่า 1 -> 1 -> 1 -> 1 -> s เมื่อได้ตัวอักษรแล้วก็ให้กลับไปเริ่มที่ Root ใหม่เสมอ เราก็จะได้อักษรต่อๆไปดังนี้
1 -> 0 -> a , 1 -> 1 -> 1 -> 0 -> n , 0 -> e จะได้คำว่า sane เป็นต้น

1. จงสร้าง Binary Search Tree สำหรับคำเหล่านี้ banana , peach , apple , pear , coconut , mango และ papaya
โดยใช้หลักการ Alphabetical Order (เรียงลำดับตามตัวอักษร)
ทำก่อนสัก 5 นาที..........แล้วดูเฉลย
2. จงสร้าง Binary Search Tree สำหรับคำเหล่านี้ oenology , phrenology , campanolog , ornithology , inchthyology ,
limnology , alchemy และ astrology โดยใช้หลักการ Alphabetical Order (เรียงลำดับตามตัวอักษร)
ทำก่อนสัก 5 นาที..........แล้วดูเฉลย
3. จงหาจำนวนครั้งที่ต้องเปรียบเทียบในการบอกที่อยู่ หรือเพิ่มคำต่อไปนี้โดยใช้ Tree ของโจทย์ข้อแรกเป็นหลัก
a) pear
b) banana
c) kumquat
d) orange
ทำก่อนนะ..........แล้วดูเฉลย
4. จงหาจำนวนครั้งที่ต้องเปรียบเทียบในการบอกที่อยู่ หรือเพิ่มคำต่อไปนี้โดยใช้ Tree ของโจทย์ข้อ 2 เป็นหลัก
a) palmistry
b) etymology
c) paleontology
d) glaciology
ทำก่อนนะ..........แล้วดูเฉลย
5. ใช้หลักการ Alphabetical Order (เรียงลำดับตามตัวอักษร) ในการสร้าง Binary Search Tree สำหรับคำต่างๆใน
ประโยคต่อไปนี้ "The quick brown fox jumps over the lazy dog."
ทำไปเรื่อยๆถ้าคิดไม่ออกก็..........ดูเฉลย
6. จงหาจำนวนครั้งที่ต้องชั่งสำหรับตาชั่งแบบ Balance Scale เพื่อที่จะหาเหรียญปลอมที่เบากว่าเหรียญจริง จาก
เหรียญทั้งหมด 4 เหรียญพร้อมทั้งบรรยายวิธีการหาด้วย
ทำนานหน่อยคิดดีๆล่ะ..........แล้วดูเฉลย
7. จงหาจำนวนครั้งที่ต้องชั่งสำหรับตาชั่งแบบ Balance Scale เพื่อที่จะหาเหรียญปลอมที่อาจจะเบากว่า หรือ หนักกว่า
เหรียญจริง จาก เหรียญทั้งหมด 4 เหรียญพร้อมทั้งบรรยายวิธีการหาด้วย
ทำสัก 10 นาทีคิดดีๆล่ะ..........แล้วดูเฉลย
8. จงหาว่า Code ต่อไปนี้ Code ไหนเป็น Prefix Codes
a) a:11 , e:00 , t:10 , s:01
b) a:0 , e:1 , t:01 , s:001
c) a:101 , e:11 , t:001 , s:011 , n:010
d) a:010 , e:11 , t:011 , s:1011 , n:1001 , i:10101
คิดดีๆ..........แล้วดูเฉลย
9. จงสร้าง Binary Tree โดยใช้ Prefix Code จากหลักการแปลงต่อไปนี้
a) a:11 , e:0 , t:101 , s:100
b) a:1 , e:01 , t:001 , s:0001 , n:00001
c) a:1010 , e:0 , t:11 , s:1011 , n:1001 , i:100001
ทำสัก 10 นาที..........แล้วดูเฉลย
10. ให้หลักการแปลงดังต่อไปนี้ a:001 , b:0001 , e:1 , r:0000 , s:0100 , t:011 , x:01010
จาหาคำจาก Code ต่อไปนี้
a) 01110100011
b) 0001110000
c) 0100101010
d) 01100101010
ทำสัก 5 นาที..........แล้วดูเฉลย