Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Trees

20/25
Recursos

Aportes 17

Preguntas 3

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

Por favor, no te asustes al llegar a esta clase, es muy sencillo:
.
Un Binary Search Tree básicamente costa de un elemento root (El elemento padre del que todos descienden). Es a partir de ese elemento en donde se empieza la búsqueda.
.
La condición es simple, un elemento únicamente puede tener dos descendientes, no más. Los descendientes que son mayores que el elemento padre se colocan del lado derecho y los descendientes que son menores se colocan del lado izquierdo, simple, ¿verdad?
.
Para buscar en un Binary Search Tree simplemente tienes que preguntarte: ¿Este elemento es mayor o menor que el que estoy buscando? Ohh es mayor, entonces me voy para la izquierda, y así sucesivamente hasta que encuentres el elemento que estabas buscando.

Los arboles son una estructura de datos que puede ser lineal o no ( ahora lo vemos), los arboles tienen una estructura con nodos que estos representan ser los hijos podemos ver en esta imagen todos los componentes que forman un arbol

  • Root o Raiz: Es el nodo superior de todo el arbol, si sabes HTML(lo mas probable es que si) seria como en el DOM el HTML es el elemento root o más bien el padre
  • Parent / Padre: Contienen ramas que apuntan a otros nodos
  • Child / Hijos: Es un nodo conectado directamente con otro cuando se aleja de la raiz
  • Lead / Hojas: Un nodo sin hijos
  • Sibling / Hermanos: Son un conjunto de nodos que vienen del mismo padre
  • Sub Tree / Sub Arbol: Son arboles que estan dentro de nodos
  • Arm / Baso: Es la conexión entre un nodo y otro
<h3>Binary Trees / Arboles Binarios</h3> <h4>Perfect Binary Tree</h4> <h3>Este tipo de arboles en concreto lo que hacen es que sus nodos se van multiplicando y van aumentando y a esto se le llama arbol balanceado porque tiene la misma cantidad de nodos en ambos lados, un ejemplo visual seria algo así:</h3>

Luego estan los

<h3>Binary Search Trees</h3>

lo que pasa con estos es que nos permiten poder buscar los datos de una manera ordenada porque se ordenan, de un lado se ponen los numeros que disminuyen y de el otro lado los numeros que aumentan

Compañeros no se supone que el 10 señalado en la imagen debería ser un número mayor a 33?

🌲 Trees

<h4>Ideas/conceptos claves</h4>

Un árbol es una estructura (posiblemente no lineal) de datos compuesta de nodos, vértices y aristas que es acíclica. Un árbol que no tiene ningún nodo se llama árbol vacío o nulo. Un árbol que no está vacío consta de un nodo raíz y potencialmente muchos niveles de nodos adicionales que forman una jerarquía.

<h4>Apuntes</h4> <h3>Anatomia de un tree</h3>
  • En un tree tenemos un nodo principal de donde se ira ramificando
  • tenemos parents ⇒ tienen ramas
  • Tenemos hojas o nodos finales
<h3>Binary Tree</h3>
  • Tiene un nodo principal el cual tendrá N ramas, las siguientes ramas que salen de estas serán el doble o 2N
  • Estos árboles se llaman arboles balanceados porque tienen una misma cantidad a la derecha e izquierda
  • Existen diferentes clases de arboles
<h3>Binary Search Tree</h3>
  • Nos ayuda para buscar información
  • La forma en la que se acomodan los datos son la siguiente
  • Una de las reglas es que los números que van de aumento van en el derecho y decremento en el lado izquierdo
  • Nos ayuda a buscar entre grandes cantidades de datos que podemos llegar a tener con la técnica “divide y vencerás”
<h3>Binary Search Trees: unbalanced tree</h3>
  • Existen árboles que no están balanceados, para ello existen ciertos algoritmos que nos ayudan a balancearlos

  • Los métodos que contienen esta estructura de datos son los siguientes:
    • Search ⇒ Buscar por un nodo
    • Insert ⇒ Insertar un nodo
    • Delete ⇒ Borrar un nodo

RESUMEN: Un arbol es una estructura de datos la cual nos ayuda a organizar de una manera eficiente grandes cantidades de datos, es una estructura la cual tiene hijos los cuales pueden contener otros hijos, además que se pueden ordenar de una manera determinada.

No se porque recordaba los trees más difíciles, debe ser porque Diego explica todo para que parezca muy sencillo.

🌳 Un tree esta compuesta de nodos, vértices y aristas. Es usada con frecuencia en la Inteligencia artificial.

🌲Trees

<h3>Trees</h3>

Consta de un único elemento raíz, que es de donde parten todos los hijos, y los hijos de estos, el termino correcto es que se genera una ramificación de datos.
Se compone de nodos y apartir del nodo raíz se empeiza a ramificar todos los demás nodos.
.
Los nodos padres son aquellos de los cuales se desprendes otras ramas, las cuales serán sus hijos.
.
Tambien tenemos las hojas del árbol (leafs) que son los nodos finales. El ultimo nodo de cada ramificación.
.
Los nodos hermanos son los nodos que provengan del mismo padre
Y por ultimo tenemos los sub arboles, estos se forman en la ramificaciones que se vayan haciendo…


<h3>binary tree (perfect binary tree)</h3>

Este es otro tipo de arbol y lo que lo hace especial es que sus nodos se van multiplicando, también se conoce como árbol balanceado, ya que tiene la misma cantidad de nodos a ambos lados del árbol.


<h3>binary search tree</h3>

Hay muchos tipos de tres pero estos son solo alguno y este en particular es muy útil.
Tiene la misma estructura de un binary tree perfect o árbol balanceado pero se diferencia en algo y es que un nodo solo puede tener dos ramificaciones y estas a su vez siguen un patrón:

  • A la izquierda iran los elementos que sean menores a su padre directo
  • A la derecha iran los elementos que sean mayores a su padre directo
    .
    Esto en que nos ayuda? Bueno en mucho, ya que nos ayuda a buscar valores de manera mas rápida. Aplicando el algoritmo “divide and conquer” Este se aplica a la búsqueda binaria, justo lo como se llama este árbol. Coincidencia? Para nada!

Si aun se sienten confundidos respecto a los Binary search trees, les recomiendo el curso de matemáticas discretas:
https://platzi.com/clases/discretas/

Lastima que no se van a ver balanceadores, es un tema bien interesante, sobre todo por su complejidad, sobre todo en árboles n-arios

super explicación

Binary Search Trees
Un árbol de búsqueda binario se puede implementar usando una estructura vinculada.
Recuerde que las listas, pilas y colas son estructuras lineales que consisten en una secuencia de elementos. Un árbol binario es una estructura jerárquica. O está vacío o consiste en un elemento, llamado raíz, y dos árboles binarios distintos, llamados subárbol izquierdo y subárbol derecho, uno o ambos pueden estar vacíos. Ejemplos de árboles binarios se muestran en la siguiente Figura:

Un comentario para quienes vienen aprendiendo CSS =

Esta es una estructura similar a como se manejan los selectores en la metodologia BEM. Padres Hijos, en el orden jerarquico, pero tambien usamos ahí hermanos, y repetimos la secuencia si queremos usar mayor especificidad.

prepend(value){
	const nodo = new Node(value)
	const lastPointer = this.getTheIndex(2)
	lastPointer.prev = this.head
	this.head.prev = nodo
	this.head = nodo
	this.length++
	return this
}

Si les cuesta entender porque le llaman árbol, denle la vuelta

los valores del lado izquierdo del arbol nunca debe ser mayor al root parent