que es el arbol de toji ?
Actualización:
no, es un mezquite que se llama toji pero quiero saber sus propiedades curativas
More Questions From This User See All
no, es un mezquite que se llama toji pero quiero saber sus propiedades curativas
Copyright © 2024 Q2A.MX - All rights reserved.
Answers & Comments
Verified answer
bueno yo solo entre a leer las respuestas
saludos
El toji es una planta paracita que crese en didtintos arboles como mezquite. Acasia. Palo fierro. Usada en la tribu mayo como planta medivinal. Es endemica de el sur de sonora y norte de sinaloa
Son unas bolas del las mismas ramas tiernas del mezquite q se dan en el monte,sirven para la diabetes ,empacho y diarrea,hay toji de palo verde y palofierro,aquí en Sonora
MAS BIEN CREO QUE SE TRATA DE ARBOL ROJI:
QUIZAS ESO QUISISTES PREGUNTAR?
Definición; FLa altura negra de un nodo x, an(x), es el número de, nodos negros que hay en cualquier camino de él a una hoja que desciende de él.FLa altura negra de un árbol es la altura negra de su raíz.
Sea A un árbol rojinegro con n nodos internos
ßSi x es un nodo en A, entonces, el subárbol con raíz
en x tiene a al menos 2an(x)-1 nodos internos.
FSea x un nodo en A, por inducción sobre an(x)
ßA) Si an(x) = 0, entonces, x es hoja y no hay nodos
en el subárbol con raíz en él.
ßPor otro lado, 2an(x)-1 = 0.
Análisis y Diseño de Algoritmos RedBlackTree-6
Observación
FB) Supongamos que an(x) > 0, x es interno y
tiene dos hijos. Es inmediato que cualquier hijo y
de x cumple con lo siguiente:
C(y) = rojo, entonces, an(y) = an(x)
C(y) = negro, entonces, an(y) = an(x) – 1
FPor hipótesis de inducción, el número de nodos
descendientes de x es al menos:
No descendientes( dere(x) ) + 1 + No_descendientes(
izq( x ) ) = 1 + 2(2an(x)-1 - 1) = 2an(x) -1
Análisis y Complejidad de Algoritmos 4
Análisis y Diseño de Algoritmos RedBlackTree-7
Observación
FLa altura de A es a lo sumo 2log2(n +1).
FSea h la altura del árbol rojinegro.
ßAl menos la mitad de los nodos en un camino de la
raíz a una hoja , sin incluir la raíz, deben ser negros.
ßLa altura negra del árbol debe ser al menos h/2
ßPor lo anterior,
ßn = 2h/2 – 1 Y log2(n +1) = h/2 Y h = log2(n +1)
Análisis y Diseño de Algoritmos RedBlackTree-8
Observaciones
FLos árboles rojinegros son árboles de búsqueda binaria
en donde las hojas tienen valores nulos.
FLos algoritmos para árboles de búsqueda binaria se
aplican a los árboles rojinegros.
ßAl insertar una nueva llave quedará como padre de dos hojas
nulas.
FLa operación de búsqueda toma un tiempo O(log n) en
el peor caso.
FLas operaciones de Inserción y Supresión son
también O(log n) pero no necesariamente mantienen
estructuras rojinegras.
Arturo Díaz Pérez
Análisis y Complejidad de Algoritmos 5
Análisis y Diseño de Algoritmos RedBlackTree-9
Rotaciones
y
x
a b
g
x
y
b g
a
Right_Rotate( T, x )
Left_Rotate( T, x )
Análisis y Diseño de Algoritmos RedBlackTree-10
LeftRotate
LeftRotate(A; x)
{ y:=right(x);
right(x):=left(y);
if left(y) ? nil then
p(left(y)) := x;
p(y) := p(x);
if p(x) = nil then
root(A) := y
else
if x := left(p(x)) then
left(p(x)) := y
else
right(p(x)) := y;
left(y) := x; p(x) := y }
y
x
a b
g
x
y
b g
a
Análisis y Complejidad de Algoritmos 6
Análisis y Diseño de Algoritmos RedBlackTree-11
RightRotate
RighRotate(A; y)
{ x :=left(y);
left(y):= right(x);
if right(y) ? nil then
p(right(x)) := y;
p(x) := p(y);
if p(y) = nil then
root(A) := x
else
if y := right(p(y)) then
right(p(y)) := x
else
left(p(y)) := x;
right(x) := y; p(y) := x }
y
x
a b
g
x
y
b g
a
Análisis y Diseño de Algoritmos RedBlackTree-12
Recorrido EntreOrden
RecorridoEntreOrden( x )
begin
if x <> nil then begin
RecorridoEntreOrden( left[x] );
writeln( x );
RecorridoEntreOrden( right[x] )
end
end;
Arturo Díaz Pérez
Análisis y Complejidad de Algoritmos 7
Análisis y Diseño de Algoritmos RedBlackTree-13
Recorrido PreOrden
RecorridoPreOrden( x )
begin
if x <> nil then begin
writeln( x );
RecorridoPreOrden( left[x] );
RecorridoPreOrden( right[x] )
end
end;
Análisis y Diseño de Algoritmos RedBlackTree-14
Recorrido PosOrden
RecorridoPosOrden( x )
begin
if x <> nil then begin
RecorridoPosOrden( left[x] );
RecorridoPosOrden( right[x] )
writeln( x );
end
end;
Análisis y Complejidad de Algoritmos 8
Análisis y Diseño de Algoritmos RedBlackTree-15
Recorrido EntreOrden
FLas rotaciones izquierda y derecha preservan
entreórdenes. Esto es, si A es el recorrido entreorden, x
está antes que y en A y B es el recorrido entreorden
después de aplicar una rotación en x, entonces, x está
antes que y en B.
ßEn efecto, consideremos situación derecha de la figura y una
rotación izquierda sobre y.
ßSe tiene a = x = b = y = g.
ßDespués de aplicar la rotación a la izquierda el orden se
preserva.
Análisis y Diseño de Algoritmos RedBlackTree-16
Inserción
FAl insertar nuevos elementos en árboles rojinegros, en
tiempo O(log n), se debe garantizar que el árbol
resultante continúe siendo rojinegro
FEn los árboles rojinegros las hojas son vacías y negras
FLos nuevos elementos se colocan como padres de hojas
FCada nuevo elemento se coloca como una estructura
del árbol binario
FComo las hojas deben ser negras, el nodo que contiene
la llave a insertarse se colorea como rojo
ßNo se aumenta la altura negra del árbol
FLa única propiedad que puede violarse es la referente al
color del padre del nodo que se ha insertado
Análisis y Complejidad de Algoritmos 9
Análisis y Diseño de Algoritmos RedBlackTree-17
InserciónRN
InserciónRN( A; x )
{ InserciónABB( A; x );
C(x) := red;
p := p(x);
while x ? root(A) ^ C(p) = red do {
if p = left (p(p(x)) then {
u := right(p(p(x));
if C(u) = red then {
1) C(p) := C(u) := black;
C(p(p(x)) := red;
x:= p(p(x)); p := p(x)
} else {
. . .
Análisis y Diseño de Algoritmos RedBlackTree-18
InserciónRN (cont.)
. . .
if x = right(p) then {
2) x := p;
LeftRotate( A; x ); p := p(x)
};
3) C(p(x)) := black;
C(p(p(x)) := red;
RightRotate( A; p(p(x)) )
}
} else {
(código simétrico intercambiando “left” y “right” )
};
};
C(root(A)) := black
Si x rojo y ambos padre y tío rojo, repintamos a estos últimos de negro y al
padre de ambos de rojo. Como A es RN, ese abuelo era negro. Al hacer los
cambios, alturas negras no se modifican. Trasladamos la dificultad en x, a su
abuelo padre(padre) y reiteramos ciclo principal.
Análisis y Complejidad de Algoritmos 11
Análisis y Diseño de Algoritmos RedBlackTree-21
InserciónRN( A, x ): Casos 2 y 3
La rotación izquierda sobre padre reduce el caso al de 3). No se
afecta a las alturas negras.
FCaso 3: x y padre rojo mas tío es negro y, x es hijo
izquierdo de padre
ßRepintar a padre negro, al abuelo rojo y rotación derecha sobre
el abuelo.
ßLas alturas negras no se modifican y la posición del abuelo
quedaría negra, con ambos hijos rojo.
ßEl ciclo principal no se repetirá más.
Análisis y Complejidad de Algoritmos 14
Análisis y Diseño de Algoritmos RedBlackTree-27
Supresión
FCoincide con la operación de supresión en los árboles
de búsqueda binaria
FSin embargo, es necesario mantener la estructura de los
árboles rojinegros
FPara evitar repeticiones se introduce vigía, nil(A), el cual
representa las hojas del árbol rojinegro
FSi el nodo suprimido y fuese rojo, entonces, las alturas
negras no cambian y, en tal caso, termina
FSi el nodo suprimido y fuese negro, entonces, las ramas
que pasen por y tienen un nodo negro menos, lo que
viola la condición de los árboles rojinegros. En este
caso es necesario ajustar colores.
Análisis y Diseño de Algoritmos RedBlackTree-28
el mejor caso?
Dime dònde lo has escuchado o visto. Paìs, Regiòn, Area, Coordenadas geogràficas. Asì te puedo ayudar!