Struktur Data Trie di Java

1. Ikhtisar

Struktur data mewakili aset penting dalam pemrograman komputer, dan mengetahui kapan dan mengapa menggunakannya sangat penting.

Artikel ini adalah pengantar singkat untuk trie (dibaca "mencoba") struktur data, implementasi dan analisis kompleksitasnya.

2. Trie

Trie adalah struktur data diskrit yang tidak cukup terkenal atau disebutkan secara luas dalam kursus algoritme tipikal, namun tetap penting.

Trie (juga dikenal sebagai pohon digital) dan kadang-kadang bahkan pohon radix atau pohon awalan (karena mereka dapat dicari dengan awalan), adalah struktur pohon terurut, yang memanfaatkan kunci yang disimpannya - biasanya string.

Posisi simpul di pohon menentukan kunci yang terkait dengan simpul itu, yang membuat percobaan berbeda dibandingkan dengan pohon pencarian biner, di mana simpul menyimpan kunci yang hanya sesuai dengan simpul itu.

Semua turunan dari sebuah node memiliki awalan yang sama dari String yang terkait dengan node tersebut, sedangkan root dikaitkan dengan String kosong .

Di sini kami memiliki pratinjau TrieNode yang akan kami gunakan dalam implementasi Trie kami:

public class TrieNode { private HashMap children; private String content; private boolean isWord; // ... }

Mungkin ada beberapa kasus ketika trie adalah pohon pencarian biner, tetapi secara umum, ini berbeda. Baik pohon pencarian biner maupun percobaan adalah pohon, tetapi setiap simpul dalam pohon pencarian biner selalu memiliki dua anak, sedangkan simpul mencoba, di sisi lain, dapat memiliki lebih banyak.

Dalam percobaan, setiap node (kecuali root node) menyimpan satu karakter atau digit. Dengan melintasi trie ke bawah dari simpul akar ke simpul n tertentu , awalan karakter atau digit yang sama dapat dibentuk yang juga digunakan oleh cabang lain dari trie.

Dengan melintasi trie dari simpul daun ke simpul akar, String atau urutan digit dapat dibentuk.

Berikut adalah kelas Trie , yang merupakan implementasi dari struktur data trie:

public class Trie { private TrieNode root; //... }

3. Operasi Umum

Sekarang, mari kita lihat bagaimana mengimplementasikan operasi dasar.

3.1. Memasukkan Elemen

Operasi pertama yang akan kami jelaskan adalah penyisipan node baru.

Sebelum kita memulai implementasi, penting untuk memahami algoritme:

  1. Tetapkan node saat ini sebagai node root
  2. Tetapkan huruf saat ini sebagai huruf pertama dari kata tersebut
  3. Jika node saat ini sudah memiliki referensi ke huruf saat ini (melalui salah satu elemen di kolom "anak"), maka setel node saat ini ke node yang direferensikan tersebut. Jika tidak, buat node baru, atur huruf yang sama dengan huruf saat ini, dan juga inisialisasi node saat ini ke node baru ini
  4. Ulangi langkah 3 hingga kunci melintasi

Kompleksitas operasi ini adalah O (n) , di mana n mewakili ukuran kunci.

Berikut implementasi dari algoritma ini:

public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true); }

Sekarang mari kita lihat bagaimana kita dapat menggunakan metode ini untuk memasukkan elemen baru dalam trie:

private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie; }

Kita dapat menguji bahwa trie telah diisi dengan node baru dari pengujian berikut:

@Test public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty()); }

3.2. Menemukan Elemen

Sekarang mari tambahkan metode untuk memeriksa apakah elemen tertentu sudah ada dalam trie:

  1. Dapatkan anak-anak dari akar
  2. Iterasi melalui setiap karakter String
  3. Periksa apakah karakter itu sudah menjadi bagian dari sub-trie. Jika tidak ada di manapun dalam percobaan, maka hentikan pencarian dan kembalikan false
  4. Ulangi langkah kedua dan ketiga hingga tidak ada karakter yang tersisa di String. Jika akhir String tercapai, return true

Kompleksitas algoritma ini adalah O (n) , di mana n mewakili panjang kunci.

Implementasi Java bisa terlihat seperti:

public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord(); }

Dan beraksi:

@Test public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life")); }

3.3. Menghapus sebuah Elemen

Selain menyisipkan dan menemukan elemen, jelas bahwa kita juga perlu menghapus elemen.

Untuk proses penghapusan, kita perlu mengikuti langkah-langkah berikut:

  1. Periksa apakah elemen ini sudah menjadi bagian dari trie
  2. Jika elemen ditemukan, hapus dari trie

Kompleksitas algoritma ini adalah O (n) , di mana n mewakili panjang kunci.

Mari kita lihat sekilas implementasinya:

public void delete(String word) { delete(root, word, 0); } private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false; }

Dan beraksi:

@Test void whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming")); }

4. Kesimpulan

Dalam artikel ini, kita telah melihat pengantar singkat untuk mencoba struktur data dan operasi yang paling umum serta implementasinya.

Kode sumber lengkap untuk contoh yang ditampilkan dalam artikel ini dapat ditemukan di GitHub.