Apa perbedaan antara kedalaman dan tinggi pohon?

Ini adalah pertanyaan sederhana dari teori algoritma.
Perbedaan di antara mereka adalah bahwa dalam satu kasus Anda menghitung jumlah node dan jumlah tepi lainnya pada jalur terpendek antara root dan simpul beton.
Yang mana?

Saya belajar bahwa kedalaman dan tinggi adalah properti sebuah simpul :

• The mendalam dari sebuah node adalah jumlah tepi dari node ke pohon simpul akar.
  Node root akan memiliki kedalaman 0.

• The ketinggian dari sebuah node adalah jumlah sisi pada jalan terpanjang dari node ke daun.
  Node daun akan memiliki tinggi 0.

Properti pohon :

• The tinggi pohon akan ketinggian simpul akar,
  atau ekuivalen, kedalaman simpul yang paling dalam.

• The diameter (atau lebar ) dari pohon adalah jumlah node pada jalur terpanjang antara dua node daun. Pohon di bawah ini memiliki diameter 6 node.

tinggi dan kedalaman pohon sama ...

tetapi ketinggian dan kedalaman suatu simpul tidak sama karena ...

tingginya dihitung dengan melintasi dari simpul yang diberikan ke daun yang paling dalam.

kedalaman dihitung dari traversal dari root ke node yang diberikan .....

Menurut Cormen et al. Pengantar Algoritma (Lampiran B.5.3), kedalaman sebuah simpul X di pohon T didefinisikan sebagai panjang jalur sederhana (jumlah tepi) dari simpul akar T ke X. Ketinggian simpul Y adalah jumlah tepi pada jalur sederhana ke bawah terpanjang dari Y ke daun. Ketinggian pohon didefinisikan sebagai ketinggian simpul akarnya.

Perhatikan bahwa jalur sederhana adalah jalur tanpa simpul berulang.

Ketinggian pohon sama dengan kedalaman maksimal pohon . Kedalaman suatu simpul dan ketinggian suatu simpul tidak harus sama. Lihat Gambar B.6 dari Edisi 3 Cormen et al. untuk ilustrasi konsep-konsep ini.

Saya kadang-kadang melihat masalah meminta seseorang untuk menghitung simpul (simpul) bukan tepi, jadi minta klarifikasi jika Anda tidak yakin Anda harus menghitung simpul atau tepi selama ujian atau wawancara kerja.

Jawaban Sederhana:
Kedalaman:
1. Pohon : Jumlah tepi / busur dari simpul akar ke simpul daun pohon disebut sebagai Kedalaman Pohon.
2. Node : Jumlah tepi / busur dari simpul akar ke simpul yang disebut sebagai Kedalaman simpul itu.

Cara lain untuk memahami konsep tersebut adalah sebagai berikut: Kedalaman: Gambar garis horizontal pada posisi root dan perlakukan garis ini sebagai ground. Jadi kedalaman root adalah 0, dan semua anak-anaknya tumbuh ke bawah sehingga setiap level node memiliki kedalaman saat ini + 1.

Tinggi: Garis horizontal yang sama tetapi kali ini posisi tanah adalah simpul eksternal, yang merupakan daun pohon dan dihitung ke atas.

Saya ingin membuat posting ini karena saya seorang mahasiswa CS sarjana dan semakin banyak kami menggunakan OpenDSA dan buku teks sumber terbuka lainnya. Sepertinya dari jawaban berperingkat teratas bahwa cara tinggi dan kedalaman yang diajarkan telah berubah dari satu generasi ke generasi berikutnya, dan saya memposting ini sehingga semua orang sadar bahwa perbedaan ini sekarang ada dan mudah-mudahan tidak akan menyebabkan bug dalam program! Terima kasih.

Dari buku OpenDSA Data Structures & Algos :

Jika n ₁ , n ₂ , ..., n _k adalah urutan node di pohon sedemikian rupa sehingga n _i adalah induk dari n _i +1 untuk 1 <= i <k, maka urutan ini disebut jalur dari n ₁ hingga n _k . Panjang jalan adalah k − 1. Jika ada jalur dari simpul R ke simpul M, maka R adalah leluhur M, dan M adalah turunan dari R. Jadi, semua simpul di pohon adalah keturunan dari akar pohon, sedangkan akar adalah leluhur dari semua node. Kedalaman simpul M di pohon adalah panjang jalur dari akar pohon ke M. Ketinggian pohon adalah satu lebih dari kedalaman simpul terdalam di pohon.Semua node kedalaman d berada di level d di pohon. Root adalah satu-satunya simpul di level 0, dan kedalamannya adalah 0.

Gambar 7.2.1: Pohon biner. Node A adalah root. Node B dan C adalah anak-anak A. Node B dan D bersama-sama membentuk subtree. Node B memiliki dua anak: anak kirinya adalah pohon kosong dan anak kanannya adalah D. Node A, C, dan E adalah leluhur dari G. Node D, E, dan F membentuk tingkat 2 dari pohon; simpul A berada di level 0. Ujung-ujungnya dari A ke C ke E ke G membentuk lintasan panjang 3. Node D, G, H, dan I adalah daun. Node A, B, C, E, dan F adalah node internal. Kedalaman I adalah 3. Tinggi pohon ini adalah 4.