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

ในวิทยาการคอมพิวเตอร์ต้นไม้WAVLหรือต้นไม้ AVL แบบอ่อนคือต้นไม้ค้นหาแบบไบนารีที่สมดุลในตัวเองต้นไม้ WAVL ได้รับการตั้งชื่อตามต้นไม้ AVLซึ่งเป็นต้นไม้ค้นหาแบบสมดุลอีกประเภทหนึ่ง และมีความสัมพันธ์อย่างใกล้ชิดกับทั้งต้นไม้ AVL และต้นไม้แดง-ดำซึ่งทั้งหมดอยู่ในกรอบงานทั่วไปของต้นไม้ที่สมดุลอันดับเช่นเดียวกับต้นไม้ค้นหาแบบไบนารีแบบสมดุลอื่นๆ ต้นไม้ WAVL สามารถจัดการการแทรก การลบ และการค้นหาได้ในเวลาO (log n )ต่อการดำเนินการ^{[ 1 ] [ 2 ]}

ต้นไม้ WAVL ได้รับการออกแบบมาเพื่อรวมคุณสมบัติที่ดีที่สุดของทั้งต้นไม้ AVL และต้นไม้แดง-ดำ ข้อดีอย่างหนึ่งของต้นไม้ AVL เหนือต้นไม้แดง-ดำคือมีความสมดุลมากกว่า กล่าวคือ มีความสูงสูงสุด(สำหรับต้นไม้ที่มีรายการข้อมูลn รายการ โดยที่ คืออัตราส่วนทองคำ ) ในขณะที่ต้นไม้แดง-ดำมีความสูงสูงสุดที่มากกว่าหากสร้างต้นไม้ WAVL โดยใช้การแทรกเท่านั้น โดยไม่มีการลบ ต้นไม้ WAVL จะมีความสูงจำกัดที่เล็กเท่ากับต้นไม้ AVL ในทางกลับกัน ต้นไม้แดง-ดำมีข้อได้เปรียบเหนือต้นไม้ AVL ในด้านการปรับโครงสร้างต้นไม้ที่น้อยกว่า ในต้นไม้ AVL การลบแต่ละครั้งอาจต้องใช้ การ หมุนต้นไม้ จำนวนลอการิทึม ในขณะที่ต้นไม้แดง-ดำมีการดำเนินการลบที่ง่ายกว่าซึ่งใช้การหมุนต้นไม้จำนวนคงที่เท่านั้น ต้นไม้ WAVL เช่นเดียวกับต้นไม้แดง-ดำ ใช้การหมุนต้นไม้จำนวนคงที่เท่านั้น และค่าคงที่นี้ดีกว่าต้นไม้แดง-ดำเสียอีก^{[ 1 ] [ 2 ]}${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$${\displaystyle \varphi }$${\displaystyle 2\log _{2}n}$

ต้นไม้ WAVL ได้รับการแนะนำโดยHaeupler, Sen & Tarjan (2015)ผู้เขียนเดียวกันนี้ยังได้เสนอมุมมองทั่วไปเกี่ยวกับต้นไม้ AVL ต้นไม้ WAVL และต้นไม้แดง-ดำ ว่าเป็นต้นไม้ที่มีสมดุลลำดับชั้นประเภทเดียวกัน^{[ 2 ]}

ต้นไม้ค้นหาแบบไบนารีแต่ละชนิดมีอัลกอริธึมที่แตกต่างกันสำหรับการแทรก/ลบและการปรับสมดุล ทำให้ยากต่อการศึกษาอย่างเป็นระบบ ผู้เขียนHaeupler, Sen & Tarjan (2015)ได้นำเสนอเฟรมเวิร์กต้นไม้สมดุลอันดับ (rank balanced trees framework) เพื่อรวมการศึกษาต้นไม้ค้นหาแบบไบนารีเข้าด้วยกัน โดยการกำหนดต้นไม้ไบนารีอันดับ และต้นไม้ค้นหาแบบไบนารีแต่ละชนิดจะปฏิบัติตามข้อจำกัดเฉพาะที่ใช้กับฟังก์ชันอันดับ โปรดทราบว่าเฟรมเวิร์กนี้ไม่ได้ระบุอัลกอริธึมที่ใช้ในการสร้างต้นไม้เหล่านี้

ต้นไม้ไบนารีแบบมีอันดับ (Rank Binary Tree) คือต้นไม้ไบนารีที่แต่ละโหนด x จะมีอันดับ r(x) ตามธรรมเนียม โหนดว่างจะมีอันดับ -1 สำหรับโหนด x ที่ไม่ใช่โหนดรากผลต่างของอันดับคือiและโหนดดังกล่าวเรียกว่าโหนดลูกที่ i ถ้าผลต่างของอันดับคือ i โหนดจะเป็นแบบ i ถ้าผลต่างของอันดับระหว่างโหนดลูกซ้ายและโหนดลูกขวาคือ i และ j (โดยไม่คำนึงถึงลำดับ) ${\displaystyle r(p(x))-r(x)}$${\displaystyle i,j}$

ด้วยเหตุนี้ เราจึงสามารถกำหนดกฎเพิ่มเติม ซึ่งสอดคล้องกับโครงสร้างต้นไม้ที่แตกต่างกันได้:

• กฎ AVL ซึ่งสอดคล้องกับโครงสร้างต้นไม้ AVL : โหนดแต่ละโหนดเป็นประเภท 1,1 หรือ 1,2
• กฎ 2-3 ซึ่งสอดคล้องกับต้นไม้ 2-3 แบบไบนารี: แต่ละโหนดมีประเภท 0,1 หรือ 1,1 และไม่มีโหนดแม่ของโหนดลูก 0 ใดเป็นโหนดลูก 0 เช่นกัน
• กฎแดงดำ ซึ่งสอดคล้องกับต้นไม้แดงดำ : ผลต่างของลำดับทั้งหมดเป็น 0 หรือ 1 และไม่มีโหนดแม่ของโหนดลูกที่เป็น 0 โหนดใดเป็นโหนดลูกที่เป็น 0 โปรดทราบว่ากฎแดงดำเป็นการขยายกฎ 2-3 โดยอนุญาตให้มีโหนดประเภท 0,0 ได้

จนถึงตอนนี้ กฎทั้งหมดเหล่านี้มีความสมมาตรสำหรับโหนดด้านซ้ายและโหนดด้านขวา การทำลายความสมมาตรดังกล่าวจะก่อให้เกิดกฎอื่นๆ ขึ้นมา:

• กฎสองสามแบบเอนขวา ซึ่งสอดคล้องกับต้นไม้ไบนารี 2-3 แบบเอนขวา: ทุกโหนดเป็น 1,1 หรือ 0,1 ไม่มีโหนดแม่ของโหนดลูก 0 ที่เป็นโหนดลูก 0 และไม่มีโหนดลูก 0 ที่เหลืออยู่
• กฎสองสามแบบเอนซ้าย ซึ่งสอดคล้องกับต้นไม้ไบนารี 2-3 แบบเอนซ้าย: ทุกโหนดเป็น 1,1 หรือ 0,1 ไม่มีโหนดแม่ของโหนดลูก 0 ที่เป็นโหนดลูก 0 และไม่มีโหนดลูก 0 ที่เป็นโหนดขวา
• กฎแดง-ดำแบบเอนไปทางขวา ซึ่งสอดคล้องกับต้นไม้แดง-ดำแบบเอนไปทาง Reft: ไม่มีผู้ปกครองของโหนดลูก 0 ที่เป็นโหนดลูก 0 และไม่มีโหนดลูก 0 ของโหนด 0,1 ที่เป็นโหนดซ้าย
• กฎแดงดำแบบเอนซ้าย ซึ่งสอดคล้องกับต้นไม้แดงดำแบบเอนซ้าย : ผลต่างของลำดับทั้งหมดเป็น 0 หรือ 1 ไม่มีผู้ปกครองของลูกที่มีลำดับ 0 เป็นลูกที่มีลำดับ 0 และไม่มีลูกที่มีลำดับ 0 ของโหนดที่มีลำดับ 0,1 อยู่ทางขวา

ต้นไม้ AVL แบบอ่อนถูกกำหนดโดยกฎ AVL แบบอ่อน:

• กฎ AVL แบบอ่อน: ผลต่างของอันดับทั้งหมดเป็น 1 หรือ 2 และโหนดใบทั้งหมดมีอันดับ 0

โปรดทราบว่าต้นไม้ AVL แบบอ่อน (weak AVL tree) เป็นการขยายแนวคิดของต้นไม้ AVL โดยอนุญาตให้มีโหนดประเภท 2,2 ได้ การพิสูจน์อย่างง่ายแสดงให้เห็นว่าต้นไม้ AVL แบบอ่อนสามารถระบายสีได้ในลักษณะที่แสดงถึงต้นไม้แดง-ดำ (red-black tree) ดังนั้นในแง่หนึ่ง ต้นไม้ AVL แบบอ่อนจึงรวมคุณสมบัติของต้นไม้ AVL และต้นไม้แดง-ดำเข้าด้วยกัน

เช่นเดียวกับต้นไม้ค้นหาแบบไบนารีโดยทั่วไป ต้นไม้ WAVL ประกอบด้วยชุดของโหนด 2 ประเภท ได้แก่ โหนดภายในและโหนดภายนอก โหนดภายในจะเก็บรายการข้อมูล และเชื่อมโยงกับโหนดแม่ (ยกเว้นโหนดรากที่กำหนดไว้ซึ่งไม่มีโหนดแม่) และกับโหนดลูกสองตัวในต้นไม้ คือ โหนดลูกซ้ายและโหนดลูกขวา โหนดภายนอกไม่มีข้อมูล และเชื่อมโยงกับโหนดแม่ในต้นไม้เท่านั้น โหนดเหล่านี้ถูกจัดเรียงเพื่อสร้างต้นไม้ไบนารี ดังนั้นสำหรับโหนดภายในx ใดๆ โหนดแม่ของโหนดลูกซ้ายและโหนดลูกขวาของx ก็ คือxเอง โหนดภายนอกจะสร้างใบของต้นไม้^{[ 3 ]}รายการข้อมูลจะถูกจัดเรียงในต้นไม้ในลักษณะที่การท่องต้นไม้แบบอินออร์เดอร์จะแสดงรายการข้อมูลตามลำดับที่เรียงแล้ว^{[ 4 ]}

สิ่งที่ทำให้ต้นไม้ WAVL แตกต่างจากต้นไม้ค้นหาแบบไบนารีประเภทอื่นคือการใช้ลำดับ (ranks ) ซึ่งเป็นตัวเลขที่เชื่อมโยงกับแต่ละโหนด โดยให้ค่าประมาณระยะทางจากโหนดไปยังโหนดลูกหลานใบที่ไกลที่สุด ต่างจากต้นไม้ AVL ที่ลำดับถูกกำหนดให้เท่ากับความสูงของโหนด ในต้นไม้ WAVL ลำดับจะไม่เท่ากับความสูงเสมอไปความแตกต่างของลำดับของโหนด x ถูกกำหนดให้เป็นผลต่างระหว่างลำดับของโหนดแม่ของ x และลำดับของ x ลำดับจะต้องเป็นไปตามคุณสมบัติต่อไปนี้: ^{[ 1 ] [ 2 ]}

• คุณสมบัติโหนดภายนอก: โหนดภายนอกทุกโหนดมีลำดับที่0 ^{[ 5 ]}
• คุณสมบัติความแตกต่างของอันดับ: ถ้าโหนดที่ไม่ใช่โหนดรากมีอันดับrอันดับของโหนดแม่จะต้องเป็นr + 1หรือr + 2กล่าวอีกนัยหนึ่ง ความแตกต่างของอันดับสำหรับโหนดที่ไม่ใช่โหนดรากใดๆ ก็คือ 1 หรือ 2 ^{[ 1 ]}
• คุณสมบัติของโหนดภายใน: โหนดภายในที่มีโหนดลูกภายนอกสองโหนดจะต้องมีลำดับชั้นเท่ากับ 1 พอดี

การค้นหาคีย์kในต้นไม้ WAVL นั้นคล้ายคลึงกับการค้นหาในโครงสร้างข้อมูลต้นไม้ค้นหาไบนารีแบบสมดุลทั่วไป โดยเริ่มจากรากของต้นไม้ จากนั้นเปรียบเทียบkกับรายการข้อมูลที่จัดเก็บไว้ที่แต่ละโหนดบนเส้นทางจากรากซ้ำๆ โดยตามเส้นทางไปยังลูกทางซ้ายของโหนดเมื่อkน้อยกว่าค่าที่โหนดนั้น หรือตามเส้นทางไปยังลูกทางขวาเมื่อkมากกว่าค่าที่โหนดนั้น เมื่อถึงโหนดที่มีค่าเท่ากับkหรือถึงโหนดภายนอก การค้นหาจะหยุดลง^{[ 6 ]}

หากการค้นหาหยุดที่โหนดภายใน แสดงว่าพบคีย์k แล้ว หากการค้นหาหยุดที่โหนดภายนอก แสดง ว่าพบตำแหน่งที่จะแทรกk (หากมีการแทรก) แล้ว ^{[ 6 ]}

การแทรกโหนดภายในที่มีคีย์kลงในต้นไม้ WAVL จำเป็นต้องค้นหาkในต้นไม้ โดยสิ้นสุดที่โหนดภายนอก จากนั้นจึงแทนที่โหนดภายนอกนั้นด้วยโหนดภายในใหม่ที่มีลูกภายนอกสองตัว และสุดท้ายคือการปรับสมดุลต้นไม้ ขั้นตอนการปรับสมดุลสามารถทำได้ทั้งแบบบนลงล่างหรือล่างขึ้นบน^{[ 2 ]}แต่การปรับสมดุลแบบล่างขึ้นบนนั้นตรงกับต้นไม้ AVL มากที่สุด^{[ 1 ] [ 2 ]}

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

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

ดังนั้นโดยรวมแล้ว ขั้นตอนการแทรกประกอบด้วยการค้นหา การสร้างโหนดใหม่จำนวนคงที่ การเปลี่ยนแปลงลำดับจำนวนลอการิทึม และการหมุนต้นไม้จำนวนคงที่^{[ 1 ] [ 2 ]}

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

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

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

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

โดยรวมแล้ว การลบประกอบด้วยการค้นหาลงไปหาโหนดที่มีลูกภายนอก การลบโหนดใหม่จำนวนคงที่ การเปลี่ยนแปลงลำดับจำนวนลอการิทึม และการหมุนต้นไม้จำนวนคงที่[1][2]

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

การค้นหา การแทรก หรือการลบแต่ละครั้งในต้นไม้ WAVL เกี่ยวข้องกับการเดินตามเส้นทางเดียวในต้นไม้และดำเนินการตามขั้นตอนจำนวนคงที่สำหรับแต่ละโหนดในเส้นทางนั้น ในต้นไม้ WAVL ที่มี รายการ nรายการซึ่งมีการแทรกเพียงอย่างเดียว ความยาวเส้นทางสูงสุดคือถ้ามีการแทรกและการลบเกิดขึ้น ความยาวเส้นทางสูงสุดคือดังนั้น ในทั้งสองกรณี เวลาในกรณีที่เลวร้ายที่สุดสำหรับการค้นหา การแทรก หรือการลบแต่ละครั้งในต้นไม้ WAVL ที่มี รายการข้อมูล nรายการคือO ( log n )${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$${\displaystyle 2\log _{2}n}$

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

ต้นไม้ WAVL มีความสัมพันธ์อย่างใกล้ชิดกับทั้งต้นไม้ AVLและต้นไม้แดง-ดำ ต้นไม้ AVL ทุกต้นสามารถกำหนดลำดับชั้นให้กับโหนดได้ในลักษณะที่ทำให้มันกลายเป็นต้นไม้ WAVL และต้นไม้ WAVL ทุกต้นสามารถระบายสีโหนดเป็นสีแดงและดำ (และกำหนดลำดับชั้นใหม่) ในลักษณะที่ทำให้มันกลายเป็นต้นไม้แดง-ดำ อย่างไรก็ตาม ต้นไม้ WAVL บางต้นไม่ได้มาจากต้นไม้ AVL ในลักษณะนี้ และต้นไม้แดง-ดำบางต้นก็ไม่ได้มาจากต้นไม้ WAVL ในลักษณะนี้เช่นกัน

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

ความแตกต่างที่สำคัญระหว่างต้นไม้ AVL และต้นไม้ WAVL เกิดขึ้นเมื่อโหนดมีลูกสองตัวที่มีลำดับหรือความสูงเท่ากัน ในต้นไม้ AVL หากโหนดxมีลูกสองตัวที่มีความสูงhเท่ากัน ความสูงของxจะต้องเป็นh + 1 อย่างแน่นอน ในทางตรงกันข้าม ในต้นไม้ WAVL หากโหนดxมีลูกสองตัวที่มีลำดับrเท่ากัน ลำดับของxสามารถเป็นr + 1หรือr + 2 ก็ได้ เนื่องจากลำดับไม่เท่ากับความสูงอย่างเคร่งครัดในต้นไม้ WAVL ความยืดหยุ่นที่มากขึ้นในลำดับนี้ยังนำไปสู่ความยืดหยุ่นที่มากขึ้นในโครงสร้างด้วย ต้นไม้ WAVL บางต้นไม่สามารถสร้างเป็นต้นไม้ AVL ได้แม้จะแก้ไขลำดับแล้วก็ตาม เนื่องจากมีโหนดที่มีความสูงของลูกต่างกันมากกว่าหนึ่ง^{[ 2 ]}อย่างไรก็ตาม เราสามารถกล่าวได้ว่าต้นไม้ AVL ทั้งหมดเป็นต้นไม้ WAVL ต้นไม้ AVL เป็นต้นไม้ WAVL ที่ไม่มีโหนดประเภทที่มีลูกทั้งสองที่มีลำดับต่างกัน 2 ^{[ 1 ]}

หากสร้างต้นไม้ WAVL โดยใช้เฉพาะการดำเนินการแทรกเท่านั้น โครงสร้างของต้นไม้ WAVL จะเหมือนกับโครงสร้างของต้นไม้ AVL ที่สร้างขึ้นโดยลำดับการแทรกเดียวกัน และอันดับของต้นไม้ WAVL จะเหมือนกับอันดับของต้นไม้ AVL ที่สอดคล้องกัน เฉพาะการดำเนินการลบเท่านั้นที่ทำให้ต้นไม้ WAVL แตกต่างจากต้นไม้ AVL โดยเฉพาะอย่างยิ่ง หมายความว่าต้นไม้ WAVL ที่สร้างขึ้นโดยการแทรกเท่านั้นจะมีระดับความสูงสูงสุด^{[ 2 ]}${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$

ต้นไม้แดง-ดำคือต้นไม้ค้นหาแบบไบนารีที่สมดุล ซึ่งแต่ละโหนดมีสี (แดงหรือดำ) และมีคุณสมบัติดังต่อไปนี้:

• โหนดภายนอกมีสีดำ
• ถ้าโหนดภายในเป็นสีแดง โหนดลูกทั้งสองของโหนดนั้นจะเป็นสีดำ
• เส้นทางทั้งหมดจากโหนดรากไปยังโหนดภายนอกจะมีจำนวนโหนดสีดำเท่ากัน

ต้นไม้แดง-ดำสามารถนิยามได้เทียบเท่ากันในแง่ของระบบลำดับชั้นที่จัดเก็บไว้ที่โหนด ซึ่งต้องเป็นไปตามข้อกำหนดต่อไปนี้ (แตกต่างจากข้อกำหนดสำหรับลำดับชั้นในต้นไม้ WAVL):

• ลำดับของโหนดภายนอกจะมีค่าเป็น 0 เสมอ และลำดับของโหนดแม่จะมีค่าเป็น 1 เสมอ
• ลำดับของโหนดที่ไม่ใช่โหนดรากจะเท่ากับลำดับของโหนดแม่ หรือลำดับของโหนดแม่ลบด้วย 1
• ไม่มีขอบสองขอบที่อยู่ติดกันบนเส้นทางราก-ใบใดๆ ที่มีผลต่างลำดับเป็น 0

ความเท่าเทียมกันระหว่างคำจำกัดความตามสีและตามลำดับชั้นสามารถมองเห็นได้ในทิศทางหนึ่ง โดยการระบายสีโหนดเป็นสีดำหากโหนดแม่มีลำดับชั้นสูงกว่า และเป็นสีแดงหากโหนดแม่มีลำดับชั้นเท่ากัน ในอีกทิศทางหนึ่ง สามารถแปลงสีเป็นลำดับชั้นได้โดยการกำหนดให้ลำดับชั้นของโหนดสีดำเท่ากับจำนวนโหนดสีดำบนเส้นทางใดๆ ไปยังโหนดภายนอก และโดยการกำหนดให้ลำดับชั้นของโหนดสีแดงเท่ากับโหนดแม่^{[ 8 ]}

ลำดับของโหนดในต้นไม้ WAVL สามารถแปลงเป็นระบบลำดับของโหนดที่สอดคล้องกับข้อกำหนดสำหรับต้นไม้แดง-ดำได้ โดยการหารแต่ละลำดับด้วยสองและปัดเศษขึ้นเป็นจำนวนเต็มที่ใกล้ที่สุด^{[ 9 ]}เนื่องจากการแปลงนี้ สำหรับต้นไม้ WAVL ทุกต้นจะมีต้นไม้แดง-ดำที่ถูกต้องซึ่งมีโครงสร้างเดียวกัน เนื่องจากต้นไม้แดง-ดำมีความสูงสูงสุด ดังนั้นจึงเป็นจริงเช่นเดียวกันสำหรับต้นไม้ WAVL ^{[ 1 ] [ 2 ]}อย่างไรก็ตาม มีต้นไม้แดง-ดำบางต้นที่ไม่สามารถกำหนดฟังก์ชันลำดับต้นไม้ WAVL ที่ถูกต้องได้^{[ 2 ]}${\displaystyle 2\log _{2}n}$

แม้ว่าในแง่ของโครงสร้างต้นไม้ ต้นไม้ WAVL จะเป็นกรณีพิเศษของต้นไม้แดง-ดำ แต่การดำเนินการอัปเดตนั้นแตกต่างกัน การหมุนต้นไม้ที่ใช้ในการดำเนินการอัปเดตต้นไม้ WAVL อาจทำให้เกิดการเปลี่ยนแปลงที่ไม่ได้รับอนุญาตในต้นไม้แดง-ดำ เนื่องจากจะทำให้เกิดการเปลี่ยนสีต้นไม้ย่อยขนาดใหญ่ของต้นไม้แดง-ดำ แทนที่จะเปลี่ยนสีเฉพาะเส้นทางเดียวในต้นไม้^{[ 2 ]}ซึ่งทำให้ต้นไม้ WAVL สามารถทำการหมุนต้นไม้น้อยลงต่อการลบ ในกรณีที่เลวร้ายที่สุด เมื่อเทียบกับต้นไม้แดง-ดำ^{[ 1 ] [ 2 ]}