การเรียงลำดับทอพอโลยีหรือการจัดลำดับทอพอโลยีของกราฟกำกับเป็นการเรียงลำดับเชิงเส้นของจุดยอดในลักษณะที่ว่าสำหรับรังสีอัลตราไวโอเลตทุกเส้นจากจุดยอด u ถึงจุดยอด v u มาก่อน v ในลำดับ สิ่งนี้สมเหตุสมผลในกราฟกำกับเท่านั้น มีหลายสถานที่ที่การเรียงลำดับทอพอโลยีเหมาะสมอย่างยิ่ง ตัวอย่างเช่น สมมติว่าคุณกำลังท

ในทฤษฎีกราฟ ปัญหาเส้นทางที่สั้นที่สุดคือปัญหาในการค้นหาเส้นทางระหว่างจุดยอดสองจุด (หรือโหนด) ในกราฟ โดยที่ผลรวมของน้ำหนักของขอบที่เป็นส่วนประกอบจะลดลง ที่นี่เราจำเป็นต้องแก้ไขขอบเพิ่มของเราและเพิ่มวิธีการโดยตรงเพื่อให้สามารถเพิ่มน้ำหนักให้กับขอบได้เช่นกัน มาดูกันว่าเราจะเพิ่มสิ่งนี้ได้อย่างไร - ตั

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

อัลกอริทึมของ Djikstra ใช้เพื่อค้นหาระยะทาง/เส้นทางของเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปยังโหนดอื่นทั้งหมด มีหลายกรณีที่เราต้องค้นหาเส้นทางที่สั้นที่สุดจากโหนดทั้งหมดไปยังโหนดอื่นทั้งหมด นี่คือจุดที่อัลกอริธึมพาธที่สั้นที่สุดของ All pairs มีประโยชน์ อัลกอริธึมพาธที่สั้นที่สุดของทุกคู่ที่ใช้มากที่สุด

การข้ามผ่านต้นไม้หมายถึงกระบวนการเยี่ยมชมแต่ละโหนดในโครงสร้างข้อมูลต้นไม้ เพียงครั้งเดียว การข้ามผ่านดังกล่าวถูกจำแนกตามลําดับที่โหนดถูกเยี่ยมชม

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

ในวิธีการข้ามผ่านนี้ โหนดรูทจะถูกเข้าชมก่อน จากนั้นจึงไปที่ทรีย่อยทางซ้าย และสุดท้ายไปที่ทรีย่อยทางขวา เราเริ่มจาก A, และหลังจากผ่านการสั่งซื้อล่วงหน้า เราไปที่ A . ก่อน ตัวเองแล้วย้ายไปที่ทรีย่อยด้านซ้าย B. ข ยังผ่านการสั่งซื้อล่วงหน้า กระบวนการนี้ดำเนินต่อไปจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด ผ

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

การลบโหนดออกจากต้นไม้นั้นค่อนข้างซับซ้อนหากคุณมองจากระยะไกล มี 3 กรณีที่ต้องพิจารณาเมื่อลบโหนด สิ่งเหล่านี้ถูกกล่าวถึงในความคิดเห็นของฟังก์ชันต่อไปนี้ อย่างที่เราทำไปก่อนหน้านี้ เราจะสร้างวิธีการในชั้นเรียนและตัวช่วยเพื่อเรียกซ้ำ วิธีการเรียน deleteNode(key) {    // If a node is successful

นี่คือการใช้งานที่สมบูรณ์ของคลาส BinarySearchTree - ตัวอย่าง class BinarySearchTree {    constructor() {       // Initialize a root element to null.       this.root = null;    }    insertIter(data) {       let node = new this

ต้นไม้ AVL (ตั้งชื่อตามนักประดิษฐ์ Adelson-Velsky และ Landis) เป็นแผนผังการค้นหาไบนารีแบบสมดุลในตัวเอง ต้นไม้ที่สร้างสมดุลในตัวเองคือต้นไม้ที่ทำการหมุนภายในต้นไม้ย่อย เพื่อให้สามารถปรับสมดุลทั้งด้านซ้ายและด้านขวา ต้นไม้เหล่านี้มีประโยชน์อย่างยิ่งในกรณีที่การแทรกซึมทำให้ต้นไม้หนักด้านใดด้านหนึ่ง ต้น

ต้นไม้ AVL ตรวจสอบความสูงของต้นไม้ย่อยด้านซ้ายและด้านขวา และรับรองว่าความแตกต่างไม่เกิน 1 ความแตกต่างนี้เรียกว่า ปัจจัยความสมดุล ตัวอย่างเช่น ในต้นไม้ต่อไปนี้ ต้นไม้ต้นแรกสมดุลและต้นไม้สองต้นถัดไปไม่สมดุล - ในต้นไม้ที่สอง ต้นไม้ย่อยด้านซ้ายของ C มีความสูง 2 และต้นไม้ย่อยด้านขวามีความสูง 0 ดังนั

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

เราสามารถเรียนรู้วิธีที่เราสามารถแทรกโหนดในแผนผัง AVL การแทรกในแผนผัง AVL จะเหมือนกับ BST เราเพียงแค่ต้องทำขั้นตอนพิเศษที่เรียกว่าแผนผังสมดุลระหว่างการแทรกเมื่อใดก็ตามที่เราเลื่อนลงมา สิ่งนี้ต้องคำนวณปัจจัยความสมดุลที่เราเคยเห็นมาก่อน และตามการกำหนดค่า เราจำเป็นต้องเรียกวิธีการหมุนที่เหมาะสม คำอธิบ

บางครั้ง เราจำเป็นต้องรวมคอนเทนเนอร์เข้าด้วยกันโดยใช้ฟังก์ชัน join และรับคอนเทนเนอร์ใหม่ เราจะเขียนวิธีการเข้าร่วมแบบคงที่ซึ่งรับ 2 HashTables และสร้าง HashTable ใหม่พร้อมค่าทั้งหมด เพื่อความง่าย เราจะให้ค่าจากค่าที่สองแทนที่ค่าของค่าแรกหากมีคีย์ใดๆ อยู่ในทั้งสองค่า ตัวอย่าง static join(table1, tab

นี่คือการนำคลาส HashTable ไปใช้งานโดยสมบูรณ์ แน่นอนว่าสิ่งนี้สามารถปรับปรุงได้โดยใช้โครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้นและอัลกอริธึมการแก้ปัญหาการชน ตัวอย่าง class HashTable {    constructor() {       this.container = [];       // Populate the container

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

Binary Tree เป็นโครงสร้างข้อมูลพิเศษที่ใช้สำหรับการจัดเก็บข้อมูล ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน ต้นไม้ไบนารีมีประโยชน์ของทั้งอาร์เรย์ที่เรียงลำดับและรายการที่เชื่อมโยง เนื่องจากการค้นหาทำได้รวดเร็วเช่นเดียวกับในอาร์เรย์ที่เรียงลำดับ และการแทรกหรือลบทำได้เร็วเท่ากับใ

โครงสร้างการค้นหาแบบไบนารีแสดงพฤติกรรมพิเศษ ลูกด้านซ้ายของโหนดต้องมีค่าน้อยกว่าค่าของพาเรนต์ และลูกด้านขวาของโหนดต้องมีค่ามากกว่าค่าพาเรนต์ ส่วนใหญ่เราจะเน้นที่ต้นไม้ดังกล่าวในส่วนนี้เกี่ยวกับต้นไม้ การดำเนินการบนทรีการค้นหาแบบไบนารี เราจะกำหนดการดำเนินการต่อไปนี้ในแผนผังการค้นหาแบบไบนารี - การ

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