This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
package library.ds; import java.util.stream.IntStream; /** * AVL木 * TreeSetだが、O(log n)で任意のインデックスの要素にアクセスできる * @param <T> */ public final class AVLTree<T extends Comparable<? super T>> { static final class Node<T extends Comparable<? super T>> { T val; @SuppressWarnings("unchecked") Node<T>[] ch = new Node[2]; int dep, size; Node(final T val, Node<T> l, Node<T> r) { this.val = val; dep = size = 1; ch[0] = l; ch[1] = r; } } private Node<T> root; private final int depth(final Node<T> t){ return t == null ? 0 : t.dep; } private final int count(final Node<T> t){ return t == null ? 0 : t.size; } private final Node<T> update(final Node<T> t) { t.dep = Math.max(depth(t.ch[0]), depth(t.ch[1])) + 1; t.size = count(t.ch[0]) + count(t.ch[1]) + 1; return t; } private final Node<T> rotate(Node<T> t, final int b) { Node<T> s = t.ch[1 - b]; t.ch[1 - b] = s.ch[b]; s.ch[b] = t; t = update(t); s = update(s); return s; } private final Node<T> fetch(Node<T> t) { if(t == null) { return t; } if(depth(t.ch[0]) - depth(t.ch[1]) == 2) { if(depth(t.ch[0].ch[1]) > depth(t.ch[0].ch[0])) { t.ch[0] = rotate(t.ch[0], 0); } t = rotate(t, 1); } else if(depth(t.ch[0]) - depth(t.ch[1]) == -2) { if (depth(t.ch[1].ch[0]) > depth(t.ch[1].ch[1])) { t.ch[1] = rotate(t.ch[1], 1); } t = rotate(t, 0); } return t; } private final Node<T> insert(final Node<T> t, final int k, final T v) { if(t == null) { return new Node<T>(v, null, null); } final int c = count(t.ch[0]), b = (k > c) ? 1 : 0; t.ch[b] = insert(t.ch[b], k - (b == 1 ? (c + 1) : 0), v); update(t); return fetch(t); } private final Node<T> erase(final Node<T> t) { if(t == null || t.ch[0] == null && t.ch[1] == null) { return null; } if(t.ch[0] == null || t.ch[1] == null) { return t.ch[t.ch[0] == null ? 1 : 0]; } return fetch(update(new Node<T>(find(t.ch[1], 0).val, t.ch[0], erase(t.ch[1], 0)))); } private final Node<T> erase(Node<T> t, final int k) { if(t == null) { return null; } final int c = count(t.ch[0]); if(k < c) { t.ch[0] = erase(t.ch[0], k); t = update(t); } else if(k > c) { t.ch[1] = erase(t.ch[1], k - (c + 1)); t = update(t); } else { t = erase(t); } return fetch(t); } private final Node<T> find(final Node<T> t, final int k) { if(t == null) { return t; } final int c = count(t.ch[0]); return k < c ? find(t.ch[0], k) : k == c ? t : find(t.ch[1], k - (c + 1)); } private final int cnt(final Node<T> t, final T v) { if(t == null) { return 0; } if(t.val.compareTo(v) < 0) { return count(t.ch[0]) + 1 + cnt(t.ch[1], v); } if(t.val.equals(v)) { return count(t.ch[0]); } return cnt(t.ch[0], v); } /** * コンストラクタ */ public AVLTree(){ root = null; } /** * 要素を追加する * @param val */ public final void add(final T val){ root = insert(root, cnt(root, val), val); } /** * k番目の要素を削除する * @param k */ public final void remove(final int k){ root = erase(root, k); } /** * AVLTree[k]を返す * @param k * @return k番目の要素 */ public final T get(final int k){ return find(root, k).val; } /** * AVLTreeに含むvalの個数を返す * @param val * @return valの個数 */ public final int count(final T val){ return cnt(root, val); } /** * AVL木の大きさを返す * @return AVL木のサイズ */ public final int size(){ return root.size; } /** * AVLTreeを配列に変換したものを返す * @return AVLTreeの配列 */ @SuppressWarnings("unchecked") public final T[] toArray(){ return (T[]) IntStream.range(0, root.size).mapToObj(this::get).toArray(); } @Override public final String toString() { final StringBuilder sb = new StringBuilder(); sb.append(get(0)); for(int i = 0; ++i < root.size;) { sb.append(", " + get(i)); } return "[" + sb.toString() + "]"; } }
Traceback (most recent call last): File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode() File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle raise RuntimeError('bundler is not specified: {}'.format(str(path))) RuntimeError: bundler is not specified: Java/library/ds/AVLTree.java