27 / 69
Balanced Binary Tree
Balanslangan ikkilik daraxt
Balanslangan ikkilik daraxt (Balanced Binary Tree yoki height-balanced binary tree) — har bir tugun uchun uning chap va o'ng quyi daraxtlari balandliklari o'rtasidagi farq ko'pi bilan 1 ga teng bo'lgan ikkilik daraxtdir.
Daraxt yoki tugun balandligi haqida batafsil ma'lumot olish uchun Daraxt ma'lumotlar tuzilmasi darsiga qarang.
Ikkilik daraxt balanslangan bo'lishi uchun quyidagi shartlar qanoatlantirilishi lozim:
- Ixtiyoriy tugun uchun chap va o'ng quyi daraxtlar balandliklari farqi (balans omili) 1 dan oshmasligi kerak.
- Chap quyi daraxt balanslangan bo'lishi kerak.
- O'ng quyi daraxt balanslangan bo'lishi kerak.
Balanslangan ikkilik daraxt namunasi (har bir darajadagi chuqurlik bilan)
Balanslanmagan ikkilik daraxt namunasi (har bir darajadagi chuqurlik bilan)
Dasturiy namunalar: Go, Python, Java, C va C++
Quyidagi dastur berilgan ikkilik daraxtning balandlik bo'yicha balanslanganligini tekshiradi.
// Go tilida daraxtning balanslangan ikkilik daraxt (Balanced Binary Tree) ekanligini tekshirish
package main
import "fmt"
type Node struct {
data int
left *Node
right *Node
}
func newNode(data int) *Node {
return &Node{data: data}
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// Balanslanganlikni tekshirish va balandlikni hisoblash
func isHeightBalanced(root *Node, height *int) bool {
var leftHeight, rightHeight int
if root == nil {
*height = 0
return true
}
l := isHeightBalanced(root.left, &leftHeight)
r := isHeightBalanced(root.right, &rightHeight)
*height = max(leftHeight, rightHeight) + 1
if abs(leftHeight-rightHeight) <= 1 {
return l && r
}
return false
}
func main() {
var height int
root := newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
if isHeightBalanced(root, &height) {
fmt.Println("Daraxt balanslangan (The tree is balanced)")
} else {
fmt.Println("Daraxt balanslanmagan (The tree is not balanced)")
}
}