Sorting
ถ้าเราจำเป็นต้องเก็บและค้นหาข้อมูลอยู่เป็นประจำ การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบ และง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุด ต้องมีการจัดการกับรายละเอียดของหนังสือต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามตัวอักษร เป็นต้น
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
1.การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
2.การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
การเรียงลำดับแบบตัวเลือก
หลักการดังนี้ คือ การเลือกข้อมูลที่มีค่าที่น้อยที่สุดในแถวลำดับ และนำค่านั้นไปเปลี่ยนที่กับข้อมูลที่บรรจุ อยู่ในแถวลำดับช่องแรก ต่อมามีการเลือกค่าที่มากกว่า และนำค่านั้นไปแลกกับข้อมูลในแถวลำดับช่องที่สอง ขั้นตอนนี้เหมือนกันกับขั้นตอนแรก ยกเว้นจะไม่มีการเปรียบเทียบกับ ข้อมูลในแถวลำดับช่องแรก เพราะรู้แล้วว่าเป็นค่าที่น้อยที่สุด ต่อจากนั้นจะมีการดำเนินงานแบบเดิม คือ เลือกตัวที่มีค่าน้อยที่สุดในบรรดา ข้อมูลที่เหลือแล้วมีการสลับที่ จนกระทั่งค่าทั้งหมดที่อยู่ในแถวลำดับมีการเรียงลำดับ และจะพบว่าที่ ส่วนแรกของแถวลำดับ ประกอบด้วยค่าน้อยที่สุด และที่ปลายสุดของแถวลำดับมีค่ามากที่สุด
การเรียงลำดับแบบฟอง
มีหลักการแตกต่างไปจาก การเรียงลำดับแบบเลือก โดยปกติวิธีการนี้จะมีการเปรียบเทียบน้อยกว่าวิธีที่กล่าวมาแล้ว แต่วิธีนี้จะมีการสลับที่มากกว่า การเรียงลำดับแบบเลือก และใช้เวลาในการทำงานมากกว่า
การเรียงลำดับวิธีนี้เริ่มโดย จะมีการเปรียบเทียบข้อมูลในแถวลำดับ ช่องแรกกับช่องถัดไป ถ้าช่องหลังมีข้อมูลขนาดใหญ่กว่า จึงเปลี่ยนที่ระหว่างช่องแรกและช่องที่สอง ต่อมามีการเปรียบเทียบระหว่างช่องที่สองกับช่องที่ 3 ถ้าช่องที่ 3 ข้อมูลมีค่ามากกว่าช่องที่ 2 มีการสลับที่ แล้วมีการเปรียบเทียบระหว่างช่องที่ 3 กับช่องที่ 4 และช่องที่ 4 กับช่องที่ 5 และมีการสลับที่นำตัวที่มีค่ามากกว่า ไว้ทางซ้ายมือ จนกระทั่งการเปรียบเทียบเกิดกับ ทุกตัวในแถวลำดับ ขั้นต่อไปมีการเปรียบเทียบอีก แล้วมีการสลับค่าจนครบทุกค่าของแถวลำดับ แต่อย่างไรก็ตามหลังจากที่มีการเปรียบเทียบ และสลับค่าครบรอบแล้วพบว่าค่าที่น้อยที่สุด จะไปอยู่ที่แถวลำดับช่อง ขวาสุด ดังนั้นจึงไม่จำเป็นต้องมีการเปรียบเทียบ กับแถวลำดับช่องนี้ในการเรียงลำดับค่ารอบต่อไป ต่อมาการเปรียบเทียบ และการเปลี่ยนค่าก็ดำเนินงานอีก โดยเว้นการเปรียบเทียบกับสองค่าสุดท้ายทาง ขวาสุดของแถวลำดับ แล้วมีการเปรียบเทียบและสลับที่เกิดขึ้นอีก โดยเว้นสามค่าสุดท้าย จะมีการเปรียบ เทียบและสลับที่ไปเรื่อย ๆ และท้ายที่สุดก็จะได้ข้อมูลในแถวลำดับ เรียงลำดับจากค่ามากสุดไปน้อยสุด
การเรียงลำดับแบบเร็ว
การเรียงลำดับแบบเร็ว (quick sort) เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้วใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็น สองส่วน ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน และอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมดจะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป จนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการ
การเรียงลำดับแบบแทรก
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกเข้าไปใหม่ในเซต ที่มีสมาชิกทุกตังเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับอยู่แล้วด้วย วิธีการเรียงลำดับ
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่1 กับ 2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้ถ้าเป็นการเรียงลำดับจากน้อยไปหามาก
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตัวแหน่งก่อน
การเรียงลำดับแบบฐาน
การเรียงลำดับแบบฐาน (radix sort) เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆ ตามลำดับการเข้ามา ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
วันพฤหัสบดีที่ 24 กันยายน พ.ศ. 2552
DTS09-01-09-2552
Graph
กราฟ Graph เป็นโครงสร้างข้อมุลแบบไม่เชิงเส้น อีกชนิดหนี่ง กราฟเป็นดครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ไขปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤต และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
1. โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edger) การเชื่อมต่อ กราฟที่มีเอ็จเชื่อมต่อระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Garphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า การฟแบบมีทิศทาง
(Directed Deaphs) หรือมีลูกศร เป็นกราฟที่แสดงการเชื่อม ระหว่าง Vertex โดยแสดงทิศทางการเชื่อมต่อด้วย บางครั้งเรียกว่า ไดกราฟ (Digraph) ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัวการสากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนดได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใดๆ สามารถวนเข้ามาหาตัวมันเองได้
โดยทั่วๆไป การเขียนกราฟเพื่อแสดงให้เห็นด้วยความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วยจุด (Pointes) หรือวงกลม (circles) ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง(Empty Graph) แต่ละเอ็จชะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง อ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node)
หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจว่างไม่มีโหนดหรือเอ็จเลยป็นกราฟว่าง(Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (Source Node)และโหนดสิ้นสุด (Target Node)
รูปแบบต่างๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบ ของกราฟแบบไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนที่กราฟในหน่วยความจำ
ในการปฎิบัติการกับโครงสร้างกราฟ สื่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างดหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การแทนที่กราฟด้วยเมตริกซ์
โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1
ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ
ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง
ตัวอย่างจากรูปกราฟแบบ Direct Graph
สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้
หากเป็นกราฟแบบ Undirected Graph
การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix
จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้
กราฟ Graph เป็นโครงสร้างข้อมุลแบบไม่เชิงเส้น อีกชนิดหนี่ง กราฟเป็นดครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ไขปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤต และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
1. โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edger) การเชื่อมต่อ กราฟที่มีเอ็จเชื่อมต่อระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Garphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า การฟแบบมีทิศทาง
(Directed Deaphs) หรือมีลูกศร เป็นกราฟที่แสดงการเชื่อม ระหว่าง Vertex โดยแสดงทิศทางการเชื่อมต่อด้วย บางครั้งเรียกว่า ไดกราฟ (Digraph) ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัวการสากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนดได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใดๆ สามารถวนเข้ามาหาตัวมันเองได้
โดยทั่วๆไป การเขียนกราฟเพื่อแสดงให้เห็นด้วยความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วยจุด (Pointes) หรือวงกลม (circles) ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง(Empty Graph) แต่ละเอ็จชะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง อ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node)
หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจว่างไม่มีโหนดหรือเอ็จเลยป็นกราฟว่าง(Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (Source Node)และโหนดสิ้นสุด (Target Node)
รูปแบบต่างๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบ ของกราฟแบบไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนที่กราฟในหน่วยความจำ
ในการปฎิบัติการกับโครงสร้างกราฟ สื่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างดหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การแทนที่กราฟด้วยเมตริกซ์
โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1
ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ
ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง
ตัวอย่างจากรูปกราฟแบบ Direct Graph
สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้
หากเป็นกราฟแบบ Undirected Graph
การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix
จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้
DTS08-25-08-2552
Tree (ทรี)
ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings) โหนดที่ไม่มีโหนดลูกเรียกว่า โหนดใบ (Leave Node) เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดเรียกว่า กิ่ง (Beanch) คือ โหนดที่ไม่ใช่ Leaf Node
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกัน ทางเดียวกันนั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N -1เส้น
การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบ คือ
1. แบบที่มีรากอยู่ด้านบน
2. แบบที่มีรากอยู่ด้านล่าง
3. แบบที่มีรากอยู่ด้านซ้าย
4. แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบเคอร์ซีฟ คือ การเรียกตัวเองมาใช้ โหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)
T1,T2,T3,....,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) ป่า หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน (ordered Tree) ทรีแบบลำดับ หมายถึง ทรีที่โหนดต่างๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ปทางขวา ไปทางซ้าย เป็นต้น
3. ทรีคล้าย (similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือทรีที่เหมือนกันโดยสมบูณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึงจำนวนย่อยของโหนด นั้นๆ
6. ระดับของโหนด (Level of Node) คือระยะทางในแนวดิ่งของโหนดนั้นๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดและจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสุง( Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลัก จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวนลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรี ซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการ วิธีการแทนที่ที่ง่ายที่สุด คือ ทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์เท่ากัน โดยอาจใช้วิธีการต่อไปนี้
1. แต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
2. แทนทรีด้วยไบนารีทรี เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำ
ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบและโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree) สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ ถ้ากำหนดให้ L คือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ 4 มีจำนวนโหนด 15 โหนด
ระดับ L มีจำนวนโหนด 2L – 1 โหนด
นั่นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่มี L ระดับสามารถคำนวณได้จากสูตรดังนี้
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลงดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในทรี
การท่องไปในไบนารีทรี (Traversing Binary Tree) คือ การเข้าไปเยือนทุก ๆ โหนดในทรี วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบ โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R) วิธีการท่องเข้าไปในทรีมี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปในทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก คือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ (Recursive) ขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์ (Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR
2. การท่องไปแบบอินออร์เดอร์ (Inorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR 3. การท่องไปแบบโพสออร์เดอร์ (Postorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LRN
เอ็กซ์เพรสชันทรี
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ (Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression) นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วย โดยมีความสำคัญตามลำดับดังนี้
1. ฟังก์ชัน
2. วงเล็บ
3. ยกกำลัง
4. ครื่องหมายหน้าเลขจำนวน (unary)
5. คูณ หรือ หาร
6. บวก หรือ ลบ
7. ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บในโหนดกิ่ง หรือโหนดที่ไม่ใช่โหนดใบ เช่น นิพจน์ A + B
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา และในแต่ละทรีย่อยก็มีคุณสมบัติเช่นเดียวกัน ค่าข้อมูลในทรีย่อยทางซ้าย < ค่าข้อมูลที่โหนดราก < ค่าข้อมูลในทรีย่อยทางขวา ปฏิบัติการในไบนารีเซิร์ชทรี เพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีเซิร์ชทรี ค่อนข้างยุ่งยาก เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้ว ต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีทรีนั้นด้วย ซึ่งมีปฏิบัติการดังต่อไปนี้
1. การเพิ่มโหนดในไบนารีเซิร์ชทรี
2. การดึงโหนดในไบนารีเซิร์ชทรี
ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบ
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวา
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้าย ต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น
ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings) โหนดที่ไม่มีโหนดลูกเรียกว่า โหนดใบ (Leave Node) เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดเรียกว่า กิ่ง (Beanch) คือ โหนดที่ไม่ใช่ Leaf Node
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกัน ทางเดียวกันนั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N -1เส้น
การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบ คือ
1. แบบที่มีรากอยู่ด้านบน
2. แบบที่มีรากอยู่ด้านล่าง
3. แบบที่มีรากอยู่ด้านซ้าย
4. แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบเคอร์ซีฟ คือ การเรียกตัวเองมาใช้ โหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)
T1,T2,T3,....,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) ป่า หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน (ordered Tree) ทรีแบบลำดับ หมายถึง ทรีที่โหนดต่างๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ปทางขวา ไปทางซ้าย เป็นต้น
3. ทรีคล้าย (similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือทรีที่เหมือนกันโดยสมบูณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึงจำนวนย่อยของโหนด นั้นๆ
6. ระดับของโหนด (Level of Node) คือระยะทางในแนวดิ่งของโหนดนั้นๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดและจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสุง( Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลัก จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวนลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรี ซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการ วิธีการแทนที่ที่ง่ายที่สุด คือ ทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์เท่ากัน โดยอาจใช้วิธีการต่อไปนี้
1. แต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
2. แทนทรีด้วยไบนารีทรี เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำ
ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบและโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree) สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ ถ้ากำหนดให้ L คือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ 4 มีจำนวนโหนด 15 โหนด
ระดับ L มีจำนวนโหนด 2L – 1 โหนด
นั่นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่มี L ระดับสามารถคำนวณได้จากสูตรดังนี้
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลงดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในทรี
การท่องไปในไบนารีทรี (Traversing Binary Tree) คือ การเข้าไปเยือนทุก ๆ โหนดในทรี วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบ โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R) วิธีการท่องเข้าไปในทรีมี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปในทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก คือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ (Recursive) ขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์ (Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR
2. การท่องไปแบบอินออร์เดอร์ (Inorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR 3. การท่องไปแบบโพสออร์เดอร์ (Postorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LRN
เอ็กซ์เพรสชันทรี
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ (Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression) นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วย โดยมีความสำคัญตามลำดับดังนี้
1. ฟังก์ชัน
2. วงเล็บ
3. ยกกำลัง
4. ครื่องหมายหน้าเลขจำนวน (unary)
5. คูณ หรือ หาร
6. บวก หรือ ลบ
7. ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บในโหนดกิ่ง หรือโหนดที่ไม่ใช่โหนดใบ เช่น นิพจน์ A + B
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา และในแต่ละทรีย่อยก็มีคุณสมบัติเช่นเดียวกัน ค่าข้อมูลในทรีย่อยทางซ้าย < ค่าข้อมูลที่โหนดราก < ค่าข้อมูลในทรีย่อยทางขวา ปฏิบัติการในไบนารีเซิร์ชทรี เพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีเซิร์ชทรี ค่อนข้างยุ่งยาก เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้ว ต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีทรีนั้นด้วย ซึ่งมีปฏิบัติการดังต่อไปนี้
1. การเพิ่มโหนดในไบนารีเซิร์ชทรี
2. การดึงโหนดในไบนารีเซิร์ชทรี
ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบ
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวา
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้าย ต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น
สมัครสมาชิก:
บทความ (Atom)