ที่นี่เราจะมาดูกันว่าต้นไม้ฝ่ายซ้ายที่มีความสูงสมดุล (HBLT) คืออะไร พิจารณาไบนารีทรีที่มีโหนดพิเศษเรียกว่า โหนดภายนอก แทนที่แต่ละทรีย่อยที่ว่างเปล่า โหนดอื่นๆ ทั้งหมดเรียกว่า Internal Nodes . เมื่อมีการเพิ่มโหนดภายนอกด้วยไบนารีทรี โหนดนั้นจะเรียกว่า ไบนารีทรีแบบขยาย . หากเราไม่พิจารณาขอบใบของต้นไ

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

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

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

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

การลบโหนดโดยพลการจาก HBLT สูงสุดหรือต่ำสุดไม่ใช่การดำเนินการมาตรฐาน สำหรับคิวลำดับความสำคัญหรือ HBLT หากเราต้องการลบโหนดที่บอกว่า K จาก HBLT เราต้องปฏิบัติตามกฎต่อไปนี้ ถอดทรีย่อยที่รูทที่ K ออกจากทรี และแทนที่ด้วยการรวมของทรีย่อยของโหนด K อัปเดตค่าจากพาธจาก K เป็นรูท และสลับทรีย่อยบนพาธนี้ตาม

ที่นี่เราจะเห็นรูปแบบอื่นของต้นไม้ฝ่ายซ้าย ในที่นี้ เราจะพิจารณาจำนวนโหนดในทรีย่อย แทนที่จะเป็นความยาวของพาธที่สั้นที่สุดสำหรับรูทไปยังโหนดภายนอก ในที่นี้เราจะกำหนดน้ำหนัก w(x) ของโหนด x ให้เป็นจำนวนโหนดภายในในทรีย่อยที่มีรูท x ถ้า x เป็นโหนดภายนอก น้ำหนักจะเป็น 0 ถ้า x เป็นโหนดภายใน น้ำหนักจะมากกว่

ที่นี่เราจะมาดูกันว่าการดำเนินการ Max-WBLT ต่างกันอย่างไร HBLT มีการดำเนินการที่แตกต่างกัน เช่น การแทรก การลบ และการเริ่มต้น พวกมันค่อนข้างคล้ายกับ WBLT เช่นกัน อย่างไรก็ตาม การทำ Meld สามารถทำได้ในการผ่านจากบนลงล่างเพียงครั้งเดียว WBLT สามารถดำเนินการผสมผ่านครั้งเดียวได้ เพราะเราสามารถหาค่า w ได้ร

ในส่วนนี้เราจะมาดูกันว่าโครงการ Robin-Hood Hashing คืออะไร การแฮชนี้เป็นหนึ่งในเทคนิคของการกำหนดที่อยู่แบบเปิด วิธีนี้จะพยายามทำให้เวลาในการค้นหาขององค์ประกอบเท่ากันโดยใช้กลยุทธ์การแก้ปัญหาการชนที่ยุติธรรมยิ่งขึ้น ในขณะที่เรากำลังพยายามแทรก หากเราต้องการแทรกองค์ประกอบ x ที่ตำแหน่ง xi และมีองค์ประกอบ

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

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

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

ที่นี่เราจะเห็นโครงสร้างข้อมูล R-Trees R-Trees ใช้เพื่อจัดเก็บดัชนีข้อมูลพิเศษในลักษณะที่มีประสิทธิภาพ โครงสร้างนี้มีประโยชน์มากในการเก็บแบบสอบถามข้อมูลพิเศษและการจัดเก็บข้อมูล R-trees นี้มีการใช้งานในชีวิตจริง เหล่านี้เป็นเหมือนด้านล่าง − การสร้างดัชนีข้อมูลหลายมิติ การจัดการข้อมูลเกม ถือพ

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

วิธีเขียนนิพจน์เลขคณิตเรียกว่าสัญกรณ์ นิพจน์เลขคณิตสามารถเขียนได้สามรูปแบบที่แตกต่างกันแต่เทียบเท่า กล่าวคือ โดยไม่ต้องเปลี่ยนสาระสำคัญหรือผลลัพธ์ของนิพจน์ สัญกรณ์เหล่านี้คือ – สารบัญ คำนำหน้า Postfix สัญกรณ์ infix เป็นสัญกรณ์ปกติที่เราใช้ในขณะที่เขียนนิพจน์ทางคณิตศาสตร์ที่แตกต่างกัน สัญ

ที่นี่เราจะเห็นต้นไม้การแข่งขัน ต้นไม้ Winner และ Looser ต้นไม้การแข่งขันเป็นต้นไม้ไบนารีที่สมบูรณ์ที่มี n โหนดภายนอกและ n – 1 โหนดภายใน โหนดภายนอกเป็นตัวแทนของผู้เล่น และโหนดภายในเป็นตัวแทนของผู้ชนะการแข่งขันระหว่างผู้เล่นสองคน ต้นไม้นี้เรียกอีกอย่างว่าต้นไม้การคัดเลือก มีคุณสมบัติบางอย่างของต้นไม

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

ในส่วนนี้ เราจะมาดูกันว่าอะไรคือความแตกต่างระหว่างต้นไม้ที่รูทแล้วกับต้นไม้ที่ยังไม่รูท ในตอนแรก เราจะเห็นตัวอย่างบางส่วนของต้นไม้ที่ทำการรูทแล้วและยังไม่ได้ทำการรูท ตัวอย่างต้นไม้ที่รูทแล้ว − ตัวอย่างของ Unrooted Tree − ความแตกต่างพื้นฐานระหว่างต้นไม้ที่รูทแล้วและไม่ได้รูท ในต้นไม้ที่รูทแล้ว แ

สำหรับฟังก์ชันแฮชใดๆ เราสามารถพูดได้ว่าหากขนาดตาราง m เล็กกว่าขนาดจักรวาล u มาก ดังนั้นสำหรับฟังก์ชันแฮช h จะมีชุดย่อยขนาดใหญ่ของ U ที่เหมือนกัน ค่าแฮช เพื่อขจัดปัญหานี้ เราจำเป็นต้องมีชุดของฟังก์ชันแฮช ซึ่งเราสามารถเลือกฟังก์ชันใดที่เหมาะกับ S ได้ หากฟังก์ชันแฮชส่วนใหญ่เหมาะกับ S มากกว่า เราก็สามา

ในส่วนนี้เราจะมาดูกันว่า hashing กับ chaining คืออะไร Chaining เป็นเทคนิคการแก้ปัญหาการชนกันอย่างหนึ่ง เราไม่สามารถหลีกเลี่ยงการชนกัน แต่เราสามารถพยายามลดการชนกัน และพยายามเก็บองค์ประกอบหลายรายการสำหรับค่าแฮชเดียวกัน เทคนิคนี้สมมติว่าฟังก์ชันแฮชของเรา h(x) มีตั้งแต่ 0 ถึง 6 ดังนั้นสำหรับองค์ประกอบม