Daraxtni akslantirish (Invert Binary Tree)

Binar daraxt berilgan. Uni ko'zguda aks ettirgandek — chapdan o'ngga — o'zgartiring.

Kirish:
        [4]
       /   \
     [2]   [7]
    / \   / \
  [1][3] [6][9]

Chiqish:
        [4]
       /   \
     [7]   [2]
    / \   / \
  [9][6] [3][1]

Har tugun uchun chap va o'ng bolalar o'rin almashadi. Bu amal rekursiv ravishda butun daraxtga tatbiq qilinadi.

Asosiy g'oya

Ko'zguda aks ettirilgan daraxtda: - Har tugunning chap va o'ng bolalari almashgan. - Bu amal ildizdan barglargacha barcha tugunlarga qo'llaniladi.

Rekursiv fikrlash: agar chap va o'ng kenja daraxtlarni akslantira olsak, keyin ularni almashtirish yetarli.

FUNCTION INVERT(node)
    IF node = NULL
        RETURN NULL

    // Rekursiv ravishda kenja daraxtlarni akslantir
    INVERT(node.left)
    INVERT(node.right)

    // Chap va o'ng bolalarni almashtir
    temp = node.left
    node.left = node.right
    node.right = temp

    RETURN node

Bu postorder: avval kenja daraxtlar akslantiriladi, so'ng joriy tugunning bolalari almashadi.

Preorder ham ishlaydi — avval almashtir, keyin rekursiya:

FUNCTION INVERT_PREORDER(node)
    IF node = NULL
        RETURN NULL

    // Avval chap va o'ng almashtir
    temp = node.left
    node.left = node.right
    node.right = temp

    // Keyin kenja daraxtlarni akslantir
    INVERT_PREORDER(node.left)
    INVERT_PREORDER(node.right)

    RETURN node

Ikkalasi ham to'g'ri. Postorder yoki preorder — natija bir xil. Inorder esa mos emas: chap rekursiyadan keyin almashtirish noto'g'ri natija beradi.

Bosqichma-bosqich dry run

        [4]
       /   \
     [2]   [7]
    / \   / \
  [1][3] [6][9]

Rekursiv chaqiruvlar:

INVERT(4):
  INVERT(2):
    INVERT(1):
      INVERT(NULL) = NULL
      INVERT(NULL) = NULL
      almashtir: 1'ning left=NULL, right=NULL → o'zgarish yo'q
      return 1
    INVERT(3):
      INVERT(NULL) = NULL
      INVERT(NULL) = NULL
      return 3
    almashtir: 2'ning left=3, right=1
    return 2

  INVERT(7):
    INVERT(6):
      return 6
    INVERT(9):
      return 9
    almashtir: 7'ning left=9, right=6
    return 7

  almashtir: 4'ning left=7, right=2
  return 4

Natija:
        [4]
       /   \
     [7]   [2]
    / \   / \
  [9][6] [3][1]

Iterativ yondashuv: BFS

Rekursiya o'rniga navbat (queue) bilan daraxtni aylanib, har tugunning bolalarini almashtiramiz.

FUNCTION INVERT_BFS(root)
    IF root = NULL
        RETURN NULL

    queue = [root]

    WHILE queue bo'sh emas
        node = queue dan DEQUEUE

        // Chap va o'ng almashtir
        temp = node.left
        node.left = node.right
        node.right = temp

        IF node.left ≠ NULL
            queue ga node.left ENQUEUE
        IF node.right ≠ NULL
            queue ga node.right ENQUEUE

    RETURN root

BFS bilan dry run:

queue: [4]

DEQUEUE 4: left=2, right=7 → almashtir → left=7, right=2
  queue: [7, 2]

DEQUEUE 7: left=6, right=9 → almashtir → left=9, right=6
  queue: [2, 9, 6]

DEQUEUE 2: left=1, right=3 → almashtir → left=3, right=1
  queue: [9, 6, 3, 1]

DEQUEUE 9, 6, 3, 1: bolasi yo'q → almashtirish ta'siz
  queue: []

Natija to'g'ri.

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira	Eslatma
Rekursiv DFS	O(n)	O(h)	Call stack
Iterativ BFS	O(n)	O(w)	Navbat hajmi

n — tugunlar soni, h — barandlik, w — eng keng qavat.

Barcha n tugun bir marta ko'riladi — O(n) vaqt. Rekursiv yondashuv call stack uchun O(h) xotira ishlatadi. BFS esa navbatda ko'pi bilan bir qavat — O(w) xotira.

Edge case'lar

Bo'sh daraxt. root = NULL → return NULL. Hech narsa qilmasa ham bo'ladi, lekin NULL bilan ishlash oldini olinishi kerak.

Bitta tugunli daraxt. Faqat ildiz — chap va o'ng NULL. Almashtirish o'zgarish keltirmaydi. return root — to'g'ri.

Faqat chap shox. root.right = NULL. Almashtirish: left = NULL, right = (avvalgi chap). Rekursiya faqat o'ng shoxga tushadi.

Allaqachon akslangan. Funksiyani ikki marta chaqirish — asl daraxtni qaytaradi. INVERT(INVERT(root)) == root.

Note

Almashtirish jarayonida vaqtinchalik o'zgaruvchi temp ishlatilishi kerak. node.left = node.right; node.right = node.left deb yozilsa, ikkinchi satrda node.left allaqachon o'ngga almashgan bo'ladi — xato.

Kengaytirilgan variantlar

Daraxtning ko'zgudagi nusxasi yaratish. Asl daraxtni o'zgartirmasdan yangi akslantirилган daraxt yaratish:

FUNCTION INVERT_COPY(node)
    IF node = NULL
        RETURN NULL

    new_node = yangi NODE(node.value)
    new_node.left  = INVERT_COPY(node.right)   // o'ngdan chap nusxa
    new_node.right = INVERT_COPY(node.left)    // chapdan o'ng nusxa

    RETURN new_node

n-ary daraxtni akslantirish. Har tugunning bolalari ro'yxati teskari tartibga solinadi:

FUNCTION INVERT_NARY(node)
    IF node = NULL
        RETURN NULL

    node.children ni teskari tartibga sol
    FOR har bir child node.children ichida
        INVERT_NARY(child)

    RETURN node

Xulosa

Daraxtni akslantirish — rekursiyaning eng toza namunalaridan biri. Har tugun uchun chap va o'ng bolalarni almashtirish va bir xil amalni kenja daraxtlarga rekursiv tatbiq qilish yetarli.

Preorder (avval almashtir) yoki postorder (avval rekursiya) — ikkalasi ham to'g'ri. Bu ikkisining tengligini tushunish rekursiv fikrlashni mustahkamlaydi.

Iterativ BFS — rekursiyani tushunish qiyin bo'lganda yoki call stack cheklangan bo'lganda muqobil.