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

ในวิทยาการคอมพิวเตอร์ต้นไม้AVL (ตั้งชื่อตามผู้คิดค้นคือAdelson - VelskyและLandis ) คือต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลได้เองในต้นไม้ AVL ความสูงของ ต้นไม้ย่อย ลูก สอง ต้นของโหนดใดๆ จะแตกต่างกันไม่เกินหนึ่ง หากเมื่อใดก็ตามที่แตกต่างกันมากกว่าหนึ่ง จะมีการปรับสมดุลใหม่เพื่อคืนค่าคุณสมบัตินี้ การค้นหา การแทรก และการลบทั้งหมดใช้ เวลา O (log n )ทั้งในกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุด โดยที่ n คือจำนวนโหนดในต้นไม้ก่อนการดำเนินการ การแทรกและการลบอาจต้องมีการปรับสมดุลต้นไม้ ใหม่ โดย การหมุนต้นไม้หนึ่งครั้งหรือมากกว่านั้น${\displaystyle n}$

ต้นไม้ AVL ได้รับการตั้งชื่อตามนักประดิษฐ์ชาวโซเวียต สองคนคือ Georgy Adelson-VelskyและEvgenii Landisซึ่งตีพิมพ์ในบทความปี 1962 ของพวกเขาเรื่อง "อัลกอริทึมสำหรับการจัดระเบียบข้อมูล" ^{[ 2 ]} นับเป็น โครงสร้างข้อมูล ต้นไม้ค้นหาไบนารีแบบปรับสมดุลตัวเองตัวแรกที่ถูกคิดค้นขึ้น^{[ 3 ]}

ต้นไม้ AVL มักถูกเปรียบเทียบกับต้นไม้แดง-ดำเนื่องจากทั้งสองรองรับชุดการดำเนินการเดียวกันและใช้เวลาในการดำเนินการพื้นฐาน สำหรับแอปพลิเคชันที่เน้นการค้นหา ต้นไม้ AVL จะเร็วกว่าต้นไม้แดง-ดำ เนื่องจากมีความสมดุลที่เข้มงวดกว่า^{[ 4 ]}เช่นเดียวกับต้นไม้แดง-ดำ ต้นไม้ AVL มีความสมดุลของความสูง โดยทั่วไปแล้วทั้งสองจะไม่สมดุลของน้ำหนักหรือสมดุลของค่าใดๆ[ ^{5 ] กล่าว}คือ โหนดพี่น้องสามารถมีจำนวนลูกหลานที่แตกต่างกันอย่างมาก ${\displaystyle {\text{O}}(\log n)}$${\displaystyle \mu }$${\displaystyle \mu \leq {\tfrac {1}{2}}}$

ในต้นไม้ไบนารีปัจจัยสมดุลของโหนดXถูกกำหนดให้เป็นผลต่างความสูง

${\displaystyle \mathrm {BF} (X):=\mathrm {Height} (\mathrm {RightSubtree} (X))-\mathrm {Height} (\mathrm {LeftSubtree} (X))}$^{[ 6 ] : 459}

โดยมีโหนดลูกย่อยสอง โหนด เป็นรากที่โหนดX

ต้นไม้ไบนารีจะถูกนิยามว่าเป็นต้นไม้ AVLถ้า

${\displaystyle \mathrm {BF} (X)\in \{-1,0,1\}}$

ใช้ได้กับทุกโหนดXในต้นไม้

โหนดXที่มีเรียกว่า "หนักซ้าย" โหนดที่มีเรียกว่า "หนักขวา" และโหนดที่มีบางครั้งเรียกว่า "สมดุล" ${\displaystyle \mathrm {BF} (X)<0}$${\displaystyle \mathrm {BF} (X)>0}$${\displaystyle \mathrm {BF} (X)=0}$

ปัจจัยสมดุลสามารถอัปเดตได้โดยการทราบปัจจัยสมดุลก่อนหน้าและการเปลี่ยนแปลงความสูง – ไม่จำเป็นต้องทราบความสูงสัมบูรณ์ สำหรับการเก็บข้อมูลสมดุล AVL สองบิตต่อโหนดก็เพียงพอแล้ว^{[ 7 ]}

ความสูง(นับเป็นจำนวนระดับสูงสุด) ของต้นไม้ AVL ที่มีโหนดอยู่ในช่วง: ^{[ 6 ] : 460} ${\displaystyle h}$${\displaystyle n}$

${\displaystyle \log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b}$

อัตราส่วนทองคำ   อยู่ที่ไหนและ นี่เป็นเพราะต้นไม้ AVL ที่มีความสูง ประกอบด้วย โหนดอย่างน้อย โดยที่ คือลำดับฟิโบนาชี่ที่มีค่าเริ่มต้น${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}$${\displaystyle b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.}$${\displaystyle h}$${\displaystyle F_{h+2}-1}$${\displaystyle \{F_{n}\}_{n\in \mathbb {N} }}$${\displaystyle F_{1}=F_{2}=1.}$

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

การค้นหาคีย์เฉพาะในต้นไม้ AVL สามารถทำได้ในลักษณะเดียวกับการค้นหาในต้นไม้ไบนารีแบบสมดุลหรือไม่สมดุลใดๆ[ 8 ^{] : บทที่ 8} เพื่อให้การค้นหามีประสิทธิภาพ จำเป็นต้องใช้ฟังก์ชันเปรียบเทียบซึ่งกำหนดลำดับทั้งหมด (หรืออย่างน้อยก็ลำดับก่อนหน้าทั้งหมด ) บนชุดของคีย์^{[ 9 ] : 23} จำนวนการเปรียบเทียบที่จำเป็นสำหรับการค้นหาที่สำเร็จนั้นถูกจำกัดด้วยความสูงhและสำหรับการค้นหาที่ไม่สำเร็จนั้นใกล้เคียงกับh มาก ดังนั้นทั้งสองจึงอยู่ในO(log n )โดยที่ n คือจำนวนโหนดในต้นไม้^{[ 10 ] : 216}

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

เมื่อพบโหนดในต้นไม้ AVL แล้วสามารถเข้าถึงโหนดถัดไปหรือ โหนด ก่อนหน้า ได้ใน เวลาคงที่โดยเฉลี่ย^{[ 11 ] : 58} ในบางกรณี การสำรวจโหนด "ใกล้เคียง" เหล่านี้ จำเป็นต้องเดินทางผ่านลิงก์มากถึงh ∝ log( n )ลิงก์ (โดยเฉพาะอย่างยิ่งเมื่อนำทางจากใบขวาสุดของซับทรีด้านซ้ายของรากไปยังราก หรือจากรากไปยังใบซ้ายสุดของซับทรีด้านขวาของราก ในต้นไม้ AVL ในรูปที่ 1 การนำทางจากโหนด P ไปยังโหนด Q ที่อยู่ถัดจากด้านขวา ต้องใช้ 3 ขั้นตอน) เนื่องจากมี ลิงก์ n −1ในต้นไม้ใดๆ ต้นทุนโดยเฉลี่ยคือ2×( n −1)/ nหรือประมาณ 2

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

หลังจากแทรกโหนดนี้แล้ว หากต้นไม้เกิดการไม่สมดุล เฉพาะบรรพบุรุษของโหนดที่แทรกใหม่เท่านั้นที่จะไม่สมดุล เนื่องจากมีเพียงโหนดเหล่านั้นเท่านั้นที่มีต้นไม้ย่อยเปลี่ยนแปลง^{[ 12 ]}ดังนั้นจึงจำเป็นต้องตรวจสอบบรรพบุรุษของแต่ละโหนดว่าสอดคล้องกับค่าคงที่ของต้นไม้ AVL หรือไม่ ซึ่งเรียกว่า "การย้อนรอย" โดยทำได้โดยพิจารณาปัจจัยสมดุลของแต่ละโหนด^{[ 6 ] : 458–481 [ 11 ] : 108}

เนื่องจากการแทรกเพียงครั้งเดียวทำให้ความสูงของซับทรี AVL ไม่สามารถเพิ่มขึ้นได้มากกว่าหนึ่ง ดังนั้นปัจจัยสมดุลชั่วคราวของโหนดหลังจากการแทรกจะอยู่ในช่วง[–2, +2]สำหรับแต่ละโหนดที่ตรวจสอบ หากปัจจัยสมดุลชั่วคราวยังคงอยู่ในช่วงตั้งแต่ –1 ถึง +1 ก็จำเป็นต้องอัปเดตปัจจัยสมดุลเท่านั้น ไม่จำเป็นต้องหมุน อย่างไรก็ตาม หากปัจจัยสมดุลชั่วคราวเป็น ±2 ซับทรีที่รากอยู่ที่โหนดนี้จะไม่สมดุล AVL และจำเป็นต้องมีการหมุน^{[ 9 ] : 52} ด้วยการแทรกดังที่โค้ดด้านล่างแสดง การหมุนที่เหมาะสม จะทำให้ ต้นไม้ สมดุลขึ้น อย่างสมบูรณ์แบบทันที

ในรูปที่ 1 เมื่อแทรกโหนดใหม่ Z เป็นโหนดลูกของโหนด X ความสูงของซับทรี Z จะเพิ่มขึ้นจาก 0 เป็น 1

ค่าคงที่ของลูปย้อนกลับสำหรับการแทรก

ความสูงของซับทรีที่รากเป็น Z เพิ่มขึ้น 1 แล้ว และมีรูปร่างแบบ AVL แล้ว

for ( X = parent ( Z ); X != null ; X = parent ( Z )) { // วนลูป (อาจวนไปจนถึงราก)// ต้องอัปเดต BF(X) :ถ้า( Z == right_child ( X )) { // ซับทรีด้านขวาเพิ่มขึ้นถ้า( BF ( X ) > 0 ) { // X มีน้ำหนักไปทางขวามาก// ==> ค่า BF(X) ชั่วคราว == +2// ==> จำเป็นต้องปรับสมดุลใหม่G = parent ( X ); // บันทึก parent ของ X ไว้เมื่อมีการหมุนถ้า( BF ( Z ) < 0 ) // กรณีซ้ายขวา (ดูรูปที่ 3)N = rotate_RightLeft ( X , Z ); // การหมุนสองรอบ: ขวา (Z) แล้วซ้าย (X)มิฉะนั้น// กรณีขวาสุด (ดูรูปที่ 2)N = rotate_Left ( X , Z ); // การหมุนซ้ายครั้งเดียว (X)// หลังจากการหมุน ให้ปรับลิงก์หลัก} อื่น{ถ้า( BF ( X ) < 0 ) {BF ( X ) = 0 ; // การเพิ่มความสูงของ Z ถูกดูดซับที่ Xbreak ; // ออกจากลูป}BF ( X ) = + 1 ;Z = X ; // ความสูง (Z) เพิ่มขึ้น 1ดำเนินการต่อ;}} else { // Z == left_child(X): ซับทรีด้านซ้ายเพิ่มขึ้นถ้า( BF ( X ) < 0 ) { // X มีน้ำหนักไปทางซ้าย// ==> ค่า BF(X) ชั่วคราว == -2// ==> จำเป็นต้องปรับสมดุลใหม่G = parent ( X ); // บันทึก parent ของ X ไว้เมื่อมีการหมุนถ้า( BF ( Z ) > 0 ) // กรณีซ้ายขวาN = rotate_LeftRight ( X , Z ); // การหมุนสองรอบ: ซ้าย (Z) แล้วขวา (X)มิฉะนั้น// กรณีซ้ายสุดN = rotate_Right ( X , Z ); // การหมุนครั้งเดียวไปทางขวา (X)// หลังจากการหมุน ให้ปรับลิงก์หลัก} อื่น{ถ้า( BF ( X ) > 0 ) {BF ( X ) = 0 ; // การเพิ่มความสูงของ Z ถูกดูดซับที่ Xbreak ; // ออกจากลูป}BF ( X ) = -1 ;Z = X ; // ความสูง (Z) เพิ่มขึ้น 1ดำเนินการต่อ;}}// หลังจากการหมุน ให้ปรับลิงก์หลัก:// N คือรากใหม่ของซับทรีที่หมุนแล้ว// ความสูงไม่เปลี่ยนแปลง: ความสูง (N) == ความสูงเดิม (X)parent ( N ) = G ;ถ้า( G != null ) {ถ้า( X == left_child ( G ))left_child ( G ) = N ;อื่นright_child ( G ) = N ;} อื่นtree -> root = N ; // N คือรากใหม่ของต้นไม้ทั้งหมดหยุดพัก;// ไม่มีทางทะลุผ่าน มีแต่การหยุด หรือดำเนินต่อไป}// หากไม่ทำการออกจากลูปด้วยคำสั่ง break ความสูงของต้นไม้ทั้งหมดจะเพิ่มขึ้น 1

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

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

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

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

เวลาที่ต้องการคือO(log n ) สำหรับการค้นหา บวกกับ ระดับการย้อนรอยสูงสุดO(log n ) (โดยเฉลี่ย O(1) ) ระหว่างทางกลับไปยังราก ดังนั้นการดำเนินการจึงสามารถเสร็จสิ้นได้ในเวลาO(log n ) ^{[ 9 ] : 53}

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

เริ่มต้นจากซับทรีนี้ จำเป็นต้องตรวจสอบความสอดคล้องของบรรพบุรุษแต่ละตัวกับค่าคงที่ของต้นไม้ AVL ซึ่งเรียกว่า "การย้อนรอย" (retracing)

เนื่องจากการลบเพียงครั้งเดียวจะทำให้ความสูงของซับทรี AVL ลดลงได้ไม่เกินหนึ่ง ดังนั้นค่าตัวประกอบสมดุลชั่วคราวของโหนดจะอยู่ในช่วงตั้งแต่ -2 ถึง +2 หากค่าตัวประกอบสมดุลยังคงอยู่ในช่วงตั้งแต่ -1 ถึง +1 ก็สามารถปรับให้สอดคล้องกับกฎ AVL ได้ หากค่าตัวประกอบสมดุลกลายเป็น ±2 แสดงว่าซับทรีไม่สมดุลและจำเป็นต้องหมุน (ต่างจากการแทรกที่การหมุนจะทำให้ต้นไม้สมดุลเสมอ หลังจากการลบ อาจมี BF(Z) ≠ 0 (ดูรูปที่ 2 และ 3) ดังนั้นหลังจากการหมุนครั้งเดียวหรือสองครั้งที่เหมาะสม ความสูงของซับทรีที่ปรับสมดุลแล้วจะลดลงหนึ่ง ซึ่งหมายความว่าต้นไม้จะต้องได้รับการปรับสมดุลอีกครั้งในระดับที่สูงขึ้นถัดไป) กรณีต่างๆ ของการหมุนจะอธิบายไว้ในส่วนการปรับสมดุล

ค่าคงที่ของลูปการย้อนรอยสำหรับการลบ

ความสูงของต้นไม้สาขาที่รากเป็น N ลดลง 1 หน่วย ขณะนี้อยู่ในรูปทรง AVL แล้ว

for ( X = parent ( N ); X != null ; X = G ) { // วนลูป (อาจวนไปจนถึงราก)G = parent ( X ); // บันทึก parent ของ X ไว้เมื่อมีการหมุน// BF(X) ยังไม่ได้รับการอัปเดต!ถ้า( N == left_child ( X )) { // ซับทรีด้านซ้ายลดลงถ้า( BF ( X ) > 0 ) { // X มีน้ำหนักไปทางขวามาก// ==> ค่า BF(X) ชั่วคราว == +2// ==> จำเป็นต้องปรับสมดุลใหม่Z = right_child ( X ); // พี่น้องของ N (สูงกว่า 2)b = BF ( Z );ถ้า( b < 0 ) // กรณีซ้ายขวา (ดูรูปที่ 3)N = rotate_RightLeft ( X , Z ); // การหมุนสองรอบ: ขวา (Z) แล้วซ้าย (X)มิฉะนั้น// กรณีขวาสุด (ดูรูปที่ 2)N = rotate_Left ( X , Z ); // การหมุนซ้ายครั้งเดียว (X)// หลังจากการหมุน ให้ปรับลิงก์หลัก} อื่น{ถ้า( BF ( X ) == 0 ) {BF ( X ) = + 1 ; // การลดความสูงของ N ถูกดูดซับที่ Xbreak ; // ออกจากลูป}N = X ;BF ( N ) = 0 ; // ความสูง (N) ลดลง 1ดำเนินการต่อ;}} else { // (N == right_child(X)): ซับทรีด้านขวาลดลงถ้า( BF ( X ) < 0 ) { // X มีน้ำหนักไปทางซ้าย// ==> ค่า BF(X) ชั่วคราว == -2// ==> จำเป็นต้องปรับสมดุลใหม่Z = left_child ( X ); // พี่น้องของ N (สูงกว่า 2)b = BF ( Z );ถ้า( b > 0 ) // กรณีซ้ายขวาN = rotate_LeftRight ( X , Z ); // การหมุนสองรอบ: ซ้าย (Z) แล้วขวา (X)มิฉะนั้น// กรณีซ้ายสุดN = rotate_Right ( X , Z ); // การหมุนครั้งเดียวไปทางขวา (X)// หลังจากการหมุน ให้ปรับลิงก์หลัก} อื่น{ถ้า( BF ( X ) == 0 ) {BF ( X ) = -1 ; // การลดความสูงของ N ถูกดูดซับที่ Xbreak ; // ออกจากลูป}N = X ;BF ( N ) = 0 ; // ความสูง (N) ลดลง 1ดำเนินการต่อ;}}// หลังจากการหมุน ให้ปรับลิงก์หลัก:// N คือรากใหม่ของซับทรีที่หมุนแล้วparent ( N ) = G ;ถ้า( G != null ) {ถ้า( X == left_child ( G ))left_child ( G ) = N ;อื่นright_child ( G ) = N ;} อื่นtree -> root = N ; // N คือรากใหม่ของต้นไม้ทั้งหมดถ้า( b == 0 )break ; // ความสูงไม่เปลี่ยนแปลง: ออกจากลูป// ความสูง (N) ลดลง 1 (== ความสูงเดิม (X) - 1)}// ถ้า (b != 0) ความสูงของต้นไม้ทั้งหมดจะลดลง 1

กระบวนการย้อนกลับจะหยุดลงได้หากค่าตัวประกอบสมดุลกลายเป็น ±1 (ซึ่งก่อนหน้านี้ต้องเป็น 0) หมายความว่าความสูงของซับทรีนั้นยังคงไม่เปลี่ยนแปลง

ถ้าค่าตัวประกอบสมดุลกลายเป็น 0 (ซึ่งต้องเป็น ±1) ความสูงของซับทรีจะลดลงหนึ่งระดับ และจำเป็นต้องทำการย้อนรอยต่อไป

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

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

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

ฟังก์ชันJoinบนต้นไม้ AVL สองต้น_t1 และ t2 และคีย์kจะส่งคืนต้นไม้ที่มีองค์ประกอบทั้งหมดในt1 , t2รวมถึงk ด้วย โดยมี _{เงื่อนไข} ว่า kต้องมากกว่าคีย์ทั้งหมดในt1และน้อยกว่าคีย์ทั้งหมดใน_t2หากต้นไม้ทั้งสองแตกต่างกันที่ความสูงไม่เกินหนึ่ง ฟังก์ชัน Joinจะสร้างโหนดใหม่ที่มีซับทรีด้านซ้ายเป็นt1 _{, รากเป็น}kและซับทรีด้านขวา_{เป็น t2} มิฉะนั้น สมมติว่าt1สูงกว่าt2 มากกว่า _{หนึ่งค่า} (กรณีอื่นเป็นแบบสมมาตร) _{ฟังก์ชัน} Joinจะตามแกนด้านขวาของt1 ไป จนถึงโหนดcซึ่งสมดุลกับ_t2ณ จุดนี้ โหนดใหม่ที่มีลูกด้านซ้ายเป็นc , รากเป็นkและลูกด้านขวา_เป็นt2 จะถูกสร้างขึ้นเพื่อแทนที่ c _โหนดใหม่นี้เป็นไปตามเงื่อนไขคงที่ของ AVL และความสูงของมันมากกว่าc หนึ่ง ค่า การเพิ่มความสูงอาจทำให้ความสูงของบรรพบุรุษเพิ่มขึ้น ซึ่งอาจทำให้ค่าคงที่ AVL ของโหนดเหล่านั้นไม่ถูกต้อง สามารถแก้ไขได้โดยการหมุนสองครั้งหากไม่ถูกต้องที่โหนดแม่ หรือหมุนซ้ายครั้งเดียวหากไม่ถูกต้องที่ระดับสูงกว่าในโครงสร้างต้นไม้ ในทั้งสองกรณีจะคืนค่าความสูงให้กับโหนดบรรพบุรุษถัดไป ดังนั้น ฟังก์ชัน Joinจะต้องใช้การหมุนอย่างมากที่สุดสองครั้ง ค่าใช้จ่ายของฟังก์ชันนี้คือผลต่างของความสูงระหว่างต้นไม้สองต้นที่ป้อนเข้ามา

ฟังก์ชัน JoinRightAVL(T L , k, T R ) (l, k', c) = expose(T L ) if (Height(c) <= Height(T R )+1) T' = Node(c, k, T R ) ถ้า (ความสูงของ T' <= ความสูงของ l + 1) แล้วให้ส่งคืน Node(l, k', T') มิฉะนั้นให้คืนค่า rotateLeft(Node(l, k', rotateRight(T'))) มิฉะนั้น T' = JoinRightAVL(c, k, T R ) T'' = โหนด(l, k', T') ถ้า (ความสูงของ T' <= ความสูงของ l + 1) ให้คืนค่า T'' มิฉะนั้นให้คืนค่าหมุนไปทางซ้ายของ T'' 

ฟังก์ชัน JoinLeftAVL(T L , k, T R ) /* สมมาตรกับ JoinRightAVL */ 

ฟังก์ชัน Join(T L , k, T R ) ถ้า (Height(T L )>Height(T R )+1) ให้คืนค่า JoinRightAVL(T L , k, T R ) ถ้า (Height(T R )>Height(T L )+1) ให้คืนค่า JoinLeftAVL(T L , k, T R ) คืนค่า Node(T L , k, T R ) 

ในการแบ่งต้นไม้ AVL ออกเป็นสองต้นไม้เล็กๆ คือ ต้นไม้ที่มีค่าน้อยกว่าคีย์kและต้นไม้ที่มีค่ามากกว่าคีย์kขั้นแรกให้ลากเส้นทางจากรากโดยการแทรกค่า kเข้าไปใน AVL หลังจากแทรกค่าแล้ว ค่าทั้งหมดที่น้อยกว่าkจะอยู่ทางด้านซ้ายของเส้นทาง และค่าทั้งหมดที่มากกว่าkจะอยู่ทางด้านขวา โดยการใช้Joinต้นไม้ย่อยทั้งหมดทางด้านซ้ายจะถูกรวมเข้าด้วยกันจากล่างขึ้นบนโดยใช้คีย์บนเส้นทางเป็นโหนดกลางจากล่างขึ้นบนเพื่อสร้างต้นไม้ด้านซ้าย ส่วนด้านขวาจะไม่สมมาตร ค่าใช้จ่ายในการแบ่งคือO(log n )ซึ่งเป็นลำดับของความสูงของต้นไม้

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

การรวมกันของต้นไม้ AVL สองต้นt 1 _และ t 2 _ซึ่งแทนเซตAและBคือ AVL tที่แทนA ∪ B

ฟังก์ชัน Union(t 1 , t 2 ): ถ้า t 1 = nil: คืนค่า t 2 ถ้า t 2 = nil: คืนค่า t 1 (t < , b, t > ) = Split(t 2 , t 1 .root) คืนค่า Join(Union(left(t 1 ), t < ), t 1 .root, Union(right(t 1 ), t > )) 

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

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

หากในระหว่างการดำเนินการแก้ไข ความแตกต่างของความสูงระหว่างซับทรีลูกสองอันเปลี่ยนแปลงไป ตราบใดที่ความแตกต่างนั้นน้อยกว่า 2 อาจสะท้อนให้เห็นได้จากการปรับข้อมูลสมดุลที่ซับทรีแม่ ในระหว่างการดำเนินการแทรกและลบ ความแตกต่างของความสูง (ชั่วคราว) 2 อาจเกิดขึ้น ซึ่งหมายความว่าซับทรีแม่จะต้อง "ปรับสมดุลใหม่" เครื่องมือซ่อมแซมที่ให้มานั้นเรียกว่าการหมุนต้นไม้เนื่องจากมันจะย้ายคีย์เฉพาะใน "แนวตั้ง" เท่านั้น ดังนั้นลำดับ (ในแนวนอน) ของคีย์จึงได้รับการรักษาไว้อย่างสมบูรณ์ (ซึ่งจำเป็นสำหรับต้นไม้ค้นหาแบบไบนารี) ^{[ 6 ] : 458–481 [ 11 ] : 33}

ให้ X เป็นโหนดที่มีปัจจัยสมดุล (ชั่วคราว) เท่ากับ −2 หรือ +2 โดยที่ซับทรีด้านซ้ายหรือด้านขวาของโหนดนี้ได้รับการแก้ไขแล้ว ให้ Z เป็นโหนดลูกที่มีซับทรีที่สูงกว่า (ดูรูปที่ 2 และ 3) โปรดสังเกตว่าโหนดลูกทั้งสองมีรูปร่างแบบ AVL ตามสมมติฐานการอุปมาน

ในกรณีของการเพิ่มจำนวน การเพิ่มจำนวนนี้เกิดขึ้นกับลูกคนใดคนหนึ่งของ Z ในลักษณะที่ทำให้ความสูงของ Z เพิ่มขึ้น ในกรณีของการลบออก การลบออกนี้เกิดขึ้นกับพี่น้อง t1 _ของ Z ในลักษณะที่ทำให้ความสูงของ t1 _ซึ่งต่ำอยู่แล้วลดลง (นี่เป็นกรณีเดียวที่ค่าสมดุลของ Z อาจเป็น 0 ได้)

การละเมิดดังกล่าวมีรูปแบบที่เป็นไปได้สี่แบบ:

และการปรับสมดุลจะดำเนินการแตกต่างออกไป:

ดังนั้น สถานการณ์ต่างๆ จึงถูกกำหนดให้เป็นCB โดยที่C (= ทิศทางของลูก) และB (= ความสมดุล) มาจากเซต{ ซ้าย , ขวา } โดยที่ขวา  := − ซ้ายการละเมิดความสมดุลในกรณีC == Bจะได้รับการแก้ไขโดยการหมุนแบบง่ายrotate_(− C )ในขณะที่กรณีC  != B จะได้รับ การแก้ไขโดยการหมุนสองครั้งrotate_CB

ค่าใช้จ่ายในการหมุน ไม่ว่าจะเป็นแบบธรรมดาหรือแบบสองรอบ ก็มีค่าคงที่

รูปที่ 2 แสดงสถานการณ์ Right Right ในครึ่งบน โหนด X มีต้นไม้ลูกสองต้นที่มีปัจจัยสมดุล+2ยิ่งไปกว่านั้น ต้นไม้ลูกภายใน t ₂₃ของ Z (กล่าวคือ ต้นไม้ลูกซ้ายเมื่อ Z เป็นต้นไม้ลูกขวา หรือต้นไม้ลูกขวาเมื่อ Z เป็นต้นไม้ลูกซ้าย) จะไม่สูงกว่าต้นไม้พี่น้อง t ₄ซึ่งอาจเกิดขึ้นได้จากการเพิ่มความสูงของต้นไม้ย่อย t ₄หรือการลดความสูงของต้นไม้ย่อย t ₁ในกรณีหลังนี้ สถานการณ์ที่ t ₂₃มีความสูงเท่ากับ t ₄ ก็ อาจเกิดขึ้น ได้เช่นกัน

ผลลัพธ์ของการหมุนไปทางซ้ายแสดงอยู่ในครึ่งล่างของรูปภาพ จะต้องปรับปรุงลิงก์สามลิงก์ (เส้นขอบหนาในรูปที่ 2) และปัจจัยสมดุลสองปัจจัย

ดังที่แสดงในรูป ก่อนการแทรก ชั้นใบจะอยู่ที่ระดับ h+1 ชั่วคราวอยู่ที่ระดับ h+2 และหลังจากการหมุนจะกลับมาอยู่ที่ระดับ h+1 อีกครั้ง ในกรณีที่มีการลบ ชั้นใบจะอยู่ที่ระดับ h+2 ซึ่งเป็นระดับเดียวกับที่ t ₂₃และ t ₄มีความสูงเท่ากัน มิฉะนั้น ชั้นใบจะอยู่ที่ระดับ h+1 ทำให้ความสูงของต้นไม้ที่หมุนลดลง

ตัวอย่างโค้ดสำหรับการหมุนซ้ายแบบง่ายๆ

node * rotate_Left ( node * X , node * Z ) {// Z มีค่ามากกว่าค่าพี่น้องอยู่ 2t23 = left_child ( Z ); // ลูกภายในของ Zright_child ( X ) = t23 ;ถ้า( t23 != null )parent ( t23 ) = X ;left_child ( Z ) = X ;parent ( X ) = Z ;// กรณีที่ 1, BF(Z) == 0,// เกิดขึ้นเฉพาะกับการลบ ไม่ใช่การแทรก:ถ้า( BF ( Z ) == 0 ) { // t23 มีความสูงเท่ากับ t4BF ( X ) = + 1 ; // t23 ตอนนี้สูงขึ้นBF ( Z ) = – 1 ; // t4 ตอนนี้ต่ำกว่า X} อื่น{ // กรณีที่ 2 เกิดขึ้นเมื่อมีการแทรกหรือลบข้อมูล:BF ( X ) = 0 ;BF ( Z ) = 0 ;}return Z ; // คืนค่ารากใหม่ของซับทรีที่หมุนแล้ว}

รูปที่ 3 แสดงสถานการณ์ซ้ายขวา ในส่วนบนสุด โหนด X มีต้นไม้ลูกสองต้นที่มีปัจจัยสมดุล+2แต่ต่างจากรูปที่ 2 ตรงที่ต้นไม้ลูกภายใน Y ของ Z สูงกว่าต้นไม้พี่น้อง t4 _สิ่งนี้อาจเกิดขึ้นได้จากการแทรก Y เอง หรือการเพิ่มความสูงของต้นไม้ย่อย t2 _หรือ t3 ₍ซึ่งส่งผลให้มีความสูงต่างกัน) หรือจากการลดความสูงของต้นไม้ย่อย t1 _ในกรณีหลังนี้ อาจเกิดขึ้นได้เช่นกันว่า t2 _และ t3 _มีความสูงเท่ากัน

ผลลัพธ์ของการหมุนครั้งแรกทางขวาแสดงอยู่ในส่วนกลางของรูป (เมื่อพิจารณาจากปัจจัยสมดุล การหมุนนี้ไม่เหมือนกับการหมุนเดี่ยวของ AVL อื่นๆ เนื่องจากความแตกต่างของความสูงระหว่าง Y และ t ₄มีเพียง 1 เท่านั้น) ผลลัพธ์ของการหมุนครั้งสุดท้ายทางซ้ายแสดงอยู่ในส่วนล่างของรูป ต้องมีการปรับปรุงลิงก์ห้าลิงก์ (ขอบหนาในรูปที่ 3) และปัจจัยสมดุลสามตัว

ดังที่แสดงในภาพ ก่อนการแทรก ชั้นใบจะอยู่ที่ระดับ h+1 ชั่วคราวอยู่ที่ระดับ h+2 และหลังจากการหมุนสองรอบจะกลับมาอยู่ที่ระดับ h+1 อีกครั้ง ในกรณีของการลบ ชั้นใบจะอยู่ที่ระดับ h+2 และหลังจากการหมุนสองรอบจะอยู่ที่ระดับ h+1 ดังนั้นความสูงของต้นไม้ที่หมุนแล้วจึงลดลง

ตัวอย่างโค้ดสำหรับการหมุนสองทิศทางจากขวาไปซ้าย

node * rotate_RightLeft ( node * X , node * Z ) {// Z มีค่ามากกว่าค่าพี่น้องอยู่ 2Y = left_child ( Z ); // ลูกภายในของ Z// Y สูงกว่าพี่น้อง 1t3 = right_child ( Y );left_child ( Z ) = t3 ;ถ้า( t3 != null )parent ( t3 ) = Z ;right_child ( Y ) = Z ;parent ( Z ) = Y ;t2 = left_child ( Y );right_child ( X ) = t2 ;ถ้า( t2 != null )parent ( t2 ) = X ;left_child ( Y ) = X ;parent ( X ) = Y ;// กรณีที่ 1, BF(Y) == 0ถ้า( BF ( Y ) == 0 ) {BF ( X ) = 0 ;BF ( Z ) = 0 ;} else if ( BF ( Y ) > 0 ) {// t3 สูงกว่าBF ( X ) = – 1 ; // t1 ตอนนี้สูงขึ้นBF ( Z ) = 0 ;} อื่น{// t2 สูงกว่าBF ( X ) = 0 ;BF ( Z ) = + 1 ; // t4 ตอนนี้สูงขึ้น}BF ( Y ) = 0 ;return Y ; // คืนค่ารากใหม่ของซับทรีที่หมุนแล้ว}

ทั้งต้นไม้ AVL และต้นไม้แดง-ดำ (RB) เป็นต้นไม้ค้นหาไบนารีแบบปรับสมดุลตัวเอง และมีความสัมพันธ์กันทางคณิตศาสตร์ อันที่จริง ต้นไม้ AVL ทุกต้นสามารถระบายสีเป็นแดง-ดำได้^{[ 14 ]}แต่มีต้นไม้ RB บางต้นที่ไม่สมดุลแบบ AVL การหมุนมีบทบาทสำคัญในการรักษาสภาพคงที่ของต้นไม้ AVL (หรือ RB) ในกรณีที่เลวร้ายที่สุด แม้ไม่มีการหมุน การแทรกหรือการลบ AVL หรือ RB ต้องใช้ การตรวจสอบ O(log n )และ/หรือการอัปเดตปัจจัยสมดุล AVL (หรือสี RB) การแทรกและการลบ RB และการแทรก AVL ต้องใช้การหมุนแบบเรียกซ้ำหาง ตั้งแต่ศูนย์ถึงสามครั้ง และทำงานในเวลาเฉลี่ยO(1) ^{[ 15 ] : หน้า 165, 158 [ 16 ]}ดังนั้นจึงคงที่เท่ากันโดยเฉลี่ย การลบ AVL ที่ต้องใช้ การหมุน O(log n )ในกรณีที่เลวร้ายที่สุดก็ ใช้ เวลาเฉลี่ยO(1) เช่นกัน โครงสร้างข้อมูลแบบ RB tree จำเป็นต้องจัดเก็บข้อมูลหนึ่งบิต (สี) ในแต่ละโหนด ในขณะที่โครงสร้างข้อมูลแบบ AVL tree ส่วนใหญ่ใช้สองบิตสำหรับค่าสมดุล แม้ว่าเมื่อจัดเก็บไว้ที่โหนดลูกแล้ว บิตเดียวที่มีความหมายว่า "ต่ำกว่าโหนดพี่น้อง" ก็เพียงพอแล้ว ความแตกต่างที่สำคัญกว่าระหว่างโครงสร้างข้อมูลทั้งสองคือขีดจำกัดความสูงของมัน

สำหรับต้นไม้ที่มีขนาดn ≥ 1

• ความสูงของต้นไม้ AVL นั้นสูงสุดไม่เกิน

  ${\displaystyle {\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}}$

โดยที่  อัตราส่วนทองคำและ​  ${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}$${\displaystyle c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440,}$   ${\displaystyle b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,}$${\displaystyle d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065}$

• ความสูงของต้นไม้ RB นั้นสูงสุดไม่เกิน

  ${\displaystyle {\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}}$ [ ^{17 ]​}

ต้นไม้ AVL มีความสมดุลที่เข้มงวดกว่าต้นไม้ RB โดยมี ความสัมพันธ์ เชิงเส้นกำกับ AVL/RB ≈0.720 ของความสูงสูงสุด สำหรับการแทรกและการลบ Ben Pfaff แสดงให้เห็นในการวัด 79 ครั้งว่ามีความสัมพันธ์ของ AVL/RB ระหว่าง 0.677 และ 1.077 โดยมีค่ามัธยฐาน ≈0.947 และค่าเฉลี่ยเรขาคณิต ≈0.910 ^{[ 4 ]}

• ต้นไม้ WAVL
• ต้นไม้ที่สมดุลน้ำหนัก
• ต้นไม้แผ่กว้าง
• ต้นไม้แพะรับบาป
• บี-ทรี
• ที-ทรี
• รายการโครงสร้างข้อมูล

• โดนัลด์ คนูธ . ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์เล่ม 3: การเรียงลำดับและการค้นหาฉบับพิมพ์ครั้งที่ 3. แอดดิสัน-เวสลีย์, 1997. ISBN 0-201-89685-0หน้า 458–475 ของหัวข้อ 6.2.3: ต้นไม้สมดุล
• Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), "ต้นไม้สมดุลอันดับ" (PDF) , ACM Transactions on Algorithms , 11 (4): บทความ 30, 26, doi : 10.1145/2689412 , MR  3361215 , S2CID  1407290.

ในวิกิบุ๊คเรื่องการนำอัลกอริทึมไปใช้ มีหน้าหนึ่งที่กล่าวถึงหัวข้อ: ต้นไม้ AVL

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับต้นไม้AVL

•  บทความนี้ได้นำเนื้อหาที่เป็นสาธารณสมบัติจากPaul E. Black มา ใช้"AVL Tree" พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูลNIST