İkili ağaç dengeli yapısal bir durum mudur?

Kendi başına ikili ağaç mutlaka dengeli bir yapıya sahip değildir. Dengeli ikili ağaç, her düğüm için sol ve sağ alt ağaçların yüksekliklerinin en fazla 1 fark ettiği ağaçtır. Bu özellik, etkili erişim, ekleme ve silme işlemlerini sağlar.

Eğer ikili ağaç dengeli değilse, en kötü durumda bağlı listeye benzeyen bir yapıya dönüşebilir ve bu da işlemlerin performansını düşürür.

Go dilinde denge kontrolü örneği (basitleştirilmiş):

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if abs(leftHeight - rightHeight) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftHeight := height(node.Left)
    rightHeight := height(node.Right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Dolayısıyla, ikili ağaç yapısı ve kurallarına bağlı olarak dengeli veya dengesiz olabilir.