C++ Binary Search Tree Standard Library

5 min read Jul 01, 2024

C++ Binary Search Tree Standard Library

C++ tidak memiliki library standar khusus untuk Binary Search Tree (BST). Namun, Anda dapat menggunakan struktur data dasar seperti std::set dan std::map yang secara internal menggunakan BST untuk mencapai efisiensi dalam operasi pencarian, penyisipan, dan penghapusan.

std::set

std::set adalah container yang menyimpan data yang terurut dalam bentuk BST. Berikut adalah beberapa ciri dari std::set:

Terurut: Elemen-elemen dalam std::set diurutkan berdasarkan operator pembanding yang Anda tentukan. Jika tidak ditentukan, operator kurang dari (<) akan digunakan secara default.
Unik: std::set tidak mengizinkan duplikat elemen.
Efisiensi: Operasi pencarian, penyisipan, dan penghapusan pada std::set memiliki kompleksitas waktu logaritmik (O(log n)).

Berikut adalah contoh penggunaan std::set:

#include 
#include 

int main() {
  std::set mySet;

  // Menambahkan elemen ke set
  mySet.insert(5);
  mySet.insert(10);
  mySet.insert(2);

  // Mencari elemen dalam set
  if (mySet.find(5) != mySet.end()) {
    std::cout << "Elemen 5 ditemukan" << std::endl;
  }

  // Menghapus elemen dari set
  mySet.erase(10);

  // Mencetak semua elemen dalam set
  for (int element : mySet) {
    std::cout << element << " ";
  }

  return 0;
}

std::map

std::map adalah container yang menyimpan pasangan kunci-nilai yang terurut dalam bentuk BST. Kunci-kunci tersebut harus unik dan diurutkan. Berikut adalah beberapa ciri dari std::map:

Terurut: Kunci-kunci dalam std::map diurutkan berdasarkan operator pembanding yang Anda tentukan. Jika tidak ditentukan, operator kurang dari (<) akan digunakan secara default.
Unik: Kunci-kunci dalam std::map harus unik. Nilai-nilai bisa duplikat.
Efisiensi: Operasi pencarian, penyisipan, dan penghapusan pada std::map memiliki kompleksitas waktu logaritmik (O(log n)).

Berikut adalah contoh penggunaan std::map:

#include 
#include 

int main() {
  std::map myMap;

  // Menambahkan pasangan kunci-nilai ke map
  myMap["apel"] = 10;
  myMap["pisang"] = 5;
  myMap["jeruk"] = 20;

  // Mengakses nilai berdasarkan kunci
  std::cout << "Jumlah apel: " << myMap["apel"] << std::endl;

  // Mencari kunci dalam map
  if (myMap.find("pisang") != myMap.end()) {
    std::cout << "Kunci pisang ditemukan" << std::endl;
  }

  // Menghapus pasangan kunci-nilai dari map
  myMap.erase("jeruk");

  // Mencetak semua pasangan kunci-nilai dalam map
  for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
  }

  return 0;
}

Implementasi Sendiri

Anda juga dapat mengimplementasikan BST sendiri menggunakan kelas dan fungsi-fungsi Anda sendiri. Ini memungkinkan Anda untuk memiliki kontrol penuh atas struktur data dan algoritma yang Anda gunakan. Namun, Anda perlu berhati-hati dalam mengimplementasikan operasi-operasi seperti penyisipan, penghapusan, dan pencarian agar tetap menjaga sifat terurut dan keseimbangan dari BST.

Kesimpulan

Meskipun C++ tidak memiliki library standar khusus untuk BST, Anda dapat menggunakan std::set dan std::map untuk mencapai fungsionalitas serupa. Kedua container ini menyediakan efisiensi tinggi untuk berbagai operasi yang umum digunakan pada BST. Anda juga dapat mengimplementasikan BST sendiri jika Anda membutuhkan fleksibilitas dan kontrol yang lebih besar.

C++ Binary Search Tree Standard Library