![]()
ตัวอย่างต้นไม้แบบที
ในสาขาวิชาวิทยาการคอมพิวเตอร์ ต้นไม้แบบที (T-tree) เป็นโครงสร้างข้อมูลประเภท ต้นไม้ทวิภาค ที่ถูกใช้เป็น ฐานข้อมูลหน่วยความจำหลัก (main-memory database) เช่น Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen และ Kairos
ต้นไม้แบบที เป็นต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (Self-balancing binary search tree) เหมาะสำหรับกรณีที่หน่วยความจำเก็บทั้งดัชนีและข้อมูลเช่นเดียวกับ ต้นไม้แบบบี (B-tree) ที่เหมาะสำหรับการรักษาข้อมูลของหน่วยความจำสำรอง เช่น ฮาร์ดดิสก์ นอกจากนี้ต้นไม้แบบทียังได้ประโยชน์จากโครงสร้างหน่วยความจำแบบต้นไม้เช่นเดียวกับ ต้นไม้เอวีแอล (AVL tree) ในขณะที่สามารถประหยัดพื้นที่เก็บข้อมูลเมื่อมีขนาดเป็นจำนวนมากได้ เพราะว่าแต่ละปมของต้นไม้เอวีแอลสามารถเก็บข้อมูลได้เพียงแค่ตัวเดียว จึงจำเป็นที่ต้องสร้างปมเพื่อเก็บข้อมูลเป็นจำนวนมากกว่า
ต้นไม้แบบทีจะใช้ความจริงที่ว่าข้อมูลจะอยู่ร่วมกันกับดัชนีในหน่วยความจำเสมอ มันจึงสามารถเก็บเฉพาะตัวชี้ไปยังข้อมูลเท่านั้น
ชื่อ ต้นไม้แบบที มาจากรูปร่างของปมที่มีลักษณะเหมือนตัวอักษรในภาษาอังกฤษตัว T[1]
ประสิทธิภาพ
แม้ว่าต้นไม้แบบทีจะถูกนำมาใช้กันอย่างแพร่หลายสำหรับฐานข้อมูลหน่วยความจำหลัก แต่การวิจัย[2][3]เมื่อเร็วๆ นี้แสดงให้เห็นว่าจริงๆ แล้วมันไม่ได้ทำงานได้ดีกว่า ต้นไม้แบบบี เลย เมื่อใช้กับฮาร์ดแวร์สมัยใหม่
เหตุผลหลักน่าจะเป็นเพราะว่าสมมติฐานแบบเดิมที่บอกว่าอัตราการเข้าถึงแคชและหน่วยความจำหลักเท่ากันใช้ไม่ได้อีกต่อไป เนื่องจากในปัจจุบันอัตราการเข้าถึงแคชจะเร็วกว่าหน่วยความจำหลักมาก
โครงสร้างปม
โครงสร้างปมของต้นไม้แบบที
ต้นไม้แบบที ประกอบจะประกอบไปด้วย ตัวชี้ไปยังปมพ่อ ตัวชี้ไปยังปมลูกซ้ายและขวา แถวลำดับของตัวชี้ข้อมูล และข้อมูลการควบคุมพิเศษ
ปมที่มีต้นไม้ย่อย (subtree) สองต้น เรียกว่า ปมภายใน (internal nodes) ปมที่ไม่มีต้นไม้ย่อย เรียกว่า ปมใบ (leaf nodes) และปมที่มีต้นไม้ย่อยเพียงแต่ต้นเดียว เรียกว่า ปมครึ่งใบ (half-leaf nodes) ปมจะถูกเรียกว่า ปมขอบเขต (bounding node) สำหรับค่าหนึ่ง ถ้าค่านั้นอยู่ระหว่างค่าน้อยสุดและมากสุดของปมนั้น
ค่าขอบเขต
ค่าที่มากที่สุดในต้นไม้ย่อยซ้ายของแต่ละปมภายใน เรียกว่า ขอบเขตล่างมากสุด (greatest lower bound) ค่าที่น้อยที่สุดในต้นไม้ย่อยขวาของแต่ละปมภายใน เรียกว่า ขอบเขตบนน้อยสุด (least upper bound) ซึ่งค่าทั้งสองนี้จะอยู่ที่ปมใบหรือปมครึ่งใบเสมอ ปมใบและปมครึ่งใบสามารถมีจำนวนข้อมูลได้ตั้งแต่หนึ่งจนถึงขนาดของแถวลำดับข้อมูล แต่จำนวนข้อมูลขั้นต่ำและมากสุดของปมภายในจะถูกกำหนดไว้ล่วงหน้าแล้ว
การสร้างบริการ
การค้นหาสมาชิก
- เริ่มค้นที่ปมราก
- ถ้าปมนั้นเป็นปมขอบเขตสำหรับค่าที่ต้องการหา จึงค้นค่าในแถวลำดับของข้อมูลของปมนั้น ถ้าไม่พบแสดงว่าไม่มีค่านั้นอยู่
- ถ้าค่าที่ต้องการหามีค่าน้อยกว่าค่าน้อยสุดของปมนั้น ให้ค้นต่อที่ต้นไม้ย่อยซ้ายของมัน ถ้าไม่มีต้นไม้ย่อยซ้ายแสดงว่าไม่มีค่านั้นอยู่
- ถ้าค่าที่ต้องการหามีค่ามากกว่าค่ามากสุดของปมนั้น ให้ค้นต่อที่ต้นไม้ย่อยขวาของมัน ถ้าไม่มีต้นไม้ย่อยขวาแสดงว่าไม่มีค่านั้นอยู่
การเพิ่มสมาชิก
- ค้นหาปมขอบเขตของค่าที่ต้องการเพิ่ม ถ้ามีอยู่แล้ว
- ตรวจสอบว่ายังคงมีพื้นที่ว่างในแถวลำดับข้อมูลหรือไม่ ถ้ามีให้เพิ่มค่าใหม่และเสร็จสิ้น
- ถ้าไม่มีพื้นที่ว่างเหลือ ให้ลบตัวที่มีค่าน้อยสุดในปมนั้นและใส่ค่าใหม่ลงไป จากนั้นไปยังปมที่เก็บค่าขอบเขตล่างมากสุดไว้ เพื่อใส่ค่าน้อยสุดที่เคยลบไป ถ้าสามารถใส่ได้ให้ใส่เป็นค่ามากสุดของปมนี้ ถ้าใส่ไม่ได้ให้สร้างปมย่อยขวาใหม่แล้วใส่ค่าลงไป
- ถ้าไม่พบปมขอบเขตอยู่ ให้ใส่ค่าใหม่ในปมสุดท้ายที่ค้น ถ้าใส่ได้ค่าใหม่นี้จะกลายเป็นค่าน้อยสุดหรือไม่ก็มากสุดของปมนั้น ถ้าใส่ไม่ได้ให้สร้างต้นไม้ย่อยซ้ายหรือขวาใหม่
ถ้ามีการเพิ่มปมใหม่ ต้นไม้อาจจำเป็นต้องปรับสมดุล (rebalanced) จะอธิบายด้านล่าง
การลบสมาชิก
- ค้นหาปมขอบเขตของค่าที่ต้องการลบ ถ้าไม่พบแล้วเสร็จสิ้น
- ถ้าปมขอบเขตไม่ได้เก็บค่าที่ต้องการลบ แล้วเสร็จสิ้น
- ลบค่าจากแถวลำดับของปมนั้น หลังจากลบแล้วให้ดำเนินการตามประเภทของปม ดังนี้
- ปมภายใน: ถ้าจำนวนข้อมูลในแถวลำดับข้อมูลมีจำนวนน้อยกว่าขั้นต่ำที่จะใส่ได้ ให้ย้ายค่าขอบเขตล่างมากสุดของปมนี้มาใส่ หลังจากนั้นให้ดำเนินการตามหนึ่งในสองขั้นตอน สำหรับการลบออกจากปมใบ หรือปมครึ่งใบ
- ปมใบ: ถ้าปมนี้มีข้อมูลเพียงตัวเดียวในแถวลำดับข้อมูล ให้ลบปมนี้ทิ้ง จากนั้นปรับสมดุลหากจำเป็น
- ปมครึ่งใบ: ถ้าแถวลำดับของปมนี้สามารถผสานกับแถวลำดับของปมใบของปมนี้ได้โดยไม่เกินจำนวนมากสุดที่ใส่ได้ ให้ผสานกันและลบปมใบทิ้ง จากนั้นปรับสมดุลหากจำเป็น
การหมุนและการปรับสมดุล
ต้นไม้แบบทีจะดำเนินการบนพื้นฐานของ ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (Self-balancing binary search tree) โดยเฉพาะตามที่บทความของ Lehman และ Carey[1] ได้อธิบายไว้ว่าต้นไม้แบบทีจะปรับสมดุลเหมือนกับต้นไม้เอวีแอล ที่ว่ามันจะไม่สมดุลเมื่อปมลูกมีความสูงต่างกันอย่างน้อยสองระดับ กรณีนี้จะเกิดขึ้นหลักจากทำการเพิ่มหรือลบปม ซึ่งหลังจากทำการเพิ่มหรือลบปมแล้ว ต้นไม้จะถูกตรวจจากใบไปยังราก ถ้าตรวจพบว่าไม่สมดุลก็จะทำการหมุนหนึ่งหรือสองครั้ง ทำให้สามารถประกันได้ว่าต้นไม้จะสมดุลเสมอ
เมื่อหมุนเสร็จแล้วปมภายในมีจำนวนข้อมูลน้อยกว่าขั้นต่ำที่ใส่ได้ให้ย้ายข้อมูลจากปมลูกมาใส่ในปมภายในนี้ (อาจมากกว่าหนึ่งปม)
ดูเพิ่ม
ต้นไม้แบบอื่น
อ้างอิง
