Cara Menentukan apakah Pohon Biner Seimbang di Jawa

1. Ikhtisar

Pohon adalah salah satu struktur data terpenting dalam ilmu komputer. Kami biasanya tertarik pada pohon yang seimbang, karena sifatnya yang berharga . Strukturnya memungkinkan melakukan operasi seperti kueri, penyisipan, penghapusan dalam waktu logaritmik.

Dalam tutorial ini, kita akan belajar bagaimana menentukan apakah pohon biner seimbang.

2. Definisi

Pertama, mari perkenalkan beberapa definisi untuk memastikan kita berada di halaman yang sama:

  • Pohon biner - sejenis pohon di mana setiap node memiliki nol, satu atau dua anak
  • Tinggi pohon - jarak maksimum dari akar ke daun (sama dengan kedalaman daun terdalam)
  • Pohon yang seimbang - sejenis pohon di mana untuk setiap subpohon jarak maksimum dari akar ke daun mana pun paling besar satu dari jarak minimum dari akar ke daun mana pun.

Kita dapat menemukan contoh pohon biner yang seimbang di bawah ini. Tiga tepi berwarna hijau adalah visualisasi sederhana tentang cara menentukan ketinggian, sedangkan angka menunjukkan level.

3. Objek Domain

Jadi, mari kita mulai dengan kelas untuk pohon kita:

public class Tree { private int value; private Tree left; private Tree right; public Tree(int value, Tree left, Tree right) { this.value = value; this.left = left; this.right = right; } } 

Demi kesederhanaan, katakanlah setiap node memiliki nilai integer . Perhatikan, jika pohon kiri dan kanan bernilai nol, berarti simpul kita adalah daun .

Sebelum kita memperkenalkan metode utama kita, mari kita lihat apa yang seharusnya dikembalikan:

private class Result { private boolean isBalanced; private int height; private Result(boolean isBalanced, int height) { this.isBalanced = isBalanced; this.height = height; } }

Jadi untuk setiap panggilan, kami akan memiliki informasi tentang ketinggian dan keseimbangan.

4. Algoritma

Memiliki definisi pohon yang seimbang, kita dapat menghasilkan algoritme. Yang perlu kita lakukan adalah memeriksa properti yang diinginkan untuk setiap node . Ini dapat dicapai dengan mudah dengan traversal pencarian kedalaman-pertama rekursif.

Sekarang, metode rekursif kami akan dipanggil untuk setiap node. Selain itu, itu akan melacak kedalaman saat ini. Setiap panggilan akan mengembalikan informasi tentang ketinggian dan keseimbangan.

Sekarang, mari kita lihat metode depth-first kami:

private Result isBalancedRecursive(Tree tree, int depth) { if (tree == null) { return new Result(true, -1); } Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1); Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1); boolean isBalanced = Math.abs(leftSubtreeResult.height - rightSubtreeResult.height) <= 1; boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1; return new Result(isBalanced && subtreesAreBalanced, height); }

Pertama, kita perlu mempertimbangkan kasus jika node kita null : kita akan mengembalikan true (yang berarti pohonnya seimbang) dan -1 sebagai tingginya.

Kemudian, kami membuat dua panggilan rekursif untuk subpohon kiri dan kanan, menjaga kedalaman tetap mutakhir .

Pada titik ini, kami telah melakukan kalkulasi untuk anak dari node saat ini. Sekarang, kami memiliki semua data yang diperlukan untuk memeriksa saldo:

  • yang isBalanced cek variabel ketinggian untuk anak-anak, dan
  • substreesAreBalanced menunjukkan jika subpohon sama-sama seimbang

Akhirnya, kami dapat mengembalikan informasi tentang keseimbangan dan ketinggian. Mungkin ada baiknya juga untuk menyederhanakan panggilan rekursif pertama dengan metode fasad:

public boolean isBalanced(Tree tree) { return isBalancedRecursive(tree, -1).isBalanced; }

5. Ringkasan

Pada artikel ini, kami telah membahas cara menentukan apakah pohon biner seimbang. Kami telah menjelaskan pendekatan pencarian mendalam-pertama.

Seperti biasa, kode sumber dengan pengujian tersedia di GitHub.