ต้นไม้ที่สมดุลน้ำหนัก
พิมพ์	ต้นไม้
ประดิษฐ์	พ.ศ. 2515
คิดค้นโดย	โดย:เจอร์ก นีเวอร์เกลต์และเอ็ดเวิร์ด ไรน์โกลด์
ความซับซ้อนในสัญกรณ์บิ๊กโอ
ความซับซ้อนของพื้นที่ ช่องว่าง ${\displaystyle O(n)}$ ความซับซ้อนเชิงเวลา การทำงาน ตัดจำหน่าย กรณีที่เลวร้ายที่สุด ค้นหา ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ แทรก ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ ลบ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

ในวิทยาการคอมพิวเตอร์ต้นไม้ไบนารีที่สมดุลน้ำหนัก ( WBTs ) เป็น ต้นไม้ค้นหาไบนารีแบบสมดุลตัวเองชนิดหนึ่งที่สามารถใช้ในการสร้างเซตแบบไดนามิกพจนานุกรม(แผนที่) และลำดับ^{[ 1 ]}ต้นไม้เหล่านี้ได้รับการแนะนำโดย Nievergelt และ Reingold ในช่วงทศวรรษ 1970 ในชื่อต้นไม้สมดุลแบบจำกัดหรือต้นไม้BB[α] ^{[ 2 ] [ 3 ]} ชื่อที่ใช้กันทั่วไป ของต้นไม้เหล่านี้มาจากKnuth ^{[ 4 ]}

ตัวอย่างที่รู้จักกันดีคือการ เข้ารหัสแบบฮัฟฟ์แมนของคลังข้อมูล

เช่นเดียวกับต้นไม้ปรับสมดุลตัวเองอื่นๆ WBT จะเก็บข้อมูลบัญชีที่เกี่ยวข้องกับความสมดุลไว้ในโหนด และดำเนินการหมุนเพื่อคืนความสมดุลเมื่อถูกรบกวนจากการแทรกหรือการลบ โดยเฉพาะอย่างยิ่ง แต่ละโหนดจะเก็บขนาดของซับทรีที่รากอยู่ที่โหนดนั้น และขนาดของซับทรีด้านซ้ายและด้านขวาจะอยู่ภายในปัจจัยบางอย่างของกันและกัน แตกต่างจากข้อมูลความสมดุลในต้นไม้ AVL (โดยใช้ข้อมูลเกี่ยวกับความสูงของซับทรี) และต้นไม้แดง-ดำ (ซึ่งเก็บบิต "สี" สมมติ) ข้อมูลบัญชีใน WBT เป็นคุณสมบัติที่มีประโยชน์จริงสำหรับแอปพลิเคชัน: จำนวนองค์ประกอบในต้นไม้เท่ากับขนาดของราก และข้อมูลขนาดเป็นข้อมูลที่จำเป็นในการดำเนินการของต้นไม้สถิติลำดับเช่น การหา องค์ประกอบที่ใหญ่ที่สุดลำดับที่ nในชุด หรือการกำหนดดัชนีขององค์ประกอบในลำดับที่เรียงแล้ว^{[ 5 ]}

ต้นไม้ที่มีน้ำหนักสมดุลเป็นที่นิยมใน ชุมชน การเขียนโปรแกรมเชิงฟังก์ชันและใช้ในการนำเซตและแผนที่ไปใช้ในMIT Scheme , SLIB , SML-NJและการใช้งานHaskell ^{[ 6 ] [ 4 ]}

ต้นไม้สมดุลน้ำหนัก (Weight-balanced tree) คือต้นไม้ค้นหาแบบไบนารี (Binary search tree) ที่เก็บขนาดของต้นไม้ย่อยไว้ในโหนด กล่าวคือ โหนดจะมีฟิลด์ต่างๆ

• กุญแจของประเภทที่เรียงลำดับใดๆ ก็ได้
• ค่า (ไม่บังคับ ใช้สำหรับกำหนดค่าเท่านั้น)
• ซ้ายขวาตัวชี้ไปยังโหนด
• ขนาดชนิดข้อมูลจำนวนเต็ม

ตามคำจำกัดความ ขนาดของใบ (โดยทั่วไปแสดงด้วย ตัวชี้ที่ เป็นค่าว่าง ) คือศูนย์ ขนาดของโหนดภายในคือผลรวมของขนาดของลูกสองตัวบวกหนึ่ง: ( size[n] = size[n.left] + size[n.right] + 1 ) โดยอิงจากขนาด เรากำหนดน้ำหนักเป็นweight[n] = size[n] + 1 [ ^{a ] ​​ข้อดี}ของ weight คือ น้ำหนักของโหนดเป็นเพียงผลรวมของน้ำหนักของลูกซ้ายและขวา

การดำเนินการที่แก้ไขโครงสร้างต้นไม้จะต้องตรวจสอบให้แน่ใจว่าน้ำหนักของต้นไม้ย่อยด้านซ้ายและด้านขวาของแต่ละโหนดนั้นยังคงอยู่ในช่วงค่าตัวประกอบαของกันและกัน โดยใช้การดำเนินการปรับสมดุล แบบเดียวกันกับ ที่ใช้ในต้นไม้ AVLได้แก่ การหมุนและการหมุนสองครั้ง ในทางทฤษฎีแล้ว การปรับสมดุลของโหนดนั้นกำหนดไว้ดังนี้:

โหนดจะสมดุลน้ำหนักα ถ้า weight[n.left] ≥ α·weight[n]และweight[n.right] ≥ α·weight[n ^] [ ^{7 ]}

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

${\displaystyle \alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289}$

เป็นเงื่อนไขที่จำเป็นสำหรับการทำงาน ของอัลกอริธึมการปรับสมดุล งานวิจัยในภายหลังแสดงให้เห็นขอบเขตล่างของα ที่2/11 แม้ว่าจะสามารถทำให้เล็กลงได้ตามอำเภอใจหากใช้อัลกอริธึมการปรับสมดุลแบบกำหนดเอง (และซับซ้อนกว่า) ^{[ 7 ]}

การใช้การปรับสมดุลอย่างถูกต้องจะรับประกันว่าต้นไม้ที่มีองค์ประกอบn จะมีความสูง ^{[ 7 ]}

${\displaystyle h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)}$

ถ้า กำหนดค่า αเป็นค่าสูงสุดที่อนุญาต ความสูงในกรณีที่เลวร้ายที่สุดของต้นไม้ที่มีการปรับสมดุลน้ำหนักจะเท่ากับความสูงของต้นไม้แดง-ดำที่ค่าα = 0 ${\displaystyle 2\log _{2}n}$

จำนวนการดำเนินการปรับสมดุลที่จำเป็นในลำดับการแทรกและการลบn ครั้งนั้นเป็นเชิงเส้นตาม nกล่าวคือ การปรับสมดุลใช้ค่าใช้จ่ายคงที่ในแง่ ของ ค่าเฉลี่ย^{[ 8 ]}

ในขณะที่การรักษาต้นไม้ด้วยต้นทุนการค้นหาขั้นต่ำต้องใช้การหมุนคู่สี่ประเภท (LL, LR, RL, RR เหมือนในต้นไม้ AVL) ในการดำเนินการแทรก/ลบ หากเราต้องการประสิทธิภาพแบบลอการิทึมเท่านั้น LR และ RL จะเป็นการหมุนเพียงประเภทเดียวที่จำเป็นในการดำเนินการแบบบนลงล่างเพียงครั้งเดียว^{[ 9 ]}

มีการกำหนดการดำเนินการเซตหลายอย่างบนต้นไม้สมดุลน้ำหนัก ได้แก่ยูเนียนอินเตอร์เซกชันและผลต่างเซต จากนั้นจึงสามารถดำเนินการจำนวนมาก อย่างรวดเร็วในการแทรกหรือลบโดยอาศัยฟังก์ชันเซตเหล่านี้ การดำเนินการเซตเหล่านี้อาศัยการดำเนินการช่วยเหลือสองอย่างคือ สปลิตและจอยน์ด้วยการดำเนินการใหม่เหล่านี้ การใช้งานต้นไม้สมดุลน้ำหนักจึงมีประสิทธิภาพมากขึ้นและสามารถขนานได้สูง^{[ 10 ] [ 11 ]}

เข้าร่วม

ฟังก์ชันJoinทำงานกับต้นไม้สองต้นที่มีน้ำหนักสมดุลกัน_t1 และ t2 และคีย์kโดยจะส่งคืนต้นไม้ที่มีองค์ประกอบทั้งหมดในt1 , t2รวมถึง_{k ด้วย ฟังก์ชันนี้}ต้องการ ให้ kมากกว่าคีย์ทั้งหมดในt1และน้อยกว่าคีย์ทั้งหมดใน_t2ถ้าต้นไม้ทั้งสองมีน้ำหนักสมดุลกัน ฟังก์ชันJoin _{จะสร้างโหนดใหม่ที่มีซับทรีด้านซ้ายเป็น t1} ,รูทเป็น k และซับทรีด้านขวาเป็น t2 สมมติว่า t1 มีน้ำหนักมากกว่า t2 (กรณีอื่นจะสมมาตรกัน) ฟังก์ชัน Join จะตามแกนด้านขวาของ t1 ไปจนถึงโหนด c ซึ่งสมดุลกับ t2 ณ จุดนี้ โหนดใหม่_ที่มีลูกด้านซ้าย_เป็นc , รูทเป็น_kและ_ลูกด้านขวาเป็น t2 จะถูก_{สร้าง}ขึ้นเพื่อแทนที่cโหนด_ใหม่นี้ อาจทำให้สมดุลน้ำหนักไม่เป็นไปตามเงื่อนไข สามารถแก้ไขได้ด้วยการหมุนครั้งเดียวหรือสอง _{ครั้ง โดยสมมติ} ว่า ...${\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}$

แยก

ในการแบ่งต้นไม้ที่มีการปรับสมดุลน้ำหนักออกเป็นสองต้นไม้เล็กๆ คือ ต้นไม้ที่มีน้ำหนักน้อยกว่าคีย์xและต้นไม้ที่มีน้ำหนักมากกว่าคีย์xขั้นแรกให้ลากเส้นทางจากรากโดยการแทรกxเข้าไปในต้นไม้ หลังจากแทรกแล้ว ค่าทั้งหมดที่น้อยกว่าxจะอยู่ทางด้านซ้ายของเส้นทาง และค่าทั้งหมดที่มากกว่าxจะอยู่ทางด้านขวา โดยการใช้Joinต้นไม้ย่อยทั้งหมดทางด้านซ้ายจะถูกรวมเข้าด้วยกันจากล่างขึ้นบนโดยใช้คีย์บนเส้นทางเป็นโหนดกลางจากล่างขึ้นบนเพื่อสร้างต้นไม้ด้านซ้าย และส่วนด้านขวาจะสมมาตรกัน สำหรับบางแอปพลิเคชันSplitยังส่งคืนค่าบูลีนที่ระบุว่าxปรากฏในต้นไม้หรือไม่ ค่าใช้จ่ายของSplitคือซึ่งเป็นลำดับของความสูงของต้นไม้ อัลกอริทึมนี้ไม่มีส่วนเกี่ยวข้องกับคุณสมบัติพิเศษใดๆ ของต้นไม้ที่มีการปรับสมดุลน้ำหนัก ดังนั้นจึงสามารถใช้ได้กับวิธีการปรับสมดุลอื่นๆ เช่นต้นไม้ AVL${\displaystyle O(\log n)}$

อัลกอริทึมการรวมข้อมูลมีดังนี้:

ฟังก์ชัน joinRightWB(T L , k, T R ) (l, k', c) = expose(T L ) if balance(|T L |, |T R |) return Node(T L , k, T R ) else T' = joinRightWB(c, k, T R ) (l', k', r') = เปิดเผย(T') ถ้า (สมดุล(|l|,|T'|)) ให้คืนค่า Node(l, k', T') มิฉะนั้น ถ้า (สมดุล(|l|,|l'|) และสมดุล(|l|+|l'|,|r'|)) ให้คืนค่า rotateLeft(Node(l, k', T')) มิฉะนั้นให้คืนค่า rotateLeft(Node(l, k', rotateRight(T')) function joinLeftWB(T L , k, T R ) /* สมมาตรกับ joinRightWB */ ฟังก์ชัน join(T L , k, T R ) ถ้า (heavy(T L , T R )) ให้คืนค่า joinRightWB(T L , k, T R ) ถ้า (heavy(T R , T L )) ให้คืนค่า joinLeftWB(T L , k, T R ) โหนด(T L , k, T R ) 

ในที่นี้ balance หมายถึงน้ำหนักสองค่าTและTมีความสมดุลกัน expose(v)=(l, k, r) หมายถึงการดึงโหนดลูกซ้าย T ของโหนดต้นไม้T , คีย์ของโหนดTและโหนดลูกขวาT Node(l, k, r) หมายถึงการสร้างโหนดจากโหนดลูกซ้ายT , คีย์Tและโหนดลูกขวา T${\displaystyle (x,y)}$

ขั้นตอนการแบ่งแยกมีดังนี้:

ฟังก์ชัน split(T, k) ถ้า (T = nil) ให้คืนค่า (nil, false, nil) (L, (m, c), R) = เปิดเผย(T) ถ้า k = m ให้ส่งคืน (L, true, R) ถ้า k < m (L', b, R') = แยก (L, k) ส่งคืน (L', b, เข้าร่วม (R', m, R)) ถ้า (k > m) (L', b, R') = แยก (R, k) ส่งคืน (join(L, m, L'), b, R)) 

การรวมกันของต้นไม้สมดุลน้ำหนักสองต้นt ₁และt ₂ซึ่งแทนเซตAและBคือต้นไม้สมดุลน้ำหนักtที่แทนA ∪ Bฟังก์ชันเรียกซ้ำต่อไปนี้คำนวณการรวมกันนี้:

ฟังก์ชัน union(t 1 , t 2 ): ถ้า t 1 = nil: คืนค่า t 2 ถ้า t 2 = nil: คืนค่า t 1 t < , t > ← แยก t 2ตาม t 1 .root คืนค่า join(union(left(t 1 ), t < ), t 1 .root, union(right(t 1 ), t > )) 

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

อัลกอริทึมสำหรับการหาจุดร่วมหรือความแตกต่างนั้นคล้ายคลึงกัน แต่ต้องใช้ รูทีนตัวช่วย Join2ซึ่งเหมือนกับJoinแต่ไม่มีคีย์ตรงกลาง โดยอาศัยฟังก์ชันใหม่สำหรับการรวม การหาจุดร่วม หรือความแตกต่าง สามารถแทรกหรือลบคีย์เดียวหรือหลายคีย์ออกจากต้นไม้ที่มีการปรับสมดุลน้ำหนักได้ เนื่องจากSplitและUnionเรียกใช้Joinแต่ไม่ได้จัดการกับเกณฑ์การปรับสมดุลของต้นไม้ที่มีการปรับสมดุลน้ำหนักโดยตรง การใช้งานในลักษณะนี้จึงมักเรียกว่า อั ลก อริทึมแบบ Join

ความซับซ้อนของการรวม การตัดกัน และความแตกต่างแต่ละอย่างนั้นสำหรับต้นไม้สมดุลน้ำหนักสองต้นที่มีขนาดTและความซับซ้อนนี้เหมาะสมที่สุดในแง่ของจำนวนการเปรียบเทียบ ที่สำคัญกว่านั้น เนื่องจากคำสั่งเรียกซ้ำสำหรับการรวม การตัดกัน หรือความแตกต่างเป็นอิสระต่อกัน จึงสามารถดำเนินการแบบขนานได้ด้วยความลึกแบบขนาน [ ^{10 ] เมื่อ}การใช้งานแบบรวมจะมีกราฟแบบไม่มีวงจร (DAG) ที่มีทิศทางการคำนวณเหมือนกับการแทรกและการลบองค์ประกอบเดี่ยว หากใช้รากของต้นไม้ที่ใหญ่กว่าเพื่อแยกต้นไม้ที่เล็กกว่า ${\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}$${\displaystyle n(\geq m)}$${\displaystyle O(\log m\log n)}$${\displaystyle m=1}$