Üç düğümlü yeniden yapılanma AVL ağaçları nedir?

Question

Ben biraz googled var, ama çok bulunamadı ve nereden başlayacağından emin değilim.

 2 
    /\ 
    1 3 

Bir düğüm silmek istediğiniz ve sonra AVL özelliği geri yüklemek zorunda:

basit AVL ağaç olduğunu varsayalım. Bir değer silindikten sonra ne kadar tri-node yeniden yapılandırmanın yapıldığına işaret edildiğinde, ne anlama gelir?

Answer 1

Bir AVL ağacı güncelleştirilirse, bazı durumlarda, bazı durumlarda, ağacın değişmezini korumak için farklı yeniden dengeleme işlemleri gerçekleştirilmelidir, yani bir arama ağacı ve dengelenmelidir (logaritmik olarak sınırlandırılmış bir yüksekliğe sahip olmak). düğüm sayısı). Hangi yeniden dengeleme işleminin gerekli olduğuna karar vermek için en fazla üç düğüm dikkate alınmalıdır. Döndürme işlemleri bu Wikipedia article'da açıklanmıştır. Sorunuzda öne sürdüğünüz örnek, böyle bir operasyonun gerekliliğine neden olacak kadar küçük olabilir.