Hola Habr!
Hace seis meses, pensé en cómo obtener un elemento de un árbol binario en O (log (N)). La respuesta llegó bastante rápido: propagación perezosa. Pero era demasiado vago para implementar esto en el código. Ahora tenemos que tomar el proyecto de graduación en la universidad, así que hago todo menos eso. Así es como me senté para implementarlo.
Algunas notas:- El árbol no está equilibrado (hasta ahora, porque el proyecto del diploma aún necesita ser escrito), como resultado de lo cual la estimación O (log (N)) se amortiza en todas partes por datos de entrada aleatorios.
- No encontré una estructura de datos similar, colegas y amigos a quienes pregunté, tampoco ofrecieron nada similar. Si conoce la implementación de tal idea, hágamelo saber.
- En la clase de vértice, uno podría prescindir del campo padre pasando el padre a los métodos.
Descripción de la idea.Almacenemos para cada vértice el número de vértices que están a la izquierda del mismo, llamemos a este campo en el conteo de vértices Más adelante. Pero luego, si agregamos el elemento más a la izquierda al árbol, tendremos que cambiar countLefter para todos los otros vértices, que pueden ser dolorosamente largos y en la raíz (oh, este juego de palabras) no se ajusta a los principios de un árbol binario. Para evitar esto, ingresemos un campo de adición para cada vértice, en el que almacenaremos cuánto necesitamos agregar al campo countLefter para cada vértice de su subárbol, incluido este vértice. Por lo tanto, al agregar el elemento más a la izquierda al árbol, solo necesita:
- Aumentar countLefter a lo largo de todo el camino que vamos al punto de inserción del nuevo vértice
- Para todos los vértices que están uno a la derecha de lo anterior, aumente la suma en 1
Ahora es lógico introducir el método push (), que agregará add al countLefter del vértice mismo y sus dos descendientes.
Así es como surgió la clase de vértice: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 + '}'; } }
¡Genial, ahora puedes comenzar a
construir un árbol!Lo primero que hacemos, ir a la cima: llamamos al método push ().
Eliminaremos el elemento eliminando a la izquierda (tomamos el vértice más a la derecha que está a la izquierda del eliminado).
Para obtener un elemento por índice, actuamos de manera bastante obvia: si index <countLefter del vértice actual, vaya a la izquierda. Si los valores son iguales, encontramos un vértice con un índice dado. De lo contrario, vamos a la derecha.
Eliminar y agregar un elemento, en principio, no es muy diferente de un árbol binario normal, excepto cambiar el countLefter y agregar campos. Si volvemos a la parte superior izquierda después de una adición / eliminación exitosa, entonces estos campos deberán cambiarse. Si a la derecha, no.
Aquí está el código del árbol: 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); } }
→
Aquí el código se puede encontrar en el github.
Daré algunos resultados de la velocidad del trabajo. Las pruebas se realizaron en:
Agregando al árbol:Entonces, agregando un millón de elementos aleatorios en el rango [0; 1_000):
Unos 100 ms. TreeSet realizó esta tarea en aproximadamente 130 ms.
Agregar un millón de elementos aleatorios en el rango [0; 10_000):
Unos 150 ms. TreeSet realizó esta tarea en unos 190 ms.
Agregar un millón de elementos aleatorios en el rango [0; 100_000):
Unos 320 ms. TreeSet realizó esta tarea en aproximadamente 415 ms.
Agregar un millón de elementos aleatorios en el rango [0; 1_000_000):
Aproximadamente 510 ms. TreeSet realizó esta tarea en aproximadamente 700 ms.
Agregar un millón de elementos aleatorios en el rango [0; 10_000_000):
Unos 590 ms. TreeSet realizó esta tarea en aproximadamente 750 ms.
Remoción ahoraAgrega aleatoriamente un millón de números al árbol. Luego intentamos eliminar un número aleatorio un millón de veces. En las pruebas, solo se tiene en cuenta el tiempo necesario para eliminar.
El rango de agregar y quitar [0; 10_000_000):
Unos 740 ms. TreeSet realizó esta tarea en aproximadamente 750 ms.
El rango de agregar y quitar [0; 1_000_000):
Unos 600 ms. TreeSet completó esta tarea en aproximadamente 800 ms (más que en la prueba anterior).
El rango de agregar y quitar [0; 100_000):
Unos 130 ms. TreeSet realizó esta tarea en aproximadamente 160 ms.
El rango de agregar y quitar [0; 10_000):
Unos 45 ms. TreeSet realizó esta tarea en unos 50 ms.
El rango de agregar y quitar [0; 1_000):
Unos 30 ms. TreeSet realizó esta tarea en aproximadamente 37 ms.
Bueno, y finalmente, en aras de que todo se inició, acceso por índiceTreeSet no tiene esta funcionalidad. Así que daré los resultados solo para UTree. Nuevamente agregamos un millón de elementos, luego obtenemos el elemento en un índice aleatorio de 0 al número de elementos en el árbol. El tiempo se tiene en cuenta solo para el acceso por índice.
Rango de adición [0; 1000): 85 ms
Rango de adición [0; 10_000): 140 ms
Rango de adición [0; 100_000): 300 ms
Rango de adición [0; 1_000_000): 655 ms
Espero que alguien encuentre útil mi idea, pero tal vez para alguien sea una ocasión para tratar con árboles binarios, si no lo ha hecho :)
PSPlaneo quedar perplejo con el equilibrio del árbol después del Año Nuevo. Si lo hago, el enlace para continuar aparecerá aquí.