อธิบายต้นไม้ 4 ประเภทในโครงสร้างข้อมูล: คุณสมบัติและการใช้งาน

ต้นไม้ในโครงสร้างข้อมูลคืออะไร?

ต้นไม้เป็นโครงสร้างข้อมูลที่แสดงถึงข้อมูลแบบลำดับชั้น มีโครงสร้างไม่เชิงเส้นประกอบด้วยโหนดที่เชื่อมต่อกันด้วยขอบ โครงสร้างข้อมูลประเภทอื่นๆ ที่ดำเนินการในโครงสร้างข้อมูลเชิงเส้น ความซับซ้อนจะเพิ่มขึ้นตามขนาดข้อมูลที่เพิ่มขึ้น อย่างไรก็ตาม โครงสร้างข้อมูลแบบทรี ช่วยให้เข้าถึงข้อมูลที่ไม่ใช่แบบเชิงเส้นได้รวดเร็วยิ่งขึ้น ความพร้อมใช้งานของโครงสร้างข้อมูลประเภทต่างๆ และอัลกอริธึมที่เกี่ยวข้อง ประสิทธิภาพของงานได้กลายเป็นวิธีที่ง่ายและมีประสิทธิภาพ

คำศัพท์บางคำที่เกี่ยวข้องกับ ต้นไม้ในโครงสร้างข้อมูล คือ:

• โหนด : โหนดเป็นเอนทิตีในโครงสร้างข้อมูลแบบต้นไม้ที่มีคีย์หรือค่าและตัวชี้ไปยังโหนดย่อย
• โหนด ย่อย : โหนดย่อยเป็นลูกหลานของโหนดใด ๆ
• Leaf nodes: โหนดที่ไม่มีโหนดย่อยและเป็นโหนดล่างสุดในทรี พวกเขาจะเรียกว่าโหนดภายนอก
• ราก : เป็นจุดบนสุดของต้นไม้
• โหนดภายใน : โหนดที่มีโหนดชายน์อย่างน้อยหนึ่งโหนด
• ขอบ: ขอบหมายถึงการเชื่อมต่อระหว่างสองโหนดในทรี
• ความสูงของโหนด: จำนวนขอบจากโหนดถึงใบไม้ที่ลึกที่สุด
• ความลึกของโหนด : จำนวนขอบจากรูทถึงโหนด
• ความสูงของต้นไม้ : ความสูงของโหนดราก
• ระดับของโหนด : จำนวนสาขาทั้งหมดไปยังโหนดนั้น
• ป่า: คอลเลกชันของต้นไม้ที่ไม่ปะติดปะต่อ

ประเภทของต้นไม้

1. ต้นไม้ไบนารี

ไบนารีทรี เป็น โครงสร้าง ข้อมูล ประเภทหนึ่ง ที่โหนดหลักทุกโหนดมีโหนดย่อยสูงสุดสองโหนด ตามชื่อที่แนะนำ ไบนารีหมายถึงสอง ดังนั้น แต่ละโหนดสามารถมีได้ 0, 1 หรือ 2 โหนด โครงสร้าง ข้อมูลไบนารีทรี แสดงใน รูปที่ 1 โหนด 1 ในทรีประกอบด้วยตัวชี้สองตัว ตัวหนึ่งสำหรับโหนดย่อยแต่ละโหนด โหนด 2 อีกครั้งมีตัวชี้สองตัวแต่ละตัวสำหรับโหนดย่อยสองโหนด ในขณะที่โหนด 3, 5 และ 6 เป็นโหนดปลายสุด ดังนั้นจึงมีพอยน์เตอร์ที่เป็นโมฆะทั้งในส่วนซ้ายและขวา

รูปที่ 1: การเป็นตัวแทนของต้นไม้ไบนารี ( https://www.javatpoint.com/binary-tree )

คุณสมบัติของไบนารีทรี

• จำนวนโหนดสูงสุดในแต่ละระดับของ I คือ 2 ผม
• ความสูงของต้นไม้ใน รูปที่ 1 คือ 3 ซึ่งหมายความว่าจำนวนสูงสุดของโหนดจะเป็น (1+2+4+8) =15

• ที่ความสูง h จำนวนโหนดสูงสุดที่เป็นไปได้คือ (20 + 21 + 22+….2h) = 2h+1 -1

• ที่ความสูง h จำนวนโหนดขั้นต่ำที่เป็นไปได้คือ h+1

• จำนวนโหนดขั้นต่ำจะแสดงถึงต้นไม้ที่มีความสูงสูงสุดและในทางกลับกัน

แม้แต่ต้นไม้ไบนารีสามารถแบ่งออกเป็นต้นไม้ประเภทต่อไปนี้:

• ต้นไม้ไบนารีแบบเต็ม: เป็นต้นไม้ไบนารีชนิดพิเศษ ในโครงสร้างข้อมูลแบบทรีนี้ ทุกโหนดหลักหรือโหนดภายในจะมีโหนดย่อยสองโหนดหรือไม่มีโหนดย่อย
• ต้นไม้ไบนารีที่สมบูรณ์แบบ: ในโครงสร้างข้อมูลทรีประเภทนี้ โหนดภายในทุกโหนดมีโหนดย่อยสองโหนด และโหนดปลายสุดทั้งหมดอยู่ในระดับเดียวกัน
• ต้นไม้ไบนารีที่สมบูรณ์: มันคล้ายกับต้นไม้ไบนารีที่สมบูรณ์โดยมีความแตกต่างเล็กน้อย
• ทุกระดับจะเต็มไปหมด
• โหนดใบเอนไปทางซ้ายของต้นไม้
• ไม่จำเป็นสำหรับโหนดปลายสุดสุดท้ายที่จะมีพี่น้องที่ถูกต้อง กล่าวคือ ต้นไม้ไบนารีที่สมบูรณ์ไม่จำเป็นต้องเป็นต้นไม้ไบนารีแบบเต็ม
• Degenerate หรือ Pathological Tree: ต้นไม้เหล่านี้มีลูกเดี่ยวทางด้านซ้ายหรือด้านขวาของโหนดหลัก
• ต้นไม้ไบนารีเบ้: เป็นต้นไม้ทางพยาธิวิทยาหรือเสื่อมโทรมซึ่งต้นไม้ถูกครอบงำโดยโหนดด้านซ้ายหรือโหนดด้านขวา ดังนั้นจึงมีไบนารีทรีเบ้สองประเภท ได้แก่ ไบนารีทรีเบ้ซ้ายหรือไบนารีทรีเบ้ขวา
• ต้นไม้ไบนารีที่สมดุล: ความแตกต่างระหว่างความสูงของทรีย่อยซ้ายและขวาสำหรับแต่ละโหนดคือ 0 หรือ 1

2. แผนผังการค้นหาไบนารี

โครงสร้างแบบต้นไม้เหล่านี้ไม่เป็นเชิงเส้น และมีหนึ่งโหนดเชื่อมต่อกับโหนดจำนวนหนึ่ง โหนดสามารถเชื่อมต่อกับโหนดย่อยได้ไม่เกินสองโหนด มันถูกเรียกว่าแผนผังการค้นหาแบบไบนารีเพราะ:

• แต่ละโหนดมีโหนดย่อยสูงสุดสองโหนด
• สามารถใช้เพื่อค้นหาองค์ประกอบในเวลา 0(log(n)) และด้วยเหตุนี้จึงเรียกว่าแผนผังการค้นหา

รูป: ตัวอย่างของโครงสร้างการค้นหาแบบไบนารี ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

คุณสมบัติของแผนผังการค้นหาแบบไบนารีคือ:

• ค่าในโหนดทั้งหมดของทรีย่อยด้านซ้ายควรน้อยกว่าค่าในโหนดรูท
• ค่าในโหนดทั้งหมดของทรีย่อยที่ถูกต้องควรมากกว่าค่าในโหนดรูท

3. AVL Tree

ต้นไม้ AVL เป็นประเภทหรือตัวแปรของต้นไม้ไบนารี ประกอบด้วยคุณสมบัติจากทั้งไบนารีและโครงสร้างการค้นหาไบนารี คิดค้นโดย Adelson Velsky Lindas ต้นไม้เหล่านี้มีความสมดุลในตัวเอง ซึ่งหมายความว่าความสูงของต้นไม้ย่อยด้านซ้ายและต้นไม้ย่อยด้านขวามีความสมดุล ยอดคงเหลือนี้วัดจากปัจจัยการทรงตัว

ปัจจัยสมดุล:

• มันคือความแตกต่างระหว่างทรีย่อยด้านซ้ายและทรีย่อยด้านขวา
• ค่าของปัจจัยการปรับสมดุลต้องเป็น 0, -1 หรือ 1 ดังนั้น แต่ละโหนดของแผนผัง AVL ควรประกอบด้วยค่าปัจจัยการปรับสมดุล เช่น 0, -1 หรือ 1
• Balance Factor = (ความสูงของทรีย่อยด้านซ้าย – ความสูงของทรีย่อยด้านขวา)
• ต้นไม้ AVL ถูกกล่าวขานว่าเป็นต้นไม้ที่สมดุล ถ้าปัจจัยความสมดุลของแต่ละโหนดอยู่ระหว่าง -1 ถึง 1

ค่าของโหนดอื่นที่ไม่ใช่ -1 ถึง 1 ในแผนผัง AVL จะแสดงแผนผังที่ไม่สมดุลซึ่งจำเป็นต้องได้รับการปรับสมดุล

• หากโหนดมีปัจจัยสมดุลเท่ากับ 1 แสดงว่าทรีย่อยด้านซ้ายสูงกว่าทรีย่อยด้านขวา 1 ระดับ
• หากโหนดมีปัจจัยสมดุลเป็น 0 แสดงว่าความสูงของทรีย่อยด้านซ้ายและทรีย่อยด้านขวาเท่ากัน
• หากโหนดมีปัจจัยสมดุล -1 แสดงว่าทรีย่อยด้านขวาสูงกว่าทรีย่อยด้านซ้าย 1 ระดับ หรือทรีย่อยด้านซ้ายต่ำกว่าทรีย่อยด้านขวา 1 ระดับ

4. บี-ทรี

B Tree เป็นรูปแบบทั่วไปของแผนผังการค้นหาแบบไบนารี เป็นที่รู้จักกันว่าต้นไม้ทาง m ที่มีความสูงสมดุล โดยที่ m คือลำดับของต้นไม้ แต่ละโหนดของทรีสามารถมีได้มากกว่าหนึ่งคีย์และโหนดย่อยมากกว่าสองโหนด ในกรณีของไบนารีทรี โหนดลีฟอาจไม่อยู่ในระดับเดียวกัน อย่างไรก็ตาม ในกรณีของ B Tree โหนดลีฟทั้งหมดควรอยู่ในระดับเดียวกัน

คุณสมบัติของ B-tree:

• คีย์จะถูกจัดเก็บในลำดับที่เพิ่มขึ้นสำหรับแต่ละโหนด x
• ค่าบูลีน "x.leaf" มีอยู่ในแต่ละโหนด ซึ่งจะเป็นจริงหาก x เป็นลีฟ
• โหนดภายในควรมีคีย์มากที่สุด "n-1" โดยที่ n คือลำดับของต้นไม้ ควรมีตัวชี้สำหรับเด็กแต่ละคนด้วย
• โหนดทั้งหมดจะมีอย่างน้อย n ลูกและอย่างน้อย n/2 ลูก ยกเว้นโหนดรูท
• โหนดใบของต้นไม้มีความลึกเท่ากัน
• โหนดรูทจะมีอย่างน้อย 1 คีย์และอย่างน้อย 2 รายการย่อย
• ถ้า n ≥ 1 ดังนั้นสำหรับ n-key B-tree ที่มีความสูง h และระดับต่ำสุด t ≥ 2 h ≥ logt (n+)/2

แอปพลิเคชั่น

• Binary Search tree สามารถใช้สำหรับค้นหาองค์ประกอบในชุดขององค์ประกอบ
• Heap tree ใช้สำหรับ heap sort
• เราเตอร์สมัยใหม่ใช้ต้นไม้ชนิดหนึ่งที่เรียกว่า Tries เพื่อจัดเก็บข้อมูลเส้นทาง
• ฐานข้อมูลยอดนิยมส่วนใหญ่ใช้ B-Trees และ T-Trees เพื่อจัดเก็บข้อมูล
• คอมไพเลอร์ใช้แผนผังไวยากรณ์เพื่อตรวจสอบไวยากรณ์ของโปรแกรมที่เขียนทุกโปรแกรม

บทสรุป

โครงสร้างข้อมูลเป็นวิธีที่มีระเบียบในการจัดเก็บข้อมูลเพื่อการจัดการที่ง่ายดายและการจัดการที่มีประสิทธิภาพ มีโครงสร้างข้อมูลประเภทต่างๆ สำหรับข้อมูลประเภทต่างๆ ผู้ใช้จะเลือกตามประเภทของข้อมูลที่ต้องการจัดเก็บ

ต้นไม้เป็นประเภทของโครงสร้างข้อมูลที่สามารถจัดเก็บข้อมูลประเภทลำดับชั้นได้ ข้อมูลถูกเก็บไว้ในโหนดซึ่งบางครั้งเก็บข้อมูลอ้างอิงสำหรับโหนดอื่นที่เรียกว่าโหนดย่อย

ตามจำนวนโหนดย่อย ต้นไม้สามารถจำแนกได้หลายประเภทตามที่กล่าวไว้ในบทความ โครงสร้างต้นไม้แต่ละต้นมีคุณสมบัติที่เกี่ยวข้องกันตามการจัดเรียงโหนดในประเภทต้นไม้ ด้วยการดำเนินการประเภทต่างๆ ที่สามารถทำได้โดยต้นไม้ประเภทต่างๆ โครงสร้างข้อมูลประเภทนี้พบแอปพลิเคชันในอัลกอริธึมการเรียงลำดับและการจัดเก็บข้อมูล

โครงการ PG สำหรับผู้บริหารด้านการพัฒนาซอฟต์แวร์ – ความเชี่ยวชาญพิเศษด้านการพัฒนาแบบครบวงจร ดูแลจัดการโดย upGrad และ IIIT-บังกาลอร์ สามารถช่วยเหลือคุณในการปรับปรุงโปรไฟล์ของคุณ และรับโอกาสการจ้างงานที่ดีขึ้นในฐานะโปรแกรมเมอร์