B-trees (balanced-trees)

• balanceados

• los nodos están ordenados

  

min: t-1

max: 2t-1

Con orden 2:

Pedirle a anita pizarrón derecho (ejemplos de lo mismo)

Ejemplo:

Una aplicación es para una base de datos SQL

Primitivas

Delete

• Caso I: lo que quiero borrar está en una hoja

  • A) Si no rompe el mínimo 😃
  • B) Puedo tomar prestado de mis hermanos?

  

  • C) No puedo prestar

    

  Caso 2: es un nodo interno

  • Predecesor inorden
  • Sucesor inorden

  2A: tiene predecesor o sucesor para reemplazarlo

  • Me fijo si a alguno de los hijos le sobra uno

  Ver ejemplo 16:50 aprox (9/4)

  2B: no tiene reemplazo

  Mergeo a los hijos

  

  Caso 3: Interno pero deja al nodo en 0

  3A:Tengo predecesor o sucesor

  Subo el más grande del izquierdo o el más chico del derecho

  3B: no tengo predecesor ni sucesor

  Bajo de nivel el árbol

  Mergeo los hijos que quedan de un lado

  

  <aside> ‼️ Es importante hacer delete e insert en los B-tree, va a entrar en el examen!

  </aside>

  B+

  Los que están arriba siempre son copias de los que están abajo, sirve para indexar. Los elementos solamente son los que están abajo de todo. Los de arriba son indicadores.