Sorting
การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถกระทำได้รวดเร็วและมีประสิทธิภาพ เช่น การค้นหาความหมายของคำในพจนานุกรม ทำได้ค่อนข้างง่ายและรวดเร็วเนื่องจากมีการเรียงลำดับคำตามตัวอักษรไว้อย่างมีระบบและเป็นระเบียบ หรือ การค้นหาหมายเลขโทรศัพท์ในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของเจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลขโทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ว เป็นต้น
การเรียงลำดับอย่างมีประสิทธิภาพหลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่ดี และเหมาะสมกับระบบงาน เพื่อให้ประสิทธิภาพในการทำงานสูงสุด ควรจะต้องคำนึงถึงสิ่งต่าง ๆ ดังต่อไปนี้
(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่
วิธีการเรียงลำดับเนื่องจากมีวิธีการมากมายที่สามารถใช้ในการเรียงลำดับข้อมูลได้ บางวิธีก็มีขั้นตอนการจัดเรียงเป็นแบบง่าย ๆ ตรงไปตรงมา แต่ใช้เวลาในการจัดเรียงลำดับนาน และบางวิธีก็มีขั้นตอนในการจัดเรียงลำดับแบบซับซ้อนยุ่งยากแต่ใช้เวลาในการจัดเรียงไม่นานนัก ดังนั้นจึงควรศึกษาวิธีการจัดเรียงลำดับด้วยวิธีการต่าง ๆ เพื่อเลือกใช้วิธีการที่ดีและเหมาะสมกับระบบงานนั้นที่สุด
วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่าง
การถ่ายเทข้อมูลจากหน่วยความจำหลักและหน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้ในการเรียงลำดับข้อมูลแบบภายใน
การเรียงลำดับแบบเลือก (selection sort)ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่าในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ
ในการเรียงลำดับข้อมูลแบบภายใน
การเรียงลำดับแบบฟอง (Bubble Sort)เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มีค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
วันพุธที่ 9 กันยายน พ.ศ. 2552
DTS09-02-09-2552
เรื่อง ทรี(ต่อ) และเรื่องกราฟ
ไบนารี่เสิร์ชทรี
ไบนารี่เสิร์ชทรี (Binary Search Tree, BST) เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์ (Key) ตั้งแต่ K1 , K2 ,…….Kn โดยแต่ละโหนด Ri จะมี Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier) ให้แต่ละโหนด ในการค้นหาโหนดที่ต้องการจะกระทำโดยค้นหาค่าของคีย์ และโหนด Ri ของไบนารี่เสิร์ชทรีจะถูกจัดการตามคุณสมบัติ ดังนี้
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านซ้ายของ Ri เป็นค่าที่มาก่อนหรือน้อยกว่าคีย์ของ Ri If Ri € Left (Ri) Then Kj <>
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านขวาของ Ri เป็นค่าที่ตามหลังหรือมากกว่าคีย์ของ Ri
If Ri € Right (Ri) Then Kj > Kiจะไดว่าคีย์ที่มาก่อนจะถูกพิจารณาตามลำดับเชิงเส้นและขึ้นกับลำดับการรวบรวม เมื่อพิจารณาตามคุณสมบัติที่ผ่านมาการค้นหาจะได้คีย์ A,B,C,D ตามลำดับและมีหลายวิธีที่จะจัดการกับไบนารี่เสิร์ชทรี จากรูปดังกล่าวจะมีไบนารี่เสิร์ชทรีหลายแบบแต่ลำดับของคีย์เหมือนกัน
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออกกราฟ (Graph)
เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนดกราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้G = ( V , E )G คือ กราฟV คือ กลุ่มของ vertexE คือ กลุ่มของ edgeศัพท์ที่เกี่ยวข้อง
1.เวอร์เทก (Vertex) หมายถึง โหนด
2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด
3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน
Graph แบ่งเป็น
1. Directed Graph (Digraph) (Arc) แบบระบุทิศทาง
2. Undirected Graph แบบไม่ระบุทิศทาง
การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้
1. Adjacency Matrix (แอดจาเซนซี เมตริก) : ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List (แอดจาเซนซี ลิส) : ใช้ลิงค์ลิสต์เก็บข้อมูลAdjacency Matrixเป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x nMk เป็นเมทริกซ์ของกราฟใด ๆ k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่งAdjacency Matrix 0 : ไม่เป็นแอดจาเซนซีกัน1 : เป็นแอดจาเซนซีกัน
การท่องไปในกราฟเป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย
การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ
ไบนารี่เสิร์ชทรี
ไบนารี่เสิร์ชทรี (Binary Search Tree, BST) เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์ (Key) ตั้งแต่ K1 , K2 ,…….Kn โดยแต่ละโหนด Ri จะมี Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier) ให้แต่ละโหนด ในการค้นหาโหนดที่ต้องการจะกระทำโดยค้นหาค่าของคีย์ และโหนด Ri ของไบนารี่เสิร์ชทรีจะถูกจัดการตามคุณสมบัติ ดังนี้
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านซ้ายของ Ri เป็นค่าที่มาก่อนหรือน้อยกว่าคีย์ของ Ri If Ri € Left (Ri) Then Kj <>
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านขวาของ Ri เป็นค่าที่ตามหลังหรือมากกว่าคีย์ของ Ri
If Ri € Right (Ri) Then Kj > Kiจะไดว่าคีย์ที่มาก่อนจะถูกพิจารณาตามลำดับเชิงเส้นและขึ้นกับลำดับการรวบรวม เมื่อพิจารณาตามคุณสมบัติที่ผ่านมาการค้นหาจะได้คีย์ A,B,C,D ตามลำดับและมีหลายวิธีที่จะจัดการกับไบนารี่เสิร์ชทรี จากรูปดังกล่าวจะมีไบนารี่เสิร์ชทรีหลายแบบแต่ลำดับของคีย์เหมือนกัน
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออกกราฟ (Graph)
เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนดกราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้G = ( V , E )G คือ กราฟV คือ กลุ่มของ vertexE คือ กลุ่มของ edgeศัพท์ที่เกี่ยวข้อง
1.เวอร์เทก (Vertex) หมายถึง โหนด
2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด
3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน
Graph แบ่งเป็น
1. Directed Graph (Digraph) (Arc) แบบระบุทิศทาง
2. Undirected Graph แบบไม่ระบุทิศทาง
การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้
1. Adjacency Matrix (แอดจาเซนซี เมตริก) : ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List (แอดจาเซนซี ลิส) : ใช้ลิงค์ลิสต์เก็บข้อมูลAdjacency Matrixเป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x nMk เป็นเมทริกซ์ของกราฟใด ๆ k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่งAdjacency Matrix 0 : ไม่เป็นแอดจาเซนซีกัน1 : เป็นแอดจาเซนซีกัน
การท่องไปในกราฟเป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย
การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ
DTS08-26-08-2552
เรื่อง ทรี(Tree)
ทรีเป็นกราฟแบบมีทิศทาง ที่มีโครงสร้างแบบลำดับชั้น ทิศทางของกราฟที่แทนทรีจะมีทิศทางจากบนลงล่าง ดังนั้นการกวาดทรี เราจึงไม่นิยมแสดงทิศทางของเส้นเชื่อมการให้นิยามในรูปของการเรียกซ้ำซึ่งสอดคล้องกับลักษณะธรรมชาติ ของทรี ดังนี้ คือ ทรีประกอบด้วยโหนด R ซึ่งเรียกว่า โหนดราก (root) และ ทรีย่อย (subtree) จำนวนศูนย์ หรือมากกว่าศูนย์ ซึ่งแต่ละทรีย่อยจะเชื่อมกับโหนดราก (R)โดยตรงด้วยเส้นเชื่อมการเรียกชื่อองค์ประกอบของทรีโหนดที่อยู่ระดับบนสุดของทรี เรียกว่า โหนด R ,โหนดราก, พ่อ (father)หนดรากของทรีย่อยของ R เรียกว่า ลูก (child) ของ Rโหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (leaf node)เส้นเชื่อมโหนดทรี เรียกว่า กิ่ง (branch)โหนดที่มีทั้งพ่อทั้งลูก เรียกว่า โหนดกิ่ง (branch node)โหนดที่มีพ่อเดียวกัน เรียกว่า โหนดพี่น้อง (sibling) และยังอาจนิยามโหนดว่าเป็น โหนดปู่ (grandfather) หรือ โหนดหลาน (gtrandchild) ได้ในลักษณะเดียวกันเส้นทาง (path) จากโหนด n1 ไปยังโหนด nk ใดๆ จะเป็นลำดับของโหนด n1,n2,...,nkความยาว (length) ของเส้นทางจะเป็นจำนวนของเส้นเชื่อมที่อยู่ในเส้นทาง ซึ่งเท่ากับ k-1 เส้นทาง จากโหนดใดๆ ไปยังตัวเองจะมีความยาวเป็ยศูนย์ และในทรีแต่ละทรี จะมีเส้นทางหนึ่งเส้นเท่านั้นจากโหนดรากไปยัง โหนดใดๆ ความลึก (depth) เป็น ความยาวของเส้นทางจากโหนดรากไปยังโหนด n โซึ่งมีเส้นทางเดียวที่ไม่ซ้ำกัน) ความสูง (height) เป็น เส้นทางทีสุดจากโหนด n ไปยังโหนดใบถ้ามีเส้นทางจาดโหนด n1 ไปยังโหนด n2 จะเป็น บรรพบุรุษ (ancestor) ของ n2 และ n2 จะเป็น ลูกหลาน (descendant) ของ n1 ถ้า n1 != n2 ดังนั้น n1 จะเป็น บรรพบุรุษที่แท้จริง (proper ascestor) ของ n1 และ n2 ลูกหลานที่แท้จริง (proper descendant) ทรีแบบลำดับทรีแบบราก (rooted tree ) เป็นทรีที่สามารถวาดได้อิสระ โดยเชื่อมโหนดในระดับต่ำลงไป และมีโหนด ใบอยู่ในระดับล่าง มีโครงสร้างไม่เหมาะสมก่การใช้งาน เนื่องจากวิธีการเรียกชื่อโหนดจากลำดับซ้ายไปขวา
"ทรีแบบลำดับ (ordered tree)" คือ ทรีแบบรากที่โหนดลูกของแต่ละโหนดถูกกำหนดลำดับดังรูป ถ้าต้องการจะใช้ทรีแบบลำดับเป็นโครงสร้างข้อมูล ในแต่ละโหนดจะต้องมีจำนวนเขตข้อมูลมากพอๆ กับจำนวน ของโหนดนั้น ดังนั้นถ้ามีบางโหนดในทรีมีจำนวนทรีมากกว่า 10 ทรีย่อย จะต้องมีเขตข้อมูลสำหรับลิงค์ของ แต่ละโหนดถึง 10 เขต ซึ่งแต่ละเขตลิงค์ต่างๆ เหล่านี้ส่วนใหญ่จะมีค่าเป็น NULL ซึ่งทำให้เนื้อที่จำนวนมาก ไม่ได้ใช้งานไบนารีทรีไบนารีทรี เป็น ทรีว่าง หรือทรีที่ประกอบด้วยโหนดรากที่เรียกว่า ราก กับ ไบนารีทรี 2 ทรี เรียกว่า ทรีย่อยทางซ้าย (left subtree) และ ทรีย่อยทางขวา (right subtree) ของราก การสร้างไบนารีทรี ที่มีโหนดเดียว สามารถสร้างโหนดนั้นเป็นโหนดรากที่มีทรีย่อยทางซ้าย และทรีทางขวาเป็นทรีว่าง จะเห็นว่าไบนารีทรีแตก ต่างจากทรีทั่วไป เนื่องจากในไบนารีทรี ความหมายของคำว่า ซ้าย หรือ ขวา มีความสำคัญ ไบนารีทรี 2 โหนด ดังนั้นไบนารีทรีสามรถได้มาจากทรีแบบลำดับที่เหมาะสมกัน โดยการแยกกิ่งทางซ้ายออกจากกิ่งทางขวาการเปลี่ยนทรีทั่วไปเป็นไบนารีทรีไบนารีทรีเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพ แต่มีข้อจำกัดว่า แต่ละโหนดมีลูกได้ไม่เกิน 2 และในการประยุกต์ ใช้งานส่วนใหญ่ โครงสร้างข้อมูลเป็นจำนวนใดๆ ได้ตามใจ การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี เริ่มต้นจะเชื่อมโหนด แต่ละโหนดกับโหนดลูกซ้ายสุดของโหนดนั้น ซึ่งเรียกว่าโหนดแรก ต่อมาเชื่อมแต่ละโหนดยกเว้นโหนดรากกับโหนดถัดไป ที่มีพ่อเดียวกัน(พี่น้อง) ซึ่งเรียกว่าเชื่อมโหนดลูกถัดไปเพื่อให้โครงสร้างของไบนารีทรีที่ดีกว่านี้ จะต้องหมุนทรีเล็กน้อยตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมที่ชี้ลงล่าง ชี้ลงไปทางซ้าย และเส้นเชื่อมที่ชี้ตามแนวนอน ชี้ลงไปข้างล่างทางขวาป่าและสวนป่า (forest) หมายถึงของทรีที่เป็นทรีแบบรก และ สวน (orchard) หมายถึง ชุดของทรีแบบลำดับ แต่โดยทั่วไป แล้วป่ากับสวนมีความหมายเดียวกัน คือ ชุดของทรีทั่วไปสามารถสร้างป่าหรือสวนได้ โดยการขจัดรากออกไปจากทรีแบบราก หรือแบบลำดับและทำนองเดียวกัน สามารถแปลง จากป่าแสวนไปเป็นไบนารีทรีได้มีขั้นตอนดังต่อไปนี้1.ขจัดเส้นเชื่อมเดิมออก2.แปลงทรีแต่ละต้นให้เป็นไบนารีทรี3.เชื่อมโหนดรากของทรีเขาด้วยกัน ในแนวนอนโดยใช้ความสัมพันธ์พี่น้อง4.หมุนทรีที่ได้ 45 องศาตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมในแนวตั้งกลายเป็นเส้นเชื่อมทางซ้าย และเส้นเชื่อมในแนวนอนกลายเป็นเส้นเชื่อมทางขวา
การท่องไบนารีทรี (traversal of binary tree)เป็นการเคลื่อนที่ไปยังโหนดทุกโหนดของไบนารีของทรี หรือการเยี่ยมโหนดทุกโหนดของทรี ในข้อมูลแบบทรีโหนด ทุกโหนดที่จะท่องมีลำดับแตกต่างกัน ที่โหนดใด ไๆที่กำหนดให้จะต้องมีการกระทำ 3 อย่าง ในลำดับใดๆ คือ
1. เยี่ยมโหนดนั้น
2. ท่องไปยังทรีย่อยทางซ้ายของโหนดนั้น
3. ท่องไปยังทรีย่อยทางขวาของโหนดนั้น
จุดสำคัญของของการท่องไบนารีทรี คือ จะเยี่ยมททรีย่อยก่อนการท่องทรีย่อยที่มีอยู่ หรือจะเยี่ยมโหนดนั้นใน ระหว่างการท่องทรีย่อยของโหนดนั้น หรือจะเยี่ยมดหนดนั้นในระหว่างการท่องทรีย่อยภายหลังจากการท่องทรีย่อย ทั้งสองของโหนดนั้นเสร็จเรียบร้อยแล้ว
ทรีเป็นกราฟแบบมีทิศทาง ที่มีโครงสร้างแบบลำดับชั้น ทิศทางของกราฟที่แทนทรีจะมีทิศทางจากบนลงล่าง ดังนั้นการกวาดทรี เราจึงไม่นิยมแสดงทิศทางของเส้นเชื่อมการให้นิยามในรูปของการเรียกซ้ำซึ่งสอดคล้องกับลักษณะธรรมชาติ ของทรี ดังนี้ คือ ทรีประกอบด้วยโหนด R ซึ่งเรียกว่า โหนดราก (root) และ ทรีย่อย (subtree) จำนวนศูนย์ หรือมากกว่าศูนย์ ซึ่งแต่ละทรีย่อยจะเชื่อมกับโหนดราก (R)โดยตรงด้วยเส้นเชื่อมการเรียกชื่อองค์ประกอบของทรีโหนดที่อยู่ระดับบนสุดของทรี เรียกว่า โหนด R ,โหนดราก, พ่อ (father)หนดรากของทรีย่อยของ R เรียกว่า ลูก (child) ของ Rโหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (leaf node)เส้นเชื่อมโหนดทรี เรียกว่า กิ่ง (branch)โหนดที่มีทั้งพ่อทั้งลูก เรียกว่า โหนดกิ่ง (branch node)โหนดที่มีพ่อเดียวกัน เรียกว่า โหนดพี่น้อง (sibling) และยังอาจนิยามโหนดว่าเป็น โหนดปู่ (grandfather) หรือ โหนดหลาน (gtrandchild) ได้ในลักษณะเดียวกันเส้นทาง (path) จากโหนด n1 ไปยังโหนด nk ใดๆ จะเป็นลำดับของโหนด n1,n2,...,nkความยาว (length) ของเส้นทางจะเป็นจำนวนของเส้นเชื่อมที่อยู่ในเส้นทาง ซึ่งเท่ากับ k-1 เส้นทาง จากโหนดใดๆ ไปยังตัวเองจะมีความยาวเป็ยศูนย์ และในทรีแต่ละทรี จะมีเส้นทางหนึ่งเส้นเท่านั้นจากโหนดรากไปยัง โหนดใดๆ ความลึก (depth) เป็น ความยาวของเส้นทางจากโหนดรากไปยังโหนด n โซึ่งมีเส้นทางเดียวที่ไม่ซ้ำกัน) ความสูง (height) เป็น เส้นทางทีสุดจากโหนด n ไปยังโหนดใบถ้ามีเส้นทางจาดโหนด n1 ไปยังโหนด n2 จะเป็น บรรพบุรุษ (ancestor) ของ n2 และ n2 จะเป็น ลูกหลาน (descendant) ของ n1 ถ้า n1 != n2 ดังนั้น n1 จะเป็น บรรพบุรุษที่แท้จริง (proper ascestor) ของ n1 และ n2 ลูกหลานที่แท้จริง (proper descendant) ทรีแบบลำดับทรีแบบราก (rooted tree ) เป็นทรีที่สามารถวาดได้อิสระ โดยเชื่อมโหนดในระดับต่ำลงไป และมีโหนด ใบอยู่ในระดับล่าง มีโครงสร้างไม่เหมาะสมก่การใช้งาน เนื่องจากวิธีการเรียกชื่อโหนดจากลำดับซ้ายไปขวา
"ทรีแบบลำดับ (ordered tree)" คือ ทรีแบบรากที่โหนดลูกของแต่ละโหนดถูกกำหนดลำดับดังรูป ถ้าต้องการจะใช้ทรีแบบลำดับเป็นโครงสร้างข้อมูล ในแต่ละโหนดจะต้องมีจำนวนเขตข้อมูลมากพอๆ กับจำนวน ของโหนดนั้น ดังนั้นถ้ามีบางโหนดในทรีมีจำนวนทรีมากกว่า 10 ทรีย่อย จะต้องมีเขตข้อมูลสำหรับลิงค์ของ แต่ละโหนดถึง 10 เขต ซึ่งแต่ละเขตลิงค์ต่างๆ เหล่านี้ส่วนใหญ่จะมีค่าเป็น NULL ซึ่งทำให้เนื้อที่จำนวนมาก ไม่ได้ใช้งานไบนารีทรีไบนารีทรี เป็น ทรีว่าง หรือทรีที่ประกอบด้วยโหนดรากที่เรียกว่า ราก กับ ไบนารีทรี 2 ทรี เรียกว่า ทรีย่อยทางซ้าย (left subtree) และ ทรีย่อยทางขวา (right subtree) ของราก การสร้างไบนารีทรี ที่มีโหนดเดียว สามารถสร้างโหนดนั้นเป็นโหนดรากที่มีทรีย่อยทางซ้าย และทรีทางขวาเป็นทรีว่าง จะเห็นว่าไบนารีทรีแตก ต่างจากทรีทั่วไป เนื่องจากในไบนารีทรี ความหมายของคำว่า ซ้าย หรือ ขวา มีความสำคัญ ไบนารีทรี 2 โหนด ดังนั้นไบนารีทรีสามรถได้มาจากทรีแบบลำดับที่เหมาะสมกัน โดยการแยกกิ่งทางซ้ายออกจากกิ่งทางขวาการเปลี่ยนทรีทั่วไปเป็นไบนารีทรีไบนารีทรีเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพ แต่มีข้อจำกัดว่า แต่ละโหนดมีลูกได้ไม่เกิน 2 และในการประยุกต์ ใช้งานส่วนใหญ่ โครงสร้างข้อมูลเป็นจำนวนใดๆ ได้ตามใจ การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี เริ่มต้นจะเชื่อมโหนด แต่ละโหนดกับโหนดลูกซ้ายสุดของโหนดนั้น ซึ่งเรียกว่าโหนดแรก ต่อมาเชื่อมแต่ละโหนดยกเว้นโหนดรากกับโหนดถัดไป ที่มีพ่อเดียวกัน(พี่น้อง) ซึ่งเรียกว่าเชื่อมโหนดลูกถัดไปเพื่อให้โครงสร้างของไบนารีทรีที่ดีกว่านี้ จะต้องหมุนทรีเล็กน้อยตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมที่ชี้ลงล่าง ชี้ลงไปทางซ้าย และเส้นเชื่อมที่ชี้ตามแนวนอน ชี้ลงไปข้างล่างทางขวาป่าและสวนป่า (forest) หมายถึงของทรีที่เป็นทรีแบบรก และ สวน (orchard) หมายถึง ชุดของทรีแบบลำดับ แต่โดยทั่วไป แล้วป่ากับสวนมีความหมายเดียวกัน คือ ชุดของทรีทั่วไปสามารถสร้างป่าหรือสวนได้ โดยการขจัดรากออกไปจากทรีแบบราก หรือแบบลำดับและทำนองเดียวกัน สามารถแปลง จากป่าแสวนไปเป็นไบนารีทรีได้มีขั้นตอนดังต่อไปนี้1.ขจัดเส้นเชื่อมเดิมออก2.แปลงทรีแต่ละต้นให้เป็นไบนารีทรี3.เชื่อมโหนดรากของทรีเขาด้วยกัน ในแนวนอนโดยใช้ความสัมพันธ์พี่น้อง4.หมุนทรีที่ได้ 45 องศาตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมในแนวตั้งกลายเป็นเส้นเชื่อมทางซ้าย และเส้นเชื่อมในแนวนอนกลายเป็นเส้นเชื่อมทางขวา
การท่องไบนารีทรี (traversal of binary tree)เป็นการเคลื่อนที่ไปยังโหนดทุกโหนดของไบนารีของทรี หรือการเยี่ยมโหนดทุกโหนดของทรี ในข้อมูลแบบทรีโหนด ทุกโหนดที่จะท่องมีลำดับแตกต่างกัน ที่โหนดใด ไๆที่กำหนดให้จะต้องมีการกระทำ 3 อย่าง ในลำดับใดๆ คือ
1. เยี่ยมโหนดนั้น
2. ท่องไปยังทรีย่อยทางซ้ายของโหนดนั้น
3. ท่องไปยังทรีย่อยทางขวาของโหนดนั้น
จุดสำคัญของของการท่องไบนารีทรี คือ จะเยี่ยมททรีย่อยก่อนการท่องทรีย่อยที่มีอยู่ หรือจะเยี่ยมโหนดนั้นใน ระหว่างการท่องทรีย่อยของโหนดนั้น หรือจะเยี่ยมดหนดนั้นในระหว่างการท่องทรีย่อยภายหลังจากการท่องทรีย่อย ทั้งสองของโหนดนั้นเสร็จเรียบร้อยแล้ว
สมัครสมาชิก:
บทความ (Atom)