Halo, Habr!
Enam bulan yang lalu, saya berpikir tentang cara mendapatkan elemen dari pohon biner di O (log (N)). Jawabannya datang cukup cepat - Propagasi Malas. Tetapi saya terlalu malas untuk mengimplementasikan ini dalam kode. Sekarang kita perlu mengambil proyek kelulusan di universitas, jadi saya melakukan apa pun kecuali itu. Begitulah cara saya duduk untuk mengimplementasikannya.
Beberapa catatan:- Pohon itu tidak seimbang (sejauh ini, karena proyek diploma masih perlu ditulis), akibatnya estimasi O (log (N)) di mana-mana diamortisasi untuk data input acak.
- Saya tidak menemukan struktur data yang serupa, kolega dan teman yang saya tanyakan, juga tidak menawarkan hal serupa. Jika Anda tahu implementasi gagasan semacam itu, beri tahu saya.
- Di kelas simpul, seseorang bisa membuang bidang induk dengan meneruskan induk ke metode.
Deskripsi gagasanMari kita simpan untuk setiap simpul jumlah simpul yang ada di sebelah kiri itu; mari kita panggil bidang ini di jumlah simpul. Setelah. Tapi kemudian, jika kita menambahkan elemen paling kiri ke pohon, kita harus mengubah hitungan. Setelah semua simpul lainnya, yang bisa sangat panjang dan akar (oh, permainan kata ini,) tidak sesuai dengan prinsip-prinsip pohon biner. Untuk menghindari hal ini, mari kita masukkan bidang tambah untuk setiap titik, di mana kita akan menyimpan berapa banyak kita perlu menambahkan ke bidang countLefter untuk setiap titik dari subtree-nya, termasuk titik ini sendiri. Dengan demikian, menambahkan elemen paling kiri ke pohon, Anda hanya perlu:
- Tambah countLefter di sepanjang jalur yang kita tuju ke titik penyisipan vertex baru
- Untuk semua simpul yang satu ke kanan di atas, tambahkan 1
Sekarang logis untuk memperkenalkan metode push (), yang akan menambahkan add ke countLefter dari vertex itu sendiri dan dua turunannya.
Inilah bagaimana kelas verteks muncul:public class UNode { UNode parent; int key; int countLefter; int add; UNode left; UNode right; public UNode() { } public UNode(UNode parent, int key, int countLefter, int add, UNode left, UNode right) { this.parent = parent; this.key = key; this.countLefter = countLefter; this.add = add; this.left = left; this.right = right; } public void push() { countLefter += add; if (left != null) left.add += add; if (right != null) right.add += add; add = 0; } @Override public String toString() { return "Node{" + "key=" + key + ", countLefter=" + countLefter + '}'; } }
Hebat, sekarang Anda bisa mulai
membangun pohon!Hal pertama yang kita lakukan, pergi ke atas - kita sebut metode push ().
Kami akan menghapus elemen dengan penghapusan kiri (kami mengambil paling kanan dari simpul yang ada di sebelah kiri yang dihapus).
Untuk mendapatkan elemen dengan indeks, kami bertindak cukup jelas: jika indeks <countLefter dari vertex saat ini, ke kiri. Jika nilainya sama, kami menemukan simpul dengan indeks yang diberikan. Kalau tidak, kita ke kanan.
Menghapus dan menambahkan elemen, pada prinsipnya, tidak jauh berbeda dari pohon biner biasa, kecuali untuk mengubah countLefter dan menambahkan bidang. Jika kita kembali ke atas di sebelah kiri setelah penambahan / penghapusan yang berhasil, maka bidang-bidang ini perlu diubah. Jika di sebelah kanan, tidak.
Berikut adalah kode pohon: import java.util.LinkedList; public class UTree { private UNode root; private int size; public UTree() { } public int size() { return size; } public int get(int index) { return get(index, root); } public boolean add(int key) { if (root == null) { root = new UNode(null, key, 0, 0, null, null); size++; return true; } boolean res = add(key, root); if (res) size++; return res; } public boolean remove(int key) { if (root == null) return false; if (key == this.root.key) { root.push(); removeRoot(); size--; return true; } boolean res = remove(key, root); if (res) size--; return res; } private int get(int index, UNode root) { root.push(); if (index == root.countLefter) return root.key; if (index < root.countLefter) return get(index, root.left); return get(index, root.right); } private boolean add(int key, UNode root) { if (key == root.key) return false; root.push(); if (key < root.key) if (root.left != null) { boolean res = add(key, root.left); if (res) { root.countLefter++; if (root.right != null) root.right.add++; } return res; } else { root.left = new UNode(root, key, root.countLefter, 0, null, null); root.countLefter++; if (root.right != null) root.right.add++; return true; } if (root.right != null) return add(key, root.right); else { root.right = new UNode(root, key, root.countLefter + 1, 0, null, null); return true; } } public boolean removeByIndex(int index) { if(this.root == null) return false; root.push(); if (index == this.root.countLefter) { removeRoot(); return true; } boolean res = removeByIndex(index, root); if (res) size--; return res; } private boolean removeByIndex(int index, UNode root) { if (root == null) return false; root.push(); if (index == root.countLefter) return removeNode(root); if (index < root.countLefter) { boolean res = removeByIndex(index, root.left); if (res) { root.countLefter--; if (root.right != null) root.right.add--; } return res; } else return removeByIndex(index, root.right); } private boolean removeNode(UNode root) { if (root.left == root.right) { if (root.parent.left == root) root.parent.left = null; else root.parent.right = null; return true; } if (root.left == null) { if (root.parent.left == root) { root.parent.left = root.right; root.right.add--; } else { root.parent.right = root.right; root.right.add--; } root.right.parent = root.parent; return true; } if (root.right == null) { if (root.parent.left == root) root.parent.left = root.left; else root.parent.right = root.left; root.left.parent = root.parent; return true; } UNode right = getRight(root.left); cut(right); root.key = right.key; root.countLefter--; root.right.add--; return true; } private boolean remove(int key, UNode root) { if (root == null) return false; root.push(); if (key == root.key) return removeNode(root); if (key < root.key) { boolean res = remove(key, root.left); if (res) { root.countLefter--; if (root.right != null) root.right.add--; } return res; } else return remove(key, root.right); } private void removeRoot() { if (root.left == root.right) { root = null; return; } if (root.left == null) { root = root.right; root.add--; return; } if (root.right == null) { root = root.left; return; } UNode right = getRight(root.left); cut(right); root.key = right.key; root.countLefter--; root.right.add--; } private static void cut(UNode node) { if (node.parent.left == node) node.parent.left = node.left; else node.parent.right = node.left; if (node.left != null) node.left.parent = node.parent; } private UNode getRight(UNode root) { root.push(); if (root.right == null) return root; return getRight(root.right); } public void printTree() { printTree(root); } private void printTree(UNode root) { if (root == null) return; root.push(); printTree(root.left); System.out.println(root); printTree(root.right); } public LinkedList<UNode> getAll(){ LinkedList<UNode> res = new LinkedList<>(); getAll(root, res); return res; } private void getAll(UNode root, LinkedList<UNode> res){ if (root == null) return; root.push(); getAll(root.left, res); res.add(root); getAll(root.right, res); } }
→
Di sini kodenya dapat ditemukan di github.
Saya akan memberikan beberapa hasil kecepatan kerja. Pengujian dilakukan pada:
Menambahkan ke pohon:Jadi, menambahkan sejuta elemen acak dalam rentang [0; 1_000):
Sekitar 100 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 130 ms.
Menambahkan sejuta elemen acak dalam rentang [0; 10_000):
Sekitar 150 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 190 ms.
Menambahkan sejuta elemen acak dalam rentang [0; 100_000):
Sekitar 320 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 415 ms.
Menambahkan sejuta elemen acak dalam rentang [0; 1_000_2000):
Sekitar 510 ms. TreeSet menyelesaikan tugas ini dalam waktu kurang lebih 700 ms.
Menambahkan sejuta elemen acak dalam rentang [0; 10_299_2000):
Sekitar 590 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 750 ms.
Penghapusan sekarangTambahkan satu juta angka ke pohon secara acak. Kemudian kami mencoba menghapus angka acak satu juta kali. Dalam tes, hanya waktu yang diambil untuk menghapus diperhitungkan.
Kisaran menambah dan menghapus [0; 10_299_2000):
Sekitar 740 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 750 ms.
Kisaran menambah dan menghapus [0; 1_000_2000):
Sekitar 600 ms. TreeSet menyelesaikan tugas ini dalam waktu kurang lebih 800 ms (lebih banyak dari pada tes sebelumnya).
Kisaran menambah dan menghapus [0; 100_000):
Sekitar 130 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 160 ms.
Kisaran menambah dan menghapus [0; 10_000):
Sekitar 45 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 50 ms.
Kisaran menambah dan menghapus [0; 1_000):
Sekitar 30 ms. TreeSet menyelesaikan tugas ini dalam waktu sekitar 37 ms.
Yah, dan akhirnya, demi semuanya dimulai, akses dengan indeksTreeSet tidak memiliki fungsi ini. Jadi saya akan memberikan hasil hanya untuk UTree. Sekali lagi kita menambahkan sejuta elemen, lalu kita mendapatkan elemen pada indeks acak dari 0 hingga jumlah elemen di pohon. Waktu diperhitungkan hanya untuk akses oleh indeks.
Rentang Tambahan [0; 1000): 85 ms
Rentang Tambahan [0; 10_000): 140 ms
Rentang Tambahan [0; 100_000): 300 ms
Rentang Tambahan [0; 1_000_2000): 655 ms
Saya harap seseorang menemukan ide saya berguna, tetapi mungkin bagi seseorang ini akan menjadi kesempatan untuk berurusan dengan pohon biner, jika Anda belum melakukannya :)
PSSaya berencana untuk bingung dengan menyeimbangkan pohon setelah Tahun Baru. Jika saya melakukannya, tautan untuk melanjutkan akan muncul di sini.