Struktur Data Pohon

Struktur Data Pohon

Dalam tutorial ini, Anda akan belajar tentang struktur data pohon. Selain itu, Anda akan belajar tentang berbagai jenis pohon dan terminologi yang digunakan dalam pohon.

Pohon adalah struktur data hierarki nonlinier yang terdiri dari node yang dihubungkan oleh tepi.

pohon dalam struktur data
Pohon

Mengapa Struktur Data Pohon?

Struktur data lainnya seperti array, linked list, stack, dan queue adalah struktur data linier yang menyimpan data secara berurutan. Untuk melakukan operasi apa pun dalam struktur data linier, kompleksitas waktu meningkat dengan bertambahnya ukuran data. Tapi, itu tidak bisa diterima di dunia komputasi saat ini.

Struktur data pohon yang berbeda memungkinkan akses yang lebih cepat dan mudah ke data karena merupakan struktur data non-linier.


Terminologi Pohon

Node

Node adalah entitas yang berisi kunci atau nilai dan penunjuk ke simpul anaknya.

Node terakhir dari setiap jalur dipanggil simpul daun atau simpul eksternal yang tidak berisi link / pointer ke node anak.

Simpul yang memiliki setidaknya simpul anak disebut simpul internal.

Tepi

Ini adalah penghubung antara dua node.

Titik dan tepi pohon
Titik dan tepi pohon

Akar

Ini adalah simpul paling atas dari sebuah pohon.

Ketinggian sebuah Node

Tinggi node adalah jumlah tepi dari node ke daun terdalam (mis. Jalur terpanjang dari node ke node daun).

Kedalaman Node

Kedalaman node adalah jumlah edge dari root ke node.

Ketinggian Pohon

Ketinggian Pohon adalah tinggi dari simpul akar atau kedalaman dari simpul yang paling dalam.

Tinggi dan kedalaman setiap simpul di pohon
Tinggi dan kedalaman setiap simpul di pohon

Derajat sebuah Node

Derajat sebuah node adalah jumlah total cabang dari node tersebut.

Hutan

Kumpulan pohon yang terputus-putus disebut hutan.

Hutan dalam struktur data
Menciptakan hutan dari pohon

Anda dapat membuat hutan dengan memotong akar pohon.


Jenis Pohon

  1. Pohon Biner
  2. Pohon Pencarian Biner
  3. Pohon AVL
  4. B-Tree

Penjelajah Pohon

Untuk melakukan operasi apa pun di pohon, Anda harus menjangkau node tertentu. Algoritme penjelajahan pohon membantu dalam mengunjungi simpul yang diperlukan di pohon.

Untuk mempelajari lebih lanjut, silakan kunjungi traversal pohon.


Aplikasi Pohon

  • Binary Search Trees (BSTs) digunakan untuk memeriksa dengan cepat apakah sebuah elemen ada dalam satu set atau tidak.
  • Heap adalah sejenis pohon yang digunakan untuk jenis heap.
  • Versi modifikasi dari pohon yang disebut Tries digunakan di router modern untuk menyimpan informasi perutean.
  • Database paling populer menggunakan B-Trees dan T-Trees, yang merupakan varian dari struktur pohon yang kita pelajari di atas untuk menyimpan datanya
  • Penyusun menggunakan pohon sintaks untuk memvalidasi sintaks setiap program yang Anda tulis.