ต้นไม้ ต้นแดงและดำ

“สวัสดี อามีโก้!”

“สวัสดี ริชิ!”

"ฉันพบบันทึกเก่าของฉันที่นั่นและเตรียมเนื้อหาที่น่าสนใจสำหรับคุณ ฉันคิดว่าคุณจะสนใจที่จะฟังมัน"

"มาฟังกัน คุณมักจะพบสิ่งที่น่าสนใจซึ่งพิสูจน์ได้ว่ามีประโยชน์มากในภายหลัง"

"ตกลง วันนี้ฉันอยากจะบอกคุณเกี่ยวกับต้นไม้ดังนั้นฉันจะเริ่มต้นด้วยกราฟ "

" กราฟคือระบบของจุดและเส้นที่เชื่อมต่อกัน จุดเหล่านี้เรียกว่าจุดยอดของกราฟ และเส้นเรียกว่าขอบของกราฟ ตัวอย่างเช่น:"

"กราฟสะดวกมากที่จะใช้เป็นแบบจำลองทางคณิตศาสตร์สำหรับกระบวนการและงานต่างๆ ในโลกแห่งความเป็นจริง งานและอัลกอริทึมต่างๆ มากมายถูกประดิษฐ์ขึ้นสำหรับกราฟ ดังนั้นจึงใช้บ่อยพอสมควร"

"ตัวอย่างเช่น สมมติว่าจุดยอดคือเมือง และขอบคือถนน จากนั้นค้นหาถนนที่สั้นที่สุดระหว่างเมืองจะกลายเป็น: «ให้กราฟ ค้นหาเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุด» "

"แต่เส้นทางจาก A ไป B ไม่เหมือนกับเส้นทางจาก B ไป A เสมอไป ดังนั้น บางครั้งควรใช้เส้นสองเส้นที่แตกต่างกัน ในการทำเช่นนี้ เส้น (ขอบของกราฟ) จะถูกแทนที่ด้วยลูกศร หรืออีกนัยหนึ่ง กราฟสามารถมีลูกศรได้สองอัน อันหนึ่งจาก A ถึง B และอีกอันจาก B ถึง A"

"ถ้ากราฟใช้ลูกศร จะเรียกว่ากราฟแบบมีทิศทางถ้ามีแต่เส้น จะเรียกว่ากราฟไม่มีทิศทาง "

"จุดยอดแต่ละจุดสามารถมีจำนวนขอบของตัวเองได้ จุดยอดยังสามารถไม่มีขอบเลย ในทางกลับกัน จุดยอดสามารถเชื่อมต่อกันด้วยขอบกับจุดยอดอื่นๆ ทุกจุด หากจุดยอดแต่ละคู่ในกราฟเชื่อมต่อกันด้วยขอบ  ดังนั้น เรียกว่ากราฟสมบูรณ์ "

"ถ้าคุณสามารถใช้ขอบเพื่อไปถึงจุดยอดทุกจุดในกราฟได้ จะเรียกว่า กราฟ เชื่อมต่อกราฟที่มีจุดยอดสามจุดแยกกันและไม่มีขอบยังคงเป็นกราฟ แต่เราเรียกมันว่ากราฟตัดการเชื่อมต่อ "

"ในการสร้างกราฟที่เชื่อมต่อจากจุดยอด N คุณต้องมีขอบอย่างน้อย N-1 กราฟประเภทนี้เรียกว่าต้นไม้"

"ยิ่งไปกว่านั้น โดยปกติแล้ว จุดยอดหนึ่งจะถูกเลือกให้เป็นราก ของต้นไม้ และส่วนที่เหลือจะถูกประกาศให้เป็นกิ่งก้าน กิ่งของต้นไม้ที่ไม่มีกิ่งของตัวเองเรียกว่าใบไม้ตัวอย่างเช่น:"

"ถ้าแต่ละองค์ประกอบของต้นไม้มีลูกสองคน จะเรียกว่าต้นไม้ไบนารีหรืออีกนัยหนึ่งคือมี 0 หรือ 2 สาขาก็ได้คุณจะเห็นต้นไม้ไบนารีที่มุมขวาบน"

ต้นไม้เรียกว่า binary tree ที่สมบูรณ์เมื่อแต่ละกิ่งมีลูก 2 ต้น และใบทั้งหมด (จุดยอดที่ไม่มีลูก) อยู่ในแถวเดียวกัน"

"ตัวอย่างเช่น:"

"ทำไมต้นไม้เหล่านี้ถึงต้องการ?"

"โอ้ ต้นไม้ถูกใช้ในหลายๆ ที่ โดยทั่วไป ต้นไม้ไบนารีจะจัดเรียงข้อมูลที่มีโครงสร้าง"

"นั่นอะไร?"

"ใช่ มันง่ายมาก เราเก็บค่าหนึ่งไว้ในแต่ละจุดยอด และแต่ละองค์ประกอบเป็นไปตามกฎ: ค่าที่เก็บไว้ในลูกด้านขวาจะต้องมากกว่าค่าที่เก็บไว้ในจุดยอด และค่าที่เก็บไว้ในลูกด้านซ้ายจะต้อง น้อยกว่าค่าที่จัดเก็บไว้ในจุดยอด การเรียงลำดับ  นี้ทำให้สามารถค้นหาองค์ประกอบของต้นไม้ที่คุณต้องการได้อย่างรวดเร็ว"

“ช่วยอธิบายหน่อยได้ไหมว่าหมายความว่าอย่างไร”

"องค์ประกอบต้นไม้มักจะเรียงตามการบวก สมมติว่าเรามี 7 องค์ประกอบ: 13, 5, 4, 16, 8, 11, 10"

"นี่คือวิธีเพิ่มองค์ประกอบลงในต้นไม้"

"ถ้าเรากำลังมองหาเลข 7 ในต้นไม้นี้ การค้นหาจะเป็นแบบนี้"

"0) เริ่มต้นที่ราก"

"1a) 7 เท่ากับ 13 หรือไม่ ไม่ใช่"

"1b) 7 มากกว่า 13 หรือเปล่า ไม่ใช่ งั้นเราย้ายไปที่แผนผังย่อยด้านซ้าย"

"2a) 7 เท่ากับ 5 หรือไม่ ไม่"

"2b) 7 มากกว่า 5 ใช่ไหม ใช่ งั้นเราย้ายไปที่แผนผังย่อยด้านขวา"

"3a) 7 เท่ากับ 8 หรือไม่ ไม่ใช่"

"3b) 7 มากกว่า 8 หรือไม่ ไม่ เราย้ายไปที่แผนผังย่อยด้านซ้าย"

"4a) ไม่มีทรีย่อยด้านซ้าย ซึ่งหมายความว่าเลข 7 ไม่อยู่ในทรี"

"อ่า พูดอีกอย่างก็คือ เราแค่ต้องตรวจสอบจุดยอดบนเส้นทางจากรากไปยังตำแหน่งที่ต้องการของตัวเลขที่ต้องการ ใช่ เร็วจริงๆ"

"ยิ่งไปกว่านั้น หากต้นไม้มีความสมดุล คุณก็จะต้องผ่านจุดยอดประมาณ 20 จุดเพื่อค้นหาองค์ประกอบนับล้าน"

“ฉันเห็นด้วย – นั่นไม่มากนัก”

“ต้นไม้สมดุลหมายความว่าอย่างไร”

“ต้นไม้ที่ไม่บิดเบี้ยว คือ ไม่มีกิ่งก้านยาว เช่นถ้าองค์ประกอบถูกจัดเรียงแล้วเมื่อเราสร้างต้นไม้ เราก็จะได้ต้นไม้ที่ยาวมากซึ่งประกอบด้วยกิ่งเดียว ”

“อืม คุณพูดถูก แล้วเราจะทำอย่างไรดี”

"อย่างที่คุณเดาได้ ต้นไม้ที่มีประสิทธิภาพมากที่สุดจะมีกิ่งก้านสาขาที่มีความยาวใกล้เคียงกัน จากนั้นการเปรียบเทียบแต่ละครั้งจะทิ้งส่วนที่ใหญ่ที่สุดของต้นไม้ย่อยที่เหลือ"

“แล้วเราต้องสร้างต้นไม้ใหม่ไหม”

"ใช่ มันจำเป็นต้อง «สมดุล» — เพื่อให้ใกล้เคียงกับไบนารีทรีที่สมบูรณ์ที่สุดเท่าที่จะทำได้"

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

"ต้นไม้เหล่านี้บางคนเรียกว่า ต้นไม้ แดงดำ "

“ทำไมถึงเรียกว่าแดง-ดำ”

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

"ตัวอย่างเช่น:"

“แล้วกฎเหล่านี้คืออะไร?”

"1) จุดยอดสีแดงไม่สามารถเป็นลูกของจุดยอดสีแดงได้"

"2) ความลึกสีดำของใบไม้ทุกใบเท่ากัน (ความลึกสีดำหมายถึงจำนวนจุดยอดสีดำบนเส้นทางจากราก)"

"3) รากของต้นไม้เป็นสีดำ"

"ฉันจะไม่อธิบายว่ามันทำงานอย่างไร หัวของคุณคงจะระเบิดไปแล้ว"

"ใช่ โปรเซสเซอร์ของฉันมีควันออกมาเล็กน้อย"

"นี่คือลิงค์สำหรับคุณ หากต้องการ คุณสามารถอ่านเพิ่มเติมเกี่ยวกับเรื่องนี้ได้ที่นี่"

เชื่อมโยงไปยังเนื้อหาเพิ่มเติม

"และตอนนี้ไปพักผ่อน"