Saya telah memverifikasi di tiga sumber untuk memasukkan kode avl. Dalam semua kasus untuk menghitung ketinggian,

root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))

Baris di atas diberikan.

Inilah pertanyaan saya, mengapa kita harus mengambil maksimal subpohon kiri dan kanan dan menambahkan satu ke dalamnya? Bagaimana jika kita menambahkan node ke subtree dengan tinggi minimum? Dalam hal ini keduanya akan memiliki tinggi yang sama H bukan H+1.

Kenaikan ketinggian ini harus ditambahkan sebagai,

 elif key < root.key:    
      root.left = self.insertNode(root.left, key)  
      root.height = 1 + self.getHeight(root.left)
 else:    
      root.right = self.insertNode(root.right, key)
      root.height = 1 + self.getHeight(root.right )

Apakah saya benar? Jika ya, mengapa orang-orang ini menambahkan satu setelah mengambil maks?

Silakan gunakan kode lengkap untuk verifikasi di bawah ini. kode diambil dari programiz.com. Juga terverifikasi geek untuk geeks.

def insertNode(self, root, key): 

        if not root: 
            return TreeNode(key) 
        elif key < root.key: 
            root.left = self.insertNode(root.left, key) 
        else: 
            root.right = self.insertNode(root.right, key) 

        root.height = 1 + max(self.getHeight(root.left), 
                        self.getHeight(root.right)) 

        balanceFactor = self.getBalance(root) 

        if balanceFactor > 1:
            if key < root.left.key: 
                return self.rightRotate(root) 
            else:
                root.left = self.leftRotate(root.left) 
                return self.rightRotate(root)

        if balanceFactor < -1:
            if key > root.right.key: 
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right) 
                return self.leftRotate(root)

        return root 
0
Gokulakannan 11 April 2020, 18:10

1 menjawab

Jawaban Terbaik

Misalkan Anda memiliki pohon seperti ini:

       5
      / \
     /   \
    3     7
   /     / \
  2     6   8
             \
              9

Pohon memiliki tinggi 3 (ada 3 cabang antara simpul akar 5 dan simpul daun terdalam 9).

Ketinggian subpohon adalah 1 untuk yang kiri (berakar pada simpul 3) dan 2 untuk yang kanan (berakar pada 7), dan

3 = H(node(5)) = 1 + max(H(node(3)), H(node(7))) = 1 + max(1, 2)

Sekarang misalkan Anda menambahkan simpul dengan kunci 4 ke pohon:

       5
      / \
     /   \
    3     7
   / \   / \
  2   4 6   8
             \
              9

Tinggi pohon yang berakar pada simpul 3 tidak bertambah: H(simpul (3)) masih sama dengan 1.

Jika Anda melakukan penggantian yang diusulkan dalam algoritme, pohon Anda akan keliru mendapatkan ketinggian 2 setelah penyisipan yang dijelaskan: 1 + H(node(3)), alih-alih menjaga ketinggian tetap sama 3.

JIKA kode Anda telah benar-benar 'diverifikasi' oleh situs pemrograman mana pun, lalu lari dari situs itu dan jangan pernah memercayai mereka lagi.

1
CiaPan 13 April 2020, 20:19