สรุป
ไบนารีทรี
นิยามว่า ไบนารีทรี เป็น ทรีว่าง หรือทรีที่ประกอบด้วยโหนดรากที่เรียกว่า ราก กับ ไบนารีทรี 2 ทรี เรียกว่า ทรีย่อยทางซ้าย (left subtree) และ ทรีย่อยทางขวา (right subtree) ของราก การสร้างไบนารีทรี ที่มี
โหนดเดียว สามารถสร้างโหนดนั้นเป็นโหนดรากที่มีทรีย่อยทางซ้าย และทรีทางขวาเป็นทรีว่าง จะเห็นว่า
ไบนารีทรีแตก ต่างจากทรีทั่วไป เนื่องจากในไบนารีทรี ความหมายของคำว่า ซ้าย หรือ ขวา มีความสำคัญ ไบนารีทรี 2 โหนด ดังนั้นไบนารีทรีสามรถได้มาจากทรีแบบลำดับที่เหมาะสมกัน โดยการแยกกิ่งทางซ้ายออกจากกิ่งทางขวา
การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี
ไบนารีทรีเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพ แต่มีข้อจำกัดว่า แต่ละโหนดมีลูกได้ไม่เกิน 2 และในการประยุกต์ ใช้งานส่วนใหญ่ โครงสร้างข้อมูลเป็นจำนวนใดๆ ได้ตามใจ การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี
เริ่มต้นจะเชื่อมโหนด แต่ละโหนดกับโหนดลูกซ้ายสุดของโหนดนั้น ซึ่งเรียกว่าโหนดแรก ต่อมาเชื่อมแต่ละโหนดยกเว้นโหนดรากกับโหนดถัดไป ที่มีพ่อเดียวกัน(พี่น้อง) ซึ่งเรียกว่าเชื่อมโหนดลูกถัดไป
เพื่อให้โครงสร้างของไบนารีทรีที่ดีกว่านี้ จะต้องหมุนทรีเล็กน้อยตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมที่ชี้
ลงล่าง ชี้ลงไปทางซ้าย และเส้นเชื่อมที่ชี้ตามแนวนอน ชี้ลงไปข้างล่างทางขวา
ป่าและสวน
ป่า (forest) หมายถึงของทรีที่เป็นทรีแบบรก และ สวน (orchard) หมายถึง ชุดของทรีแบบลำดับ แต่โดยทั่วไป แล้วป่ากับสวนมีความหมายเดียวกัน คือ ชุดของทรีทั่วไป
สามารถสร้างป่าหรือสวนได้ โดยการขจัดรากออกไปจากทรีแบบราก หรือแบบลำดับและทำนองเดียวกัน สามารถแปลง จากป่าแสวนไปเป็นไบนารีทรีได้มีขั้นตอนดังต่อไปนี้
1.ขจัดเส้นเชื่อมเดิมออก
2.แปลงทรีแต่ละต้นให้เป็นไบนารีทรี
3.เชื่อมโหนดรากของทรีเขาด้วยกัน ในแนวนอนโดยใช้ความสัมพันธ์พี่น้อง
4.หมุนทรีที่ได้ 45 องศาตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมในแนวตั้งกลายเป็นเส้นเชื่อมทางซ้าย และเส้นเชื่อมในแนวนอนกลายเป็นเส้นเชื่อมทางขวา
การท่องไบนารีทรี (traversal of binary tree)
เป็นการเคลื่อนที่ไปยังโหนดทุกโหนดของไบนารีของทรี หรือการเยี่ยมโหนดทุกโหนดของทรี ในข้อมูล
แบบทรีโหนด ทุกโหนดที่จะท่องมีลำดับแตกต่างกัน ที่โหนดใด ไๆที่กำหนดให้จะต้องมีการกระทำ 3 อย่าง ในลำดับใดๆ คือ
1. เยี่ยมโหนดนั้น
2. ท่องไปยังทรีย่อยทางซ้ายของโหนดนั้น
3. ท่องไปยังทรีย่อยทางขวาของโหนดนั้น
จุดสำคัญของของการท่องไบนารีทรีคือ จะเยี่ยมททรีย่อยก่อนการท่องทรีย่อยที่มีอยู่ หรือจะเยี่ยมโหนดนั้นในระหว่างการท่องทรีย่อยของโหนดนั้น หรือจะเยี่ยมดหนดนั้นในระหว่างการท่องทรีย่อยภายหลังจากการท่องทรีย่อย ทั้งสองของโหนดนั้นเสร็จเรียบร้อยแล้ว
ถ้าเรากำหนดให้การเยี่ยมโหนด เป็นงาน V การท่องทรีย่อยทางซ้ายเป็น L การท่องทรีย่อยทางขวาเป็น R จึงจะ ได้วิธีการท่องทรีทั้งหมด 6 วิธี
VLR
LVR
LRV
VRL
RVL
RLV
การท่องทรีทั้ง 6 วิธีดังกล่าวเราจะลดเหลือ 3 วิธี ที่มีการท่องทรีย่อยทางซ้ายก่อนการท่องทรีย่อยทางขวา ส่วนอีก 3 วิธีที่เหลือ ก็เหมือนกับเป็นภาพกระจกเงาของ 3 วิธี ดังกล่าววิธีการท่องทรีย่อยทางซ้ายก่อนทรีย่อยทางขวา 3 วิธีดังกล่าว เรามีชื่อเรียกเฉพาะดังนี้
แบบ VLR เรียกว่า พรีออร์เดอร์ (preoder)
แบบ LVR เรียกว่า อินออร์เดอร์ (inorder)
แบบ LRV เรียกว่า โพสต์ออร์เดอร์(postorder)
การเรียกชื่อ 3 วิธีดังกล่าว จะเรียกตามลำดับการเยี่ยมโหนด V นั่นคือการท่องแบบพรีออร์เดอร์จะเยี่ยม
โหนด V ก่อนการเยี่ยมทรีย่อยทาง ซ้ายและทางขวา การท่องแบบอินออร์เดอร์จะเยี่ยมโหนด V ในระหว่างการท่องทรีย่อยทางซ้าย และทรีย่อยทางขวา และการท่องแบบโพสต์ออร์เดอร์ โหนด V จะถูกเยี่ยมหลังจากท่องทรีย่อยทางซ้ายและทางขวา มาแล้ว
การท่องแบบพรีออร์เดอร์ โหนดรากจะต้องถูกเยี่ยมเป็นอันดับแรก จากนั้นจะเคลื่อนไปท่องยังทรีย่อยทางซ้าย และจากนั้นก็จะเคลื่อนไปเยี่ยมทรีย่อยทางขวาของโหนดราก
การท่องแบบอินออร์เดอร์ ก่อนที่จะมีการเยี่ยมโหนดราก จะท่องทรีย่อยทางซ้ายของโหนดรากก่อน จากนั้นจะเคลื่อน ไปเยี่ยมโหนดราก และสุดท้ายก็จะเยี่ยมโหนดทางขวาของโหนดราก
การท่องแบบโพสต์ออร์เดอร์ จะท่องทรีย่อยทางซ้ายและทางขวาก่อนที่จะเยี่ยมโหนดราก
การประยุกต์ใช้ ไบนารีทรีกับนิพจน์ ก็สามารถจะกระทำได้ ถ้าประยุกต์ใช้แบบอินออร์เดอร์ จะได้ นิพจน์อินฟิกส์ ถ้าประยุกต์ใช้แบบโพสออร์เดอร์ จะได้นิพจน์โพสต์ฟิกส์ถ้าประยุกต์ใช้แบบพรีออร์เดอร์ จะได้นิพจน์
พรีฟิกส์
ไบนารีแบบเทรด
การท่องไบนารีแบบทรีดังข้างต้น จะมีขั้นตอนการทำงานแบบเรียกซ้ำ จึงต้องมีการใช้สแตกมาช่วย คือในขณะที่ ทำการท่องไบนารีทรี จะเก็บตำแหน่งต่าง ๆ ที่มีการเคลื่อนที่ผ่านไปไว้ในสแตก และเมื่อต้องการย้อนกลับไปทางเดิมก็จะทำ การพ็อพสแตกเพื่อนำตำแหน่งต่าง ๆออกมา
วิธีการที่ประสิทธิภาพในการท่องไบนารี โดยการให้ลิงค์ทางขวาของแต่ละโหนดที่เป็น NULL เก็บลิงค์พิเศษ ที่ชี้ไปยังโหนดที่มาตามหลังโหนดนั้นๆ ในการท่องไบนารีทรี และเรียกลิงค์พิเศษนี้ว่า "เทรดทางขวา"(right tread) การใช้เทรดทำให้การท่องทำได้ง่ายขึ้น เพราะเพียงแต่เดินตามลิงค์ธรามดา หรือเดินตามเทรดเพื่อหาโหนดถัดไป และต่อมาเมื่อสร้างเทรดทางซ้าย (left tread) ด้วยโดย ให้โหนดที่เป็นลิงค์ทางซ้ายเป็น NULL เก็บลิงค์พิเศษที่ชี้ไปยังโหนดที่มาก่อน ซึ่งจะทำให้ได้ไบนารีเทรดแบบสมบูรณ์(Fully threaded binary tree) และในทำนองเดียวกันก็สมารถสร้างเทรดแบบพรีออร์เดอร์ และโพสต์ออร์เดอร์ ได้ โดยการให้ลิงค์ทางซ้ายแทนค่าNULL ชี้ไปยังโหนดที่มาก่อนแบบพรีออร์เดอร์หรือโพสต์ออร์เดอร์และลิงค์ทางขวามีค่าเป็น NULL ชี้ไปยังโหนดที่มาทีหลัง แบบพรีออร์เดอร์ หรือ โพสต์ออร์เดอร์ ในการเขียนโปรแกรม ต้องมีวิธีการบางอย่างที่จะบอกว่าลิงค์แต่ละตัวเป็นลิงค์ที่ชี้ไปยังทรีย่อยปกติหรือเป็นเทรดที่ชี้
เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครง สร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตาม ความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน
- วงเล็บ ( )
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน
- คูณ หรือ หาร * /
- บวก หรือ ลบ + -
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การ แทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือ โหนดที่ไม่ใช่โหนดใบ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น