MUAZHAN
Home

Balanced Binary Search Tree C++ Stl

5 min read Jun 28, 2024
Balanced Binary Search Tree C++ Stl

Balanced Binary Search Tree di C++ STL

C++ STL menyediakan container yang efisien untuk menyimpan data terurut, seperti std::set dan std::map. Kedua container ini menggunakan balanced binary search tree sebagai implementasinya. Balanced binary search tree adalah struktur data pohon biner yang menjamin bahwa tinggi pohon selalu seimbang, sehingga operasi pencarian, penyisipan, dan penghapusan dapat dilakukan dalam waktu logaritmik (O(log n)).

Keuntungan Balanced Binary Search Tree

  • Pencarian yang Efisien: Karena pohon terbalance, pencarian dapat dilakukan dengan cepat dalam waktu O(log n).
  • Penyisipan dan Penghapusan yang Efisien: Penyisipan dan penghapusan node juga dilakukan dalam waktu O(log n).
  • Urutan Terurut: Data disimpan dalam urutan terurut, memungkinkan pengambilan data terurut secara efisien.
  • Implementasi Efisien: C++ STL telah menyediakan implementasi balanced binary search tree yang dioptimalkan, sehingga Anda dapat menggunakannya dengan mudah tanpa perlu implementasi sendiri.

Jenis Balanced Binary Search Tree di C++ STL

C++ STL menggunakan self-balancing binary search trees, yaitu algoritma yang secara otomatis menjaga keseimbangan pohon saat terjadi penyisipan atau penghapusan node. Jenis-jenis balanced binary search tree yang umum digunakan di C++ STL:

  • AVL Tree: Pohon AVL (Adelson-Velskii dan Landis) adalah jenis self-balancing binary search tree yang menjaga keseimbangan dengan membatasi perbedaan tinggi antara anak kiri dan kanan setiap node menjadi maksimal 1.
  • Red-Black Tree: Pohon Red-Black adalah jenis self-balancing binary search tree yang menggunakan warna (merah atau hitam) untuk node-node dalam pohon, sehingga dapat menjaga keseimbangan dengan mempertahankan beberapa properti warna.

Penggunaan di C++ STL

Anda dapat menggunakan std::set dan std::map untuk mengakses balanced binary search tree di C++ STL.

Contoh Penggunaan std::set:

#include 
#include 

int main() {
  std::set mySet;

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

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

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

  return 0;
}

Contoh Penggunaan std::map:

#include 
#include 

int main() {
  std::map myMap;

  // Menambahkan pasangan kunci-nilai ke map
  myMap["Apple"] = 10;
  myMap["Banana"] = 5;
  myMap["Orange"] = 15;

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

  // Mengakses nilai berdasarkan kunci
  std::cout << "Nilai untuk kunci 'Banana': " << myMap["Banana"] << std::endl;

  return 0;
}

Kesimpulan

Balanced binary search tree adalah struktur data yang sangat efisien untuk menyimpan data terurut. C++ STL menyediakan implementasi balanced binary search tree yang mudah digunakan melalui container std::set dan std::map. Dengan menggunakan container ini, Anda dapat menyimpan dan mengakses data terurut dengan cepat dan efisien.

C++

Latest Posts

Featured Posts