Soy consciente de las formas de mantener los árboles de búsqueda binarios equilibrados / autoequilibrados mediante rotaciones.

No estoy seguro de que mi caso deba ser tan complicado. No necesito mantener ninguna propiedad de orden ordenada como con las BST autoequilibradas. Solo tengo un árbol binario ordinario que puede que necesite para eliminar nodos o insertar nodos. Necesito intentar mantener el equilibrio en el árbol. Para simplificar, mi árbol binario es similar a un árbol de segmentos, y cada vez que se elimina un nodo, todos los nodos a lo largo de la ruta desde la raíz hasta este nodo se verán afectados (en mi caso, es solo una resta de los valores nodales) . De manera similar, cada vez que se inserta un nodo, todos los nodos desde la raíz hasta la ubicación final del nodo insertado se verán afectados (una adición a los valores nodales esta vez).

¿Cuál sería la forma más sencilla de mantener equilibrado un árbol como este? No es necesario que esté tan equilibrado en altura como los árboles AVL, pero algo como los árboles RB o tal vez un poco menos equilibrado también es aceptable.

1
user5965026 13 mar. 2021 a las 05:14

1 respuesta

Al equilibrar no BST, la gran pregunta es

¿Puede su árbol soportar rotaciones de manera eficiente?

Algunos tipos de árboles binarios, como los árboles k-d, tienen una estructura específica capa por capa que hace que las rotaciones no sean factibles. Otros, como los árboles de rango, tienen metadatos auxiliares en cada nodo que son costosos de actualizar después de una rotación. Pero si puede manejar las rotaciones, entonces puede usar casi cualquiera de las estrategias de equilibrio que existen. La opción más simple podría ser modelar su árbol en un treap: coloque un campo de peso elegido al azar en cada nodo y luego, durante las inserciones, gire la hoja recién agregada hacia arriba hasta que su peso sea menor que el de su padre. Para eliminar, rote repetidamente el nodo con su hijo más claro hasta que sea una hoja, luego elimínelo.

Si no puede admitir rotaciones, necesitará una estrategia de reequilibrio que no las requiera. Quizás la opción más fácil que existe es modelar su árbol después de un árbol de chivo expiatorio, que funciona detectando perezosamente un nodo que es demasiado profundo para que el árbol esté equilibrado, luego reconstruyendo el subárbol desequilibrado más pequeño posible en un árbol perfectamente equilibrado para volver a poner todo en su lugar. orden. Las eliminaciones se manejan reconstruyendo todo el árbol una vez que el número de nodos cae en algún factor constante.

0
templatetypedef 13 mar. 2021 a las 02:42