Download Árboles

Estructura de Datos En C++
Dr. Romeo Sánchez Nigenda.
E-mail: romeo.sanchez@gmail.com
http://yalma.fime.uanl.mx/~romeo/
Oficina: 1er. Piso del CIDET. Oficina con Dr. Oscar Chacón
Horas de Tutoría: 10am-11am Martes y Jueves,
3:30pm-4:30pm Miércoles, 2:00pm-4:00pm Viernes.
Website: http://yalma.fime.uanl.mx/~romeo/ED/2011/
Sesiones: 48
Material de apoyo:
Estructura de Datos con C y C++.
Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum, Brooklyn College
Segunda Edición, Prentice-Hall.
Algorithms. Third Edition.
Parts 1-4, Fundamentals Data Structures Sorting Searching
Robert Sedgewick.
Estructura de Datos.
Román Martínez, Elda Quiroga.
Thomson Learning.
Cualquier libro de Estructura de Datos!
Software:
Compiladores GCC (GNU Compiler Collection)
IDEs (Integrated Development Environment):
http://www.eclipse.org/downloads/
http://kdevelop.org/
http://www.bloodshed.net/devcpp.html
6. Árboles

Objetivo: El alumno entenderá y aprenderá las estructuras
de datos no lineales y dinámicas más importantes en
computación.

Temario:
◦
◦
◦
◦
Árboles en general
Árboles binarios
Árboles balanceados
Árboles multicaminos
Árboles

En Informática, los árboles son abstracciones matemáticas que
juegan un rol central en el diseño y análisis de algoritmos, porque:
◦ Los usamos para describir propiedades dinámicas de los algoritmos
◦ Construimos estructuras de datos que son realizaciones concretas de
árboles.

Podemos concluir que un árbol es entonces una estructura de
datos que mantiene un conjunto de nodos conectados (imitando la
forma de un árbol).

Encontramos muchos ejemplos de árboles en nuestra vida diaria:
◦
◦
◦
◦
◦
Organización de torneos deportivos
Árboles familiares (ascendientes y descendientes)
Organigramas de corporaciones
Procesamiento de lenguaje natural
Organización de sistemas de archivos (directorios y archivos)
Árboles

Existen diferentes tipos de árboles:
◦ Árboles en general
◦ Árboles binarios (AVL, Rojo-Negro, AA)
◦ Árboles balanceados
◦ Árboles multi-caminos (B, B+, B*)

En general un árbol es un conjunto de vértices y aristas que satisfacen
ciertos requisitos.
◦ Un vértice es un objeto simple, también denominado nodo, que contiene información.
◦ Una arista (o arco) es una conexión entre dos vértices
◦ Un camino (o ruta) en un árbol es una lista de vértices distintos, en los que cada uno de
ellos se encuentran conectados sucesivamente por aristas en el árbol.

La propiedad definitoria de un árbol es que existe solamente un camino o
ruta conectando un par de nodos. Si hay más de un camino entre dos
nodos, o si no hay un camino entre un par de nodos, entonces lo que
tenemos es un Grafo.
Árboles: Terminología

Un nodo por lo tanto, es la unidad sobre la que se construye el árbol, y
puede tener cero o más nodos hijos conectados a él (por medio de
aristas) esta propiedad se le denomina grado.

Se dice que un nodo a es padre de un nodo b (o b es hijo de a) si existe un
enlace desde a hasta b.

Un árbol solo puede tener un único nodo sin padres, al cual se le
denomina raíz. En un árbol con raíz, cualquier nodo es la raíz de un
subárbol, el cual consiste de sí mismo y de los nodos descendientes de él

Un nodo que no tiene hijos se le denomina hoja o terminal.

El resto de los nodos se les conoce como rama, ya que tienen padre y
uno o varios hijos.
Árboles

En computación, usualmente se usa el término árbol para referirse a un
árbol con raíz. Mientras que se asume el término árbol libre para
referirse a la estructura más general.

Las aristas en un árbol no tienen dirección, usualmente se menciona que
se encuentran apuntando hacia la raíz o fuera de ella. Y usualmente se
coloca a la raíz en la cima del árbol.

Un árbol ordenado es un árbol con raíz en el cual el orden de los nodos
descendientes (hijos) sigue un patrón determinado

Si cada nodo debe tener un número determinado de hijos en un orden
específico, entonces tenemos un árbol de M-aristas. El árbol de M-aristas
más simple es el árbol binario.
Árboles: Definición General

Caso base: Un árbol con un solo nodo, el cual es a la vez la raíz del árbol
y una hoja.

Un árbol a partir de un nodo raíz R y k árboles A1, A2, A3,…, Ak con
raíces n1, n2, n3, …, nk respectivamente, y N1, N2, N3,…, Nk nodos cada
uno.

El árbol resultante de N = 1 + N1 + N2 + N3 +…+Nk nodos tiene como
raíz al nodo R, por lo que los nodos n1, n2, n3, …, nk son los hijos de R.

A cada uno de los árboles Ai se les denota como subárboles de la raíz.

Un recorrido es una sucesión de nodos del árbol de tal forma que entre
cada dos nodos consecutivos de la sucesión hay una relación de
parentesco.
Árboles: Definición General

Existen dos recorridos típicos para listar los nodos de un árbol: en
profundidad y en anchura.

En profundidad (depth-first) listamos los nodos expandiendo primero
el hijo actual de cada nodo hasta llegar a una hoja, al llegar a una hoja
regresamos al nodo anterior probando el siguiente hijo, y así
sucesivamente.

En anchura (breadth-first), antes de recorrer los nodos del nivel d+1
(profundidad de d+1 aristas desde la raíz), se listan todos los nodos del
nivel d.
Árboles: Ejemplos
Árboles Binarios

Un árbol binario es un conjunto finito de elementos que está vacío o
dividido en tres subconjuntos:
1. El primer subconjunto contiene un elemento único, la raíz del árbol,
2. Un subárbol binario izquierdo que puede o no estar vacío
3. Un subárbol binario derecho equivalente al izquierdo

En otras palabras, un árbol binario es un nodo externo, o un nodo
interno conectado a un par de árboles binarios, los subárboles izquierdo
y derecho.
raíz
izq
ancestro
der
descendiente
hoja
hermanos
Árboles Binarios

Nivel de un árbol binario: La raíz del árbol tiene el nivel 0, y el nivel de
cualquier otro nodo en el árbol es uno más el nivel de su padre.
Nivel = 0
Nivel = 1
Nivel = 2
Profundidad
Nivel = 3

Nivel = 0
1
nodos
2
4
Nivel = 1
Nivel = 2

d
2l nodos por nivel, por lo tanto la
Cantidad de nodos en un árbol de
Profundidad d es igual a la suma de
Los nodos por nivel:
N = 20 + 21 + … + 2d = ∑d 2j = 2d+1 - 1
j=0
Árbol binario completo: Es un árbol
binario que tiene todos sus nodos
completos en cada subárbol a una
profundidad d.
Si un árbol binario contiene m
nodos en el nivel l, entonces
contiene un máximo de 2m nodos
en el nivel l+1.
Árboles Binarios: Operaciones

Entre las aplicaciones más comunes tenemos:
◦ Dado un apuntador p a un nodo en un árbol binario
Null
info(p) : Retorna el contenido del
nodo, en este ejemplo es a
father(p) : Retorna un
apuntador al padre del nodo
a
left(p) : Retorna un apuntador
al hijo izquierdo del nodo b
d
isLeft(d) = true
p
c
e
right(p) : Retorna un apuntador
al hijo derecho del nodo
f
isLeft(e) = false
g
isRight(g) = true
brother(p) : Retorna un apuntador al hermano del nodo.
Note que si no existe un nodo que satisfaga cualquiera de las funciones anteriores, se
retorna un nulo (null) entonces.
Las funciones lógicas isLeft(p) y isRight(p) retornan true si p se encuentra en el
lado izquierdo o derecho de algún otro nodo respectivamente, false sino es el caso.
Árboles Binarios: Operaciones

Las funciones isLeft(p), isRight(p), y brother(p),
se implementan usando la funcionalidad de
left(p), right(p), y father(p). Ejemplo:
Bool isLeft(p)
q = father(p)
if(q == null)
return false;
if(left(q) == p)
return true;
return false;
isLeft(a) ?
a
isLeft(b) ? b
d
c
e
f
Implementa isRight(p)!
isLeft(c) ?
g
Árboles Binarios: Operaciones
brother(p)
if(father(p) == null)
return null;
d
if(isLeft(p))
return right(father(p))
return left(father(p))
father
a
c brother(c) ?
b
e
f
Operaciones adicionales:
-makeTree(p) : Crea un árbol binario con un nodo único (raíz)
- setLeft(p, x) : Establece un nodo x como hijo izquierdo de otro nodo p,
siempre y cuando p no tenga un hijo del lado izquierdo ya establecido.
- setRight(p, x) : Similar a la función anterior.
g
Árboles Binarios: Aplicación de Ejemplo



Los árboles binarios son útiles cuando se toman decisiones en dos
sentidos en cada punto del proceso.
Ejemplo: Encontrar todos los duplicados en una lista de números:
{15,4,8, 7, 4, 3, 19, 5, 7, 9, 16, 5,17}
Algoritmo: Primer elemento es la raíz, subsecuentes elementos se
colocan a la izquierda si son menores o a la derecha si son mayores.
Si son duplicados no se insertan pero se reportan.
15
15
4
15
4
15
4
4
8
8
7
15
4
3
8
7
Árboles Binarios: Aplicación de Ejemplo
{15,4,8, 7, 4, 3, 19, 5, 7, 9, 16, 5,17}
15
4
3
15
19
8
4
15
19
3
4
3
8
7
7
5
19
16
8
7
…
5
9
17
Árboles Binarios: Aplicación de Ejemplo
Pseudocódigo:
int numbers[13] = {15,4,8, 7, 4, 3, 19, 5, 7, 9, 16, 5,17};
tree = makeTree(numbers[0]);
for(int i=1;i<length(numbers);i++){
p = q = tree;
while(numbers[i] !=info(p) && q!=NULL){
p = q;
3
if(numbers[i]<info(p))
q = left(p);
else
q = right(p);
}
if(numbers[i] == info(p))
cout<<“Numero repetido”;
else if(numbers[i] < info(p))
setleft(p,numbers[i]);
else
setright(p, numbers[i]);
}
15
4
19
16
8
7
5
9
17
Ejemplo 2: Expresiones


La raíz del árbol binario contiene un operador que se aplicará a la
evaluación de las expresiones representadas por sus subárboles
izquierdo y derecho.
Los operandos son únicamente hojas en el árbol
+
$
A
*
+
A+B*C
B
*
C
A
+
*
C
*
B
+
C
A
C
(A+B*C)$((A+B)*C)
A
B
(A+B)*C
B
Representación básica de un árbol binario
struct tnode
int info;
struct tnode
struct tnode
struct tnode
};
{
* father; //No necesario
* left;
Info
* right;
typedef struct tnode * TNODEPTR;
TNODEPTR createNode() {
TNODEPTR p = (TNODEPTR)
malloc(sizeof(struct tnode));
return p;
}
void freeNode(TNODEPTR P) {
free( p);
}
L
F
R
p
Representación básica de un árbol binario
TNODEPTR makeTree(int x) {
TNODEPTR root = createNode();
root->info = x;
root->father = NULL;
root->left = NULL;
X
root->right = NULL;
return root;
}
TNODEPTR father(TNODEPTR pNode) {
return pNode->father;
}
TNODEPTR leftChild(TNODEPTR pNode)
{
return pNode->left;
}
TNODEPTR rightChild(TNODEPTR pNode)
{
return pNode->right;
}
NULL NULL NULL
Representación básica de un árbol binario
pNode
void setLeftChild(TNODEPTR pNode, int x) {
if (pNode == NULL)
cout << "Error, padre es nulo!" << endl;
else if (leftChild(pNode) != NULL)
cout << "Error, hijo izquierdo presente!“;
else {
pNode ->left = makeTree(x);
pNode ->left ->father = pNode;
}
}
pNode
pNode
Y N N N
X N N N
Y
N N
Y
N N
makeTree(x);
X N N N
X N
N
pNode->left=…
pNode ->left ->father = pNode;
void setRightChild(TNODEPTR pNode, int x){…} //Es similar
Representación básica de un árbol binario
bool isLeft(TNODEPTR pNode) {
if (pNode == NULL)
return false;
else if (father(pNode) == NULL)
return false;
else
return (leftChild(father(pNode)) == pNode);
}
bool isRight(TNODEPTR pNode) {
if (pNode == NULL)
return false;
else if (father(pNode) == NULL)
return false;
return (rightChild(father(pNode)) == pNode);
}
Representación básica de un árbol binario
TNODEPTR sibling(TNODEPTR pNode) {
if (pNode == NULL)
return NULL;
if (father(pNode) == NULL)
return NULL;
if (isLeft(pNode))
return rightChild(father(pNode));
else
return leftChild(father(pNode));
}
father
a
c sibling(c) ?
b
d
e
f
g
Árbol binario de búsqueda u ordenado

El ejemplo anterior introdujo el árbol binario de búsqueda o
árbol binario ordenado

Este tipo de árbol tiene todos sus nodos en orden, para cada
nodo X:
◦ Todos los elementos de su árbol izquierdo son menores o iguales a X,
◦ Mientras los nodos en su árbol derecho son mayores a X.

En promedio, un árbol binario ordenado puede localizar un
nodo en un árbol de N nodos en tiempo log(N).
Búsqueda en un árbol binario ordenado
//Dado un árbol binario, retorna
4
//verdadero si el dato buscado se
//encuentra en el árbol, o falso si no
bool find(TNODEPTR pNode, int data){
3
//Caso base:arbol vacio
8
if(pNode==NULL){
return false;
} else{
7
//Dato es encontrado
if(pNode->info==data){
return true;
5
}else{
if(data<pNode->info){
//Recursa a la izq si es menor
return find(pNode->left,data);
} else{
//Recursa a la derecha si es mayor
return find(pNode->right,data);
}
}
}
}
15
19
16
9
17
Inserción en un árbol binario ordenado
15
4
//Dado un árbol binario, inserta un
//nuevo nodo en el lugar correcto del arbol.
TNODEPTR insert(TNODEPTR pNode, int data){
3
8
//1: Si el arbol esta vacio retorna
//un nodo unico
if(pNode==NULL){
1
9
7
return makeTree(data);
} else{
//Recursa hacia abajo del arbol
//Para encontrar el lugar correcto
5
if(data<=pNode->info){
pNode->left = insert(pNode->left, data);
}else{
pNode->right = insert(pNode->right, data);
}
//Retorna el nodo original sin cambiar
return(pNode);
}
}
19
16
17
Árbol binarios: Ejercicio simple

Escribe código que implemente el siguiente árbol binario:
Llamando a makeTree tres veces
y usando tres variables puntero.
a)
2
1
TNODEPTR build123(){
TNODEPTR one, two three;
one = makeTree(1);
two = makeTree(2);
three = makeTree(3);
two->left = one;
two->right = three;
return two
}
3
Llamando a makeTree tres veces
y usando una variable puntero.
b)
TNODEPTR build123(){
TNODEPTR two;
two = makeTree(2);
two->left = makeTree(1);
two->right = makeTree(3);
return two
}
Llamando a insert tres veces,
pasándole la raíz del árbol.
b)
TNODEPTR build123(){
TNODEPTR root=NULL;
root = insert(root,2);
root = insert(root,1);
root = insert(root,3);
return root;
}
Árbol binarios: Ejercicio simple

Implementa la función size que calcula el número de
nodos en un árbol binario.
int size(TNODEPTR pNode){
if(pNode==NULL){
return 0;
}else{
return (size(pNode->left)+
1 +
size(pNode->right));
}
}

Dado un árbol binario ordenado no nulo, implementa
una función que retorne el valor mínimo en el árbol
int minimum(TNODEPTR pNode){
TNODEPTR current = pNode;
while(current->left!=NULL)
current = current->left
}
return current->info;
}
Recorrido de árboles binarios


Recorrer un árbol binario significa visitar la raíz y recorrer sus
subárboles izquierdo y derecho de forma recursiva.
Orden previo:
1. Visitar la raíz
2. Recorrer el subárbol izquierdo en orden previo
3. Recorrer el subárbol derecho en orden previo
A
1
2
3
B
C
5
6
D
4
void recorridoPreorden(TNODEPTR pNode){
if(pNode!=NULL){
cout<<"Node: "<<pNode->info;
recorridoPreorden(pNode->left);
recorridoPreorden(pNode->right);
}
}
H
G
7
E
F
I
8
9
ABDGCEHIF
Recorrido de árboles binarios

Orden Simétrico/Inorden:
1. Recorrer el subárbol izquierdo en orden simétrico
2. Recorrer la raíz
3. Recorrer el subárbol derecho en orden simétrico
A
4
3
1
B
6
D
2
C
8
H
G
5
E
void recorridoInorden(TNODEPTR pNode){
if(pNode!=NULL){
recorridoPreorden(pNode->left);
cout<<"Node: "<<pNode->info;
recorridoPreorden(pNode->right);
}
}
F
I
7
9
DGBAHEICF
Recorrido de árboles binarios

Orden Posterior:
1. Recorrer el subárbol izquierdo en orden posterior
2. Recorrer el subárbol derecho en orden posterior
3. Recorrer la raíz
A
9
3
2
B
C
8
6
D
1
void recorridoPostorden(TNODEPTR pNode){
if(pNode!=NULL){
recorridoPreorden(pNode->left);
recorridoPreorden(pNode->right);
cout<<"Node: "<<pNode->info;
}
}
H
G
4
E
F
I
5
7
GDBHIEFCA
Remoción en un árbol binario ordenado
15

15
Se presentan tres casos:
◦ El nodo a suprimir no tiene hijos: Se elimina el
nodo del árbol sin mayores ajustes
4
3
19
4
16
8
19
15
◦ Si el nodo a suprimir sólo tiene un subárbol: Su
único hijo se mueve hacia arriba y ocupa su lugar
16
8
15
4
19
8
19
16
8
16
15
◦ El nodo a suprimir tiene dos subárboles: Su
sucesor de orden intermedio S (o
antecesor) debe ocupar su lugar. El sucesor
intermedio es el nodo hijo más a la izquierda en
su árbol derecho. Dicho nodo no puede tener
un subárbol izquierdo. El antecesor sería el nodo
hijo más a la derecha de su árbol izquierdo.
4
3
23
19
8
16
25
18
23
24
24
Remoción en un árbol binario ordenado
void deleteNode(TNODEPTR tree, int x)
{
TNODEPTR p = tree, q = NULL, rp;
15
15
4
19
while (p != NULL && p->info != x) {
4
19
q = p;
3
16
8
15
}
if (p == NULL) return;
16
8
p = (x < p->info) ? p->left :
p-> right;
15
4
19
8
19
if (p->left == NULL)
rp = p-> right;
else if (p-> right == NULL)
16
8
16
rp = p->left;
15
else {
4
23
19
TNODEPTR f = p;
rp = p-> right;
3
8
16
25
TNODEPTR s = rp->left;
while (s != NULL) {
18
23
24
f = rp;
rp = s;
s = rp->left;
24
Árboles Balanceados

La altura (profundidad) de un árbol binario es el nivel
máximo de sus hojas

Un árbol binario balanceado o árbol AVL es aquel en el
que las alturas de los dos subárboles de cada nodo nunca
difieren en más de 1.

El balance de un nodo en un árbol binario se define como
la altura de su subárbol izquierdo menos la altura de su
subárbol derecho.

Por lo tanto, cada nodo en un árbol AVL tiene un balance
de 1, -1 o 0, dependiendo de si la altura de su subárbol
izquierdo es mayor que, menor que o igual a la altura del
derecho.
Árboles Balanceados
-1
0
1
0
0
0
-1
1
0
0
0
0
0
0
0
0
Factor de Equilibrio (FE): Cada nodo en un árbol AVL tiene un balance de 1, -1 o
0, dependiendo de si la altura de su subárbol izquierdo es mayor que, menor que
o igual a la altura del derecho.
Si el FE>=2, es necesario reequilibrar el árbol.
0
Árbol AVL

Debido a que los árboles están balanceados, la
complejidad de búsqueda de un elemento es del orden
O(log n).

Las operaciones en un árbol AVL balanceado son las
mismas que en un árbol binario de búsqueda
desequilibrado, pero si al insertar o borrar elementos
el árbol pierde su balance entonces se rotan los nodos
para equilibrar de nuevo el árbol.

El propósito de la rotación es que el recorrido de
orden intermedio del árbol rotado sea el mismo que
para el árbol original (es decir, el árbol rotado sigue
siendo un árbol de búsqueda binaria).
Árbol AVL: Representación
Cada nodo debe contener, además de los datos, su factor
de equilibrio y los punteros hacia sus hijos.
Por ejemplo:
P = {data=10, left=7, right=15, FE=2}
p
10
7
5
2
15
8
6
Árbol AVL: Rotaciones
7
5
2
2,5,6,7,8,10,15
10
6
8
15
10
5
7
2
15
7
6
5
2,5,6,7,8,10,15
10
8
Recorrido Inorder
8
Rotación derecha
15
2
6
Rotación izquierda
Algoritmo de Rotación Izquierda
p
7
10
p
r
l
5
6
r’
7
15
l
10
5
lr’
2
r
q = right(p);
temp = left(q);
left(q) = p;
right(p) = temp
8
lr’
r’
8
15
2
6
Rotación izquierda
Dado un árbol de raíz p, y de hijo izquierdo l y derecho r, se forma un nuevo
árbol cuya raíz sea la raíz del hijo del lado derecho (es decir r), y como su hijo
derecho le colocamos el hijo derecho que tenía anteriormente (es decir r’).
Del lado izquierdo de la nueva raíz r, colocamos a la raíz anterior p, teniendo
como raíz de su subárbol derecho el hijo izquierdo lr’ de la nueva raíz r’.
Rotaciones Dobles
r
12
r’
p
Si la inserción se produce en el hijo derecho (lr’) del
hijo izquierdo (p) del nodo desequilibrado (r) o
viceversa , se realizará una doble rotación.
7
15
l
5
Rotación Doble a la Derecha: Primero es
una rotación simple a la izquierda, y luego
rotación simple a la derecha.
9
2
6
8
10
12
Rotación a
la izquierda
9
15
Rotación a
la derecha
9
7
7
12
10
5
2
lr’
6
8
5
8
2
6
10
15
Casos de Inserción

La inserción funciona como si fuera un árbol de búsqueda
binario desequilibrado, retrocediendo hacia la raíz y rotando
sobre cualquier nodo no balanceado.
Nuevo nodo
Caso 1: Izquierda
* Imágenes tomadas de Wikimedia bajo licencia de documentación libre GNU
Solución: Rotación Derecha
Casos de Inserción

Caso 2: Derecha
Nuevo nodo
* Imágenes tomadas de Wikimedia bajo licencia de documentación libre GNU
Solución: Rotación Izquierda
Casos de Inserción

Caso 3: Izquierda-Derecha
Solución: Rotación doble
Rotación Izquierda
* Imágenes tomadas de Wikimedia bajo licencia de documentación libre GNU
Rotación Derecha
Casos de Inserción

Caso 4: Derecha-Izquierda
Solución: Rotación doble
Rotación Derecha
* Imágenes tomadas de Wikimedia bajo licencia de documentación libre GNU
Rotación Izquierda
Árboles Multicaminos


Un árbol multi-camino o multi-direccional de
orden n, es un árbol general en el cual cada nodo
tiene n o menos subárboles, y contiene una llave
(key) menos que subárboles.
Sea A un árbol de n-caminos si y solo si:
I.
II.
A está vacío
A puede tener hasta n subárboles S0, S1, S2, …, Sn-1 en
cada nodo
III. Dado n subárboles para un nodo p de A; p tiene Kn-2
llaves en orden. Es decir, cada nodo contiene una llave
menos que subárboles
IV. Todas las llaves en el subárbol S0 son menores que o
iguales a K0, mientras todas las llaves en los subárboles
Sj (1<j<n-2) son mayores que Kj-1.
V. Todas las llaves en el subárbol Sn-1 son mayores que las
llaves kn-2.
Árboles Multicaminos: Nodos
Nodo A
Cantidad variable de apuntadores
S0
K0
…
Cantidad variable de llaves
Kj-1
Sj
Kj
…
Kn-2
Sn-1
X
X
X
X < K0
Kj-1 < X < Kj
X > Kn-2
Árboles Multicaminos: Ejemplos
Árbol multicamino de orden 4.
Máxima cantidad de llaves es 3
A
12
B
6
50
85
C
10
D
60
37
F
E
70
80
62
65
120
H
G
25
100
69
110
150
Árboles Multicaminos: Operaciones Básicas

numTrees(p): Dado un nodo multicamino p, retorna el número de hijos
(subárboles) de p (0<=numTrees(p)<=n). Donde n es el orden o grado del árbol.

child(p,i): Retorna el i_ésimo hijo del nodo p. Donde 0<=i<numTrees(p)-1.

key(p,j): Retorna la j_ésima llave del nodo p. Donde 0<=j<numTrees(p)-2 son las
llaves en orden ascendente
numTrees(A) => 4
A
key(A,0)
12
50
key(A,2)
85
child(A,3)
child(A,0)
B
6
C
10
37
D
60
E
70
80
100
120
150
Árboles Multicaminos: Operaciones Básicas
child(p,i) para
1<=i<=numTrees(p)-2, contiene
todas las llaves en el árbol
entre key(p, i-1) y key(p,i).
child(p,0) apunta a un
subárbol cuyas llaves son
todas menores que la llave
key(p,0).
12
B
6
A
key(A,0)
C
10
child(A,0): Las
llaves de este
nodo {6,10} < 12
37
50
key(A,2)
85
child(p, numTrees(p)-1) apunta
a un subárbol que contiene
únicamente llaves mayores a
key(p, numTrees(p)-2).
D
60
E
70
80
100
120
150
child(A,3): Las
llaves de este nodo:
{100,120, 150} > 85
Árboles Multicaminos: Operaciones Básicas

Recorrido: Impresión de llaves en orden
ascendente.
traverse(T node){
if(node != NULL){
nt = 4
nt = numTrees(node);
0<=i<3
for(i = 0; i<nt-1; i++){
traverse(son(node,i));
key(A,0), Key(A,1), Key(A,2)
cout<<key(node, i);
A
}
12
50 85
traverse(son(node,nt-1));
}
son(A,0)
son(A,1)
son(A,2)
son(A,3)
}
B
C
D
E
6
10
37
60
70
80
100
120
150
Árboles Multicaminos: Operaciones Básicas

Acceso secuencial directo: Accede a la siguiente llave partiendo de
otra que se le conoce su posición en el árbol. Asumimos que la llave
que conocemos se encuentra en Key(node, index)
next(T node, int index){
p = son(node, index+1);
q = null;
while(p != NULL){
q = p;
p = son(p,0);
}
if (q!=NULL)
return key(q,0);
if(index < numTrees(node)-2)
return key(node, index+1);
return (NULL);
}
succesor(T node, int index){
p = son(node, index+1);
if(p!=NULL && index<numTrees(node)-2)
return (next(p,index));
f = father(node);
i = index(node);
while(f != NULL&& i==numTrees(f) -1){
i = index(f);
f = father(f);
}
if (f==NULL)
return (NULL);
return (key(f,i));
}