in

Árbol binario | Conjunto 3 (tipos de árbol binario)

gfg 200x200 min

Hemos discutido la Introducción al árbol binario en el conjunto 1 y las propiedades del árbol binario en el conjunto 2. En esta publicación, se discuten los tipos comunes de árboles binarios.

Los siguientes son tipos comunes de árboles binarios.

Árbol binario completo Un árbol binario es un árbol binario completo si cada nodo tiene 0 o 2 hijos. Los siguientes son ejemplos de un árbol binario completo. También podemos decir que un árbol binario completo es un árbol binario en el que todos los nodos, excepto los nodos hoja, tienen dos hijos.

               18
           /         
         15         30  
        /          /  
      40    50    100   40

             18
           /       
         15     20    
        /         
      40    50   
    /   
   30   50

               18
            /       
          40       30  
                   /  
                 100   40

Árbol binario completo: Un árbol binario es un árbol binario completo si todos los niveles están completamente llenos, excepto posiblemente el último nivel y el último nivel tiene todas las claves a la izquierda.

Los siguientes son ejemplos de árboles binarios completos

               18
           /         
         15         30  
        /          /  
      40    50    100   40


               18
           /         
         15         30  
        /          /  
      40    50    100   40
     /     /
    8   7  9 

Un ejemplo práctico de árbol binario completo es Binary Heap.

Árbol binario perfecto Un árbol binario es un árbol binario perfecto en el que todos los nodos internos tienen dos hijos y todos los nodos hoja están en el mismo nivel.
Los siguientes son ejemplos de árboles binarios perfectos.

               18
           /         
         15         30  
        /          /  
      40    50    100   40


               18
           /         
         15         30  

En un árbol binario perfecto, el número de nodos hoja es el número de nodos internos más 1

L = I + 1 Donde L = Número de nodos hoja, I = Número de nodos internos.

Un árbol binario perfecto de altura h (donde la altura del árbol binario es el camino más largo desde el nodo raíz a cualquier nodo hoja en el árbol, la altura del nodo raíz es 1) tiene 2h – 1 nodo.

Un ejemplo de un árbol binario perfecto son los antepasados ​​de la familia. Mantenga a una persona en la raíz, a los padres como hijos, a los padres de padres como a sus hijos.

Árbol binario equilibrado
Un árbol binario está equilibrado si la altura del árbol es O (Log n) donde n es el número de nodos. Por ejemplo, el árbol AVL mantiene la altura O (Log n) asegurándose de que la diferencia entre las alturas de los subárboles izquierdo y derecho sea como máximo 1. Los árboles rojo-negro mantienen la altura O (Log n) asegurándose de que el número de nodos negros en cada ruta de raíz a hoja es el mismo y no hay nodos rojos adyacentes. Los árboles de búsqueda binaria equilibrada son buenos en cuanto al rendimiento, ya que proporcionan tiempo O (log n) para buscar, insertar y eliminar.

Un árbol degenerado (o patológico) Un árbol donde cada nodo interno tiene un hijo. Dichos árboles tienen el mismo rendimiento que la lista vinculada.

      10
      /
    20
     
     30
      
      40     

Fuente:
https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

¡Atención lector! No dejes de aprender ahora. Obtenga todos los conceptos importantes de DSA con el Curso autodidacta de DSA a un precio asequible para los estudiantes y prepárese para la industria. Para completar su preparación desde el aprendizaje de un idioma hasta DS Algo y muchos más, consulte Curso completo de preparación para entrevistas.

En caso de que desee asistir clases en vivo con expertos, consulte Clases en vivo de DSA para profesionales que trabajan y Programación competitiva en vivo para estudiantes.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

apple touch icon@2

¿Cómo obtengo la fecha actual en JavaScript?

250px Microprocessor

32 bits frente a 64 bits: diferencia y comparación