[Powered by Google Translate] Como representar todos os membros da súa familia en un ordenador? Nós poderiamos simplemente usar unha lista pero non hai unha xerarquía clara aquí. 

Imos dicir que nós estamos comezando co seu bisavó, Alice. Ela ten dous fillos, Bob eo seu avó, Charlie. Charlie ten 3 fillos, seu tío, Dave, súa tía, Eva, eo seu pai, Fred. Vostede é fillo único de Fred. 

Por que organizar os seus familiares, deste xeito ser mellor que a representación da lista simple? Unha razón é que esta estrutura xerárquica, chamado "árbore", contén máis informacións do que unha simple lista. Sabemos que as relacións familiares entre todos só a través do exame da árbore. Ademais, pode acelerar look-up de tempo tremenda, os datos da árbore está clasificada. 

Non podemos aproveitar de que aquí, pero imos ver un exemplo diso en breve. Cada persoa é representada por un nó na árbore. Nós pode ter nós fillo así como un nó pai. Estes son os termos técnicos, mesmo cando se usa árbores para cousas alén de familias. Nó de Alicia ten dous fillos e non dos pais, mentres que no de Charlie ten 3 fillos e unha nai. 

Un nodo folla é aquel que non ten fillos no bordo exterior da árbore. O nodo máis alto da árbore, o nodo raíz, non ten pai. 

Unha árbore binaria é un tipo específico de árbore, en que cada nodo ten como máximo, 2 nenos. Aquí é a estrutura dun nodo dunha árbore binaria en C. Cada nodo ten algúns datos asociados e dous punteiros para outros nós. 

Na nosa árbore de familia, os datos asociados era o nome de cada persoa. Aquí é un int, que podería ser calquera cousa. Como se ve, unha árbore binaria non sería unha boa representación para unha familia, xa que as persoas moitas veces teñen máis de dous fillos. 

Unha árbore de busca binaria é un tipo especial de árbore binaria ordenada que nos permite ollar os valores rapidamente. Debe ter notado que cada nodo abaixo da raíz dunha árbore é a raíz doutra árbore, chamado de "sub". Aquí, a raíz da árbore é de 6, eo seu fillo, 2, é a raíz dunha subárvore. 

Nunha árbore de busca binaria todos os valores dun nodo é subárvore dereita son maiores que o valor do nodo. Aquí: 6. Así, os valores na subárvore esquerda dun nodo son menos que o valor do nodo. Se necesitamos tratar con valores duplicados, podemos cambiar ou daqueles a unha desigualdade solto, significa valores idénticos poden caer ou á esquerda ou á dereita, sempre que sexan consistentes sobre el todo. Esta árbore é unha árbore de busca binaria porque segue estas regras. 

Isto é como ficaría se converteu todos os nós en estruturas C. Teña en conta que, se un neno está en falta, o punteiro é nulo. Como podemos comprobar, a ver se é 7 na árbore? Comezamos na raíz. Sete é superior a 6, polo que se está na árbore, debe ser para a dereita. A continuación, é inferior a 8, polo que debe ser deixado. Aquí, nós descubrimos 7. Agora, imos comprobar a 5. Cinco é inferior a 6, polo que debe ser á esquerda. Cinco é maior que 2, debería estar seguro, e tamén é maior que 4, entón debe estar seguro de novo. Con todo, non hai ningún neno aquí. O punteiro é nulo. Isto significa que, 5 non é na nosa árbore. 

Podemos buscar a árbore binaria co seguinte código: En cada nodo, imos comprobar a ver se temos atopado o valor que estamos a buscar. Se non atopalo, imos determinar se debe ser sobre a esquerda ou dereita e comprobar que subárvore. Este ciclo vai continuar a descender da árbore ata que non haxa ningún nodo fillo de ambos á esquerda ou cara á dereita. 

Lembre que 5 non estaba na árbore. Como podemos inserir-lo? O proceso é semellante a busca. Repetimos a árbore a partir do 6 de esquerda a 2, dereita a 4, e de novo á dereita, pero 4 non ten fillo deste lado. Esta será a nova posición para 5, e el vai comezar sen fillos. 

O quão rápido son operacións nunha árbore de busca binaria? Recordar que Bigohnotation busca proporcionar un límite superior. No peor dos casos, nosa árbore podería ser simplemente unha lista encadeada o que significa que a inserción, supresión e investigación pode levar tempo proporcional ao número de nós na árbore. Este é O (n). 

Por exemplo, o seguinte é unha árbore de busca binaria válido. No entanto, se tentar atopar 9, temos que atravesan cada nó. Non é mellor que unha lista ligada. Ideal, queremos cada nodo da nosa árbore de busca binaria de 2 fillos. Desta forma, a inserción, supresión e investigación levaría, no peor dos casos, o (log n). A árbore de antes podería ser máis equilibrado, como este. Agora, mirando a calquera valor ten como máximo 3 pasos. Esta árbore é equilibrada, o que significa que é, ten unha profundidade mínima en relación ao número de nós. 

Á procura dun valor nunha árbore equilibrada de busca binaria é semellante ao de busca binaria nun array ordenado. En realidade, se nós non necesitamos inserir ou eliminar elementos, eles se comportan exactamente da mesma maneira. Con todo, a estrutura da árbore é mellor para insercións e borrados de manipulación 

O meu nome é Bannus Van der Kloot. Este é CS50.