- Seri: Trees (video)
- konstruksi pohon dasar
- traversal
- algoritma manipulasi
- BFS(breadth-first search) dan DFS(depth-first search) (video)
- Catatan BFS:
- level order (BFS, menggunakan queue)
- kompleksitas waktu: O(n)
- kompleksitas ruang: terbaik: O(1) terburuk: O(n/2)=O(n)
- Catatan DFS:
- kompleksitas waktu: O(n)
- kompleksitas ruang: terbaik: O(log n) - rata-rata. ketinggian tree terburuk: O(n)
- dalam urutan (DFS: kiri, sendiri/self, kanan)
- pasca urutan (DFS: kiri, kanan, sendiri/self)
- pra urutan (DFS: sendiri/self, kiri, kanan)
- Catatan BFS:
- Ulasan Binary Search Tree (video)
- Serial (video)
- starts with symbol table and goes through BST applications
- Pendahuluan (video)
- MIT (video)
- C/C++:
- Binary search tree - Implementasi di C/C++ (video)
- Implementasi BST - alokasi memori di stack dan heap (video)
- Temukan min dan max elemen dalam binary search tree (video)
- Temukan ketinggian pohon biner (video)
- Binary tree traversal - strategi luas-pertama dan mendalam-pertama (video)
- Pohon biner: Level Order Traversal (video)
- Binary tree traversal: Preorder, Inorder, Postorder (video)
- Periksa apakah pohon biner adalah binary search tree atau bukan (video)
- Hapus node dari Binary Search Tree (video)
- Penerus Berurutan di binary search tree (video)
- Implementasikan:
- insert // masukkan nilai ke dalam pohon
- get_node_count // dapatkan hitungan nilai yang disimpan
- print_values // mencetak nilai di pohon, dari min hingga maks
- delete_tree
- is_in_tree // mengembalikan nilai true jika nilai yang diberikan ada di pohon
- get_height // mengembalikan tinggi dalam node (tinggi node tunggal adalah 1)
- get_min // mengembalikan nilai minimum yang disimpan di pohon
- get_max // mengembalikan nilai maksimum yang disimpan di pohon
- is_binary_search_tree
- delete_value
- get_successor // mengembalikan nilai tertinggi berikutnya di pohon setelah nilai yang diberikan, -1 jika none
- Heap (tumpukan)
- Priority Queue (Prioritas Antrian)
- Binary Heap (Biner Heap)
- divisualisasikan sebagai pohon, tetapi biasanya linier dalam penyimpanan (array, linked list)
- Heap
- Pendahuluan (video)
- Penerapan Naif (video)
- Pohon Biner (video)
- Keterangan Tinggi Pohon (video)
- Operasi Dasar (video)
- Pohon Biner Lengkap (video)
- Pseudocode (video)
- Urutan Heap - lompat untuk memulai (video)
- Urutan Heap (video)
- Membangun heap (video)
- MIT: Heaps dan Heap Sort (video)
- CS 61B Kuliah 24: Antrian Prioritas (video)
- Linear Time BuildHeap (max-heap)
- Menerapkan sebuah max-heap:
- insert
- sift_up - dibutuhkan untuk memasukkan
- get_max - mengembalikan item maksimal, tanpa menghapusnya
- get_size() - mengembalikan jumlah elemen yang disimpan
- is_empty() - mengembalikan nilai true jika heap tidak berisi elemen
- extract_max - mengembalikan item maksimal, menghapusnya
- sift_down - dibutuhkan untuk extract_max
- remove(i) - menghapus item pada indeks i
- heapify - membuat heap dari larik elemen, dibutuhkan untuk heap_sort
- heap_sort() - mengambil array yang tidak disortir dan mengubahnya menjadi array yang diurutkan di tempat menggunakan heap maks atau heap min
Selanjutnya - Penyortiran