Normalización es un conjunto de reglas que sirven para ayudar a los diseñadores a desarrollar un esquema que minimice los problemas de lógica. Cada regla está basada en la que le antecede. La normalización se adoptó porque el viejo estilo de poner todos los datos en un solo lugar, como un archivo o una tabla de la base de datos, era ineficiente y conducía a errores de lógica cuando se trataba de manipular los datos. Por ejemplo, vea la base de datos MiTienda. Si almacena todos los datos en la tabla Clientes, ésta podría verse como se muestra a continuación:
Clientes
ID_Cliente Nombre
Apellidos
Nombre_Producto1 Costo_Producto1
Imagen_Producto1 Nombre_Producto2 Costo_Producto2
Imagen_Producto2 Fecha_Pedido
Cantidad_Pedido
Nombre_Cia_Envios
La tabla se ha descrito de manera abreviada pero aun así representa la idea general.
¿Cómo podría añadir un nuevo cliente en su tabla Clientes? Debería añadir un producto y un pedido también. ¿Qué tal si quisiera emitir un informe de todos los productos que vende? No podría separar fácilmente los productos de los clientes con una simple instrucción SQL. Lo bello de las bases de datos relacionales, si están bien diseñadas, es que puede hacer esto fácilmente.
La nomlalización también hace las cosas fáciles de entender. Los seres humanos tenemos la tendencia de simplificar las cosas al máximo. Lo hacemos con casi todo desde los animales hasta con los automóviles. Vemos una imagen de gran tamaño y la hacemos menos compleja agrupando cosas similares juntas. Las guías que la nomlalización provee crean el marco de referencia para simplificar la estructura. En su base de datos de muestra es fácil detectar que usted tiene tres diferentes grupos: clientes, productos y pedidos. Si sigue las guías de la nomlalización, podría crear las tablas basándose en estos grupos.
El proceso de nomlalización tiene un nombre y una serie de reglas para cada fase. Esto puede parecer un poco confuso al principio, pero poco a poco irá entendiendo el proceso, así como las razones para hacerlo de esta manera. A la mayoría de la gente le encantan las hojas de cálculo por la forma en la que manejan sus datos. El tiempo que le lleve reconfigurar su esquema para ajustarlo al proceso de nomlalización, siempre será bien Iinvertido. Al fin y al cabo, esto le tomará menos tiempo que el que tendría que invertir , para cortar y pegar sus columnas de datos para generar el infomle que quiere su jefe.
Otra ventaja de la nomlalización de su base de datos es el consumo de espacio. Una base de datos nomlalizada puede ocupar menos espacio en disco que una no nomlalizada. Hay menos repetición de datos, lo que tiene como consecuencia un mucho menor uso de espacio en disco.
Grados de normalización
Existen básicamente tres niveles de normalización: Primera Fomla Normal (1NF), Segunda Fomla Normal (2NF) y Tercera Fomla Normal (3NF). Cada una de estas formas tiene sus propias reglas. Cuando una base de datos se conforma a un nivel, se considera nomlalizada a esa forma de nomlalización. Por ejemplo, supongamos que su
base de datos cumple con todas las reglas del segundo nivel de nomlalización. Se considera que está en la Segunda Fomla Normal. No siempre es una buena idea tener una base de datos conformada en el nivel más alto de normalización. Puede llevar aun nivel de complejidad que pudiera ser evitado si estuviera en un nivel más bajo de normalización.
Primera Forma Normal
La regla de la Primera Forma Normal establece que las columnas repetidas deben eliminarse y colocarse en tablas separadas. Ésta es una regla muy fácil de seguir. Observe el esquema de la tabla Clientes de la base de datos.
.
Clientes
ID Cliente
Nombre
Apellidos
Nombre_Producto1
Costo_Producto1
Imagen_Producto1
Nombre_Producto2
Costo_Producto2
Imagen_Producto2
Fecha_Pedido
Cantidad_Pedido
Nombre Cia Envios
–
La tabla tiene varias columnas repetidas. Éstas se refieren principalmente a los productos. De acuerdo con la regla, debe eliminar las columnas repetidas y crearles su propia tabla.
Eliminación de datos repetidos en una base de datos
Clientes Pedidos
ID_Clientes Nombre_Productos
Nombre Costo_Producto
Apellidos Imagen_Producto
Direccion
Numero_Pedido
Fecha_Pedido
Cantidad_Pedido
Clave_Cia_Envios
Nombre_Ci_ Envios
–
Ahora tiene dos tablas. Pero todavía hay un problema. No hay forma de relacionar los datos de la tabla original con los de la nueva tabla. Para hacerlo, debe añadir un campo clave a la segunda tabla de forma que se establezca la relación. Añada a la tabla Productos una clave primaria que se llame ID_Producto y añada una clave a la tabla Clientes que la relacione con la tabla Productos. El campo ID_Producto es el candidato ideal.
Primera Forma Normal
Clientes Pedidos
ID_Productos ID_Productos
ID_Clientes Nombre_Productos
Nombre Costo_Producto
Apellidos Imagen_Producto
Direccion
Numero_Pedido
Fecha_Pedido
Cantidad_Pedido
Clave_Cia_Envios
–
Así, se ha establecido una relación uno a varios. Ésta representa lo que la base de datos estará haciendo en la vida real. El cliente tendrá muchos productos que podrá comprar,
sin importar cuántos otros clientes quieran comprarlos también. Además, el cliente necesitará haber pedido un producto para ser un cliente. Usted ya no está obligado a añadir
un cliente cada vez que añade un nuevo producto a su inventario.
Poner la base de datos en la Primera Forma Normal resuelve el problema de los encabezados de columna múltiples. Muy a menudo, los diseñadores de bases de datos inexpertos harán algo similar a la tabla no normalizada. Una y otra vez, crearán columnas que representen los mismos datos. En una empresa de servicios de electricidad, había una base de datos para el control de refacciones de una planta nuclear. La tabla de su base de datos, la cual contenía los números de parte de las refacciones, tenía una columna repetida más de treinta veces. Cada vez que una nueva parte se tenía que dar de alta, se creaba una nueva columna para almacenar la información. Obviamente, el diseño de la base de datos era bastante pobre y, por lo mismo, resultaba una pesadilla para sus programadores/administradores.
La normalización ayuda a clarificar la base de datos ya organizarla en partes más pequeñas y más fáciles de entender. En lugar de tener que entender una tabla gigantesca y monolítica que tiene muchos diferentes aspectos, usted sólo tiene que entender objetos pequeños y más tangibles, así como las relaciones que guardan con otros objetos también pequeños. No es necesario mencionar que un mejor entendimiento del funcionamiento de su base de datos conducirá aun mejor aprovechamiento de sus activos.
Segunda Forma Normal
La regla de la Segunda Forma Normal establece que todas las dependencias parciales se deben eliminar y separar dentro de sus propias tablas. Una depen dencia parcial es un término que describe a aquellos datos que no dependen de la clave de la tabla para identificarlos. En la base de datos de muestra, la información de pedidos está en cada uno de los registros. Sería mucho más simple utilizar únicamente el número del pedido. El resto de la información podría residir en su propia tabla. Una vez que haya organizado la información de pedidos.
Eliminación de las dependencias parciales -Segunda Forma Normal
Clientes Pedidos Productos
ID_Productos ID_Productos ID_Producto
ID_Clientes Nombre_Productos Fecha_Compra
Nombre Cantidad_Pedido Costos_Productos
Apellidos Imagen_Producto
Direccion
Numero_Pedido
Nombre_Cia_Envios
De nuevo, al organizar el esquema de esta forma puede reflejar el mundo real en su base de datos. Tendría que hacer algunos cambios en sus reglas del negocio para que esto fuera aplicable, pero para ilustrar la normalización, así está bien.
Una de las mayores desventajas de la normalización es el tiempo que lleva hacerlo. La mayoría de la gente está demasiado ocupada, y emplear tiempo para asegurarse de que sus datos están normalizados cuando todo funciona más o menos bien, parece ser un desperdicio de tiempo. Pero no es así. Usted tendrá que emplear más tiempo arreglando una base de datos no normalizada que el que emplearía en una normalizada.
Al haber alcanzado la Segunda Forma Normal, usted puede disfrutar de algunas de las ventajas de las bases de datos relacionales. Por ejemplo, puede añadir nuevas columnas a la tabla Clientes sin afectar a las tablas Productos y Pedidos. Lo mismo aplica para las otras tablas. Alcanzar este nivel de normalización permite que los datos se acomoden de una manera natural dentro de los límites esperados.
Una vez que ha alcanzado el nivel de la Segunda Forma Normal, se han controlado la mayoría de los problemas de lógica. Puede insertar un registro sin un exceso de datos en la mayoría de las tablas. Observando un poco más de cerca la tabla Clientes, vemos la columna Nombre_Cia_Envios. Ésta no es dependiente del cliente. El siguiente nivel de normalización explicará cómo solucionar esto.
Tercera Forma Normal
La regla de la Tercera Forma Normal señala que hay que eliminar y separar cualquier dato que no sea clave. El valor de esta columna debe depender de la clave. Todos los valores deben identificarse únicamente por la clave. En la base de datos de muestra, la tabla Clientes contiene la columna Nombre_Cia_Envios, la cual no se identifica únicamente por la clave. Podría separar estos datos de la tabla y ponerlos en una tabla aparte.
Eliminación de los datos que no son claves para la Tercera Forma Normal
Clientes Productos PedidoMaestro PedidoDetallado Cias_Envios
ID_cliente ID_Producto ID_Pedido ID_PedidoDetallado ID_Cia_Envios
ID_Producto Nombre_Producto Fecha_Pedido ID_Pedido Nombre_Cia_Envios.
Numero_Pedido Costos_Productos Cantidad_Pedidos Fecha_Pedido
ID_Cia_Envios Foto_Producto Cantidad_Pedido
Nombre
Apellidos
Direccion
Ahora todas sus tablas están en la Tercera Forma Normal. Esto le da más flexibilidad y previene errores de lógica cuando inserta o borra registros. Cada columna en la tabla está identificada de manera única por la clave, y no hay datos repetidos. Esto provee un esquema limpio y elegante, que es fácil de trabajar y expandir.
Qué tan lejos debe llevar la normalización
La siguiente decisión es ¿qué tan lejos debe llevar la normalización? La normalización es una ciencia subjetiva. Determinar las necesidades de simplificación depende de usted. Si su base de datos va a proveer información aun solo usuario para un propósito simple y existen pocas posibilidades de expansión, normalizar sus datos hasta la 3FN sea quizá algo extremoso. Las reglas de normalización existen como guías para crear tablas que sean fáciles de manejar, así como flexibles y eficientes.
A veces puede ocurrir que normalizar sus datos hasta el nivel más alto no tenga sentido. Por ejemplo, suponga que añade una columna extra para la dirección en su base de datos. Es muy normal tener dos líneas para la dirección. El esquema de la tabla podría verse como se muestra a continuación:
ID_Cliente
Nombre
Apellidos
Direccion1
Direccion2
De acuerdo con las reglas, si aplica la Primera Forma Normal, la columna de dirección debería sacarse de esta tabla y reemplazarse con la clave de una nueva tabla. El resultado de este esquema se muestra a continuación:
ID_Ciente ID_Direccion
Nombre ID_Cliente
Apellidos Direccion
La base de datos ahora cumple con la Primera Forma Normal. Los clientes pueden tener más de una dirección. El problema aquí es que usted ha complicado demasiado una idea simple, por tratar de seguir las reglas de normalización. En el ejemplo mostrado, la segunda dirección es totalmente opcional. Está ahí sólo para colectar información que pudiera utilizarse como información de contacto. No hay necesidad de partir la tabla en dos y forzar las reglas de la normalización. En esta instancia, el exceso de normalización frustra el propósito para el que se utilizan los datos. Añade, de manera innecesaria, un nivel más de complejidad. Una buena forma de determinar si está llevando demasiado lejos su normalización, es ver el número de tablas que tiene. Un número grande de tablas pudiera indicar que está normalizando demasiado. Observe su esquema.
¿Está dividiendo tablas sólo para seguir las reglas o estas divisiones son en verdad prácticas? Éstas son el tipo de cosas que usted, el diseñador de la base de datos, necesita decidir. La experiencia y el sentido común lo pueden auxiliar para tomar la decisión correcta. La normalización no es una ciencia exacta. Es subjetiva.
Existen seis niveles más de normalización que no se han discutido aquí. Ellos son Forma Normal Boyce-Codd, Cuarta Forma Normal (4NF), Quinta Forma Normal (5NF) o
Forma Normal de Proyección-Unión, Forma Normal de Proyección-Unión Fuerte, Forma Normal de Proyección-Unión Extra Fuerte y Forma Normal de Clave de Dominio. Estas formas de normalización pueden llevar las cosas más allá de lo que necesita. Éstas existen para hacer una base de datos realmente relacional. Tienen que ver principalmente con dependencias múltiples y claves relacionales.
En resumen
La normalización es una técnica que se utiliza para crear relaciones lógicas apropiadas entre tablas de una base de datos.
Ayuda a prevenir errores lógicos en la manipulación de datos. La normalización facilita también agregar nuevas columnas sin romper el esquema actual ni las relaciones.
Existen varios niveles de normalización: Primera Forma Normal, Segunda Forma Normal, Tercera Forma Normal, Forma Normal Boyce-Codd, Cuarta Forma Normal, Quinta Forma Normal o Forma Normal de Proyección-Unión, Forma Normal de Proyección-Unión Fuerte, Forma Normal de Proyección-Unión Extra Fuerte y Forma
Normal de Clave de Dominio. Cada nuevo nivel o forma lo acerca más a hacer su base de datos verdaderamente relacional.
Se discutieron las primeras tres formas. Éstas proveen suficiente nivel de normalización para cumplir con las necesidades de la mayoría de las bases de datos.
Normalizar demasiado puede conducir a tener una base de datos ineficiente y hacer a su esquema demasiado complejo para trabajar. Un balance apropiado de sentido común y
práctico puede ayudarle a decidir cuándo normalizar.
Una de las dudas mas habituales cuando nos enfrentamos a la instalación de scripts (perl, php) es la asignación de los permisos correspondientes. Las preguntas sobre CHMOD suelen ser las mas habituales en todos los foros que se dedican a estos temas. En este artículo abordaremos que son los permisos, para que sirven, y como asignarlos.
CHMOD (”Change mode”) es un comando UNIX que permite cambiar los permisos de acceso de un archivo. Cada archivo tiene nueve clases de acceso, que pueden ser permitidas o denegadas. Se pueden aplicar diferentes permisos al dueño del fichero, al grupo al que el fichero pertenece y al resto de usuarios. Cada una de estas tres clases de usuarios (dueño, grupo, resto de usuarios) puede tener permisos de lectura, escritura y ejecución
Al instalar cualquier archivo en una página web, podemos definir sus propiedades, para determinar en que forma será accesible para los visitantes de la página.
Estas propiedades son lo que llamamos permisos y segun cuales asignemos a cada archivo este será solo de lectura, de escritura o ejecutable, o cualquier combinación de los tres.
Piensa por ejemplo en una página de html sencilla, respecto de la cual solo nos interesa garantizar que todo el mundo pueda verla pero no modificarla; el archivo que contiene esa página necesita unicamente permisos de lectura, pero no de ejecución ni de escritura. Por contra, si se trata de un script, necesitará probablemente permisos de lectura y de ejecución, etc.
En este documento nos referimos a la asignación de permisos en servidores unix (unix, linux, freebsd, todos ellos pertenecientes a la familia unix, y con diferencia los mas difundidos en la red). La asignación de permisos se hace mediante el comando CHMOD. Por eso, cuando al leer las instrucciones de instalación de cualquier aplicación web te encuentres con la misteriosa frase “haz chmod 666 tal_archivo.htm” ten en consideración que nos estan diciendo los permisos que ese archivo necesita.
Los servidores Windows tienen su propio sistema de permisos, en los que no vamos a entrar aqui.
El sistema operativo UNIX esta diseñado para ser multiusuario. Por ello UNIX permite tres niveles de acceso a los archivos, para tres categorias diferentes de usuarios:
owner (propietario) La persona que el sistema reconoce como dueño del archivo.
Group (grupo): Conjunto de usuarios con permisos similares. Muy usado en entornos de trabajo, es de escasa aplicación en páginas web.
Other (otros): Cualquier otra persona.
Es un error asociar el concepto de usuario a una persona real. Se trata de una abstracción, que se refiere no a personas sino a categorias. Por ejemplo, si nosotros creamos un script, somos efectivamente sus autores y propietarios; pero ese script esta destinado a la red. Nosotros, y el resto de personas, accederan al archivo no a traves de nuestra maquina local sino por internet. Es frecuente en los servidores la creación de usuarios genéricos (root, www, www-user etc). En definitiva no olvides que cuando asignas permisos a un script, el owner puede ser cualquiera que visite la página, lo cual será necesario si como es normal se trata de scripts que se administran via web.
Read (lectura): Permiso para ver el archivo o directorio, sin hacer cambios.
Write (escritura): Permiso de escritura: puede escribir el archivo, y por tanto, cambiarlo.
Execute (ejecución): El archivo o directorio puede ser ejecutado. Se usa para directorios con scripts, formularios, etc …
Y tratándose de directorios:
read listar los archivos de un directorio
write añadir nuevos archivos al directorio
execute acceder a los archivos del directorio
Si tenemos acceso ftp al servidor, tecleamos el comando ls -l y vemos algo asi:
-rw-r--r-- 1 irvnet irvnet 1272 Sep 28 07:31 index.php | // / | | | | | | | | | | tamaño nombre del archivo | | | | | |_ nombre grupo | | | | | | | | | |_ nombre usuario | | | | | | | |_ Permisos genericos | | | | | |_ Los siguientes tres digitos los permisos del Group | | | |___ los siguientes tres caracteres determinan los permisos del owner: | r de real, lectura; w, write, escritura y x de | execute, ejecución | | |___ El primer carácter indica si nos encontramos ante un directorio o un fichero: d significa directorio, - significa fichero, l significa link
Advierte que tenemos TRES categorias de usuarios (”user,” “group,” y “other”) y para categoria pueden asignarse TRES tipos de permisos: “r,” “w,” y “x”.
La orden chmod puede usarse con letras o numeros. La forma mas corriente es expresar los permisos numericamente. Seguro que lo has visto por ahi, chmod 777 etc …
Para comprender el significado tienes que tener en cuenta que convencionalmente 4 significa permiso de lectura. 2 permiso de escritura y 1 permiso de ejecución. Sumando estos valores vemos que un archivo puede tener los siguientes permisos (por cada tipo de usuario):
4= lectura 2= escritura 1= ejecución 6 (4+2)= lectura y escritura 5 (4+1)= lectura y ejecución 3 (2+1)= escritura y ejecución 7 (4+2+1)= lectura, escritura y ejecución
Todo ello para los tres tipos de usuario.
Asi, un chmod file 777 significa que owner, group y others tienen permiso de lectura, escritura y ejecución. chmod 766 significa que el owner tiene permiso de lectura, escritura y ejecución, y el group y others permiso de lectura y escritura. Chmod 744 significa que el owner tiene permisos de lectura, escritura y ejecución, y group y others unicamente permisos de lectura.
Como ves, son tres digitos, de izquierda a derecha designan los permisos del owner, group y others.
Vemos a continuación su equivalente en letras:
0 = --- = sin acceso 1 = --x = ejecución 2 = -w- = escritura 3 = -wx = escritura y ejecución 4 = r-- = lectura 5 = r-x = lectura y ejecución 6 = rw- = lectura y escritura 7 = rwx = lectura, escritura y ejecución
Asi, en el ejemplo de antes:
rw-r--r--
significa que el owner tiene permisos de lectura y escritura (rw-); el group permisos de lectura unicamente (r–) y other, permiso de lectura (r–). ¿como seria el equivamente numerico? sería chmod 644.
La sintaxis para usar chmod con texto:
chmod [ugo][+-][rwx] [nombre_archivo]
Donde [u=user, g=group y o=other]; [+/- activa o desactiva los atributos siguientes] [r=read, w=write, x=execute]
Por ejemplo, chmod go+r index.php significa que asignamos permisos de lectura para group y others en index.php
De esta forma solo cambiamos los atributos que especificamos, pero no alteramos otros compatibles que pudieran estar asignados anteriormente) por ejemplo, no modifica la atribucion anterior a group de un permiso de ejecución).
Si queremos fijar de nuevo todos los permisos, la sintaxis sería:
chmod go=r index.php donde asignamos a group y other permiso de lectura sobre index.php y eliminamos cualquier otro permiso para ambos.
Ten encuenta asimismo que puedes usar comodines:
chmod 644 *.html etc …
This free script provided by JavaScript Kit
Este apartado se mantiene como simple ejemplo. Las ultimas versiones de php-nuke NO precisan permisos de archivo especiales.
Si leemos el install de phpnuke (versiones antiguas anteriores a la 6.0), por ejemplo, el de la versión 4.4, encontramos:
“… In order to use the File Manager, please be sure to chmod 666 ALL files and 777 ALL directories.
4) Also, to activate Headlines you “need” to chmod 777 the “cache” directory, otherwise headlines won’t work.
….
NOTE: If you want to edit config.php file from web browser remember to chmod 666 the file config.php or your changes will not be saved! If can’t execute chmod just edit the file by hand and re-upload it to your server”.
Bueno, aqui nos están diciendo que si queremos utilizar el “administrador de archivos” hay que asignar permisos 666 a todos los archivos, es decir, ya sabemos, permisos de lectura y escritura para TODOS los usuarios (owner, group, other) y 777 a todos los directorios (permiso para listar archivos, subir archivos, acceder archivos en el directorio, a los tres grupos de usuarios).
Para activar las headlines chmod 777 el directorio cache: listar archivos, subir archivos, acceder archivos en el directorio, a los tres grupos de usuarios.
Para modificar las preferencias de nuestra página via web (a traves de admin.php) debemos asignar a config.php permiso 666, es decir, permisos de lectura y escritura. De otra forma, si no tiene permisos de escritura, no se guardaran los cambios.
WS_FTP: click derecho sobre el archivo o directorio, y elegir “chmod” en el menu emergente. O tambien, click derecho y elegir del menu “SITE”, y en la barra que sale escribir el comando UNIX, por ejemplo, “chmod 666 config.php”.
CuteFTP: click derecho sobre el archivo o carpeta y elegir “Change file attributes” del menu emergente. Para ver los permisos en la ventana, click derecho sobre la ventana y elegir “Long listing”.
Telnet: Conectados al servidor, simplemente tecleamos chmod 666 config.php
HTML-kit Selecciona el archivo en el worksplace; click en el botón secundario del ratón y selecciona Set permissions. Obtendras una ventana donde podrás fijar el valor CHMOD chequeando casillas con los permisos, o bien introduciendo directamente su traducción numérica
he probado toda clase de sistemas para hacerlo y nunca me funcionó alguno, pero por fin encontré una solución que me funcionó. Se llama RecordMyDesktop y se instala muy fácilmente con dpkg -i archivo.deb o con gdebi haciendo doble click sobre él.
Hay que bajar los siguientes 2 archivos e instalarlos en orden para no tener problemas de dependencias:
RecordMyDesktop
gtk-RecordMyDesktop
Y listo… instalados, luego para ejecutarlo nos vamos a Inicio/Sonido y Video/gtk-recordmydesktop.
En estos días he tenido la necesidad de ver ciertas operaciones que se implementan el los árboles binarios de búsqueda (Binary Search Trees), y en este sitio encontré una implementación particularmente interesante, espero que les sea de utilidad.
En ciencias de la computación, un árbol binario de búsqueda es un árbol que tiene las siguientes propiedades:
La ventaja más notable de los árboles binarios de búsqueda es que los algoritmos de ordenación y búsqueda relacionados como transversal inorden pueden ser muy eficientes.
Los árboles binarios de búsqueda son una estructura de datos fundamental usada para construir más estructuras de datos abstractas como conjuntos y arrays asociativos.
// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) –> Insert x
// void remove( x ) –> Remove x
// void removeMin( ) –> Remove minimum item
// Comparable find( x ) –> Return item that matches x
// Comparable findMin( ) –> Return smallest item
// Comparable findMax( ) –> Return largest item
// boolean isEmpty( ) –> Return true if empty; else false
// void makeEmpty( ) –> Remove all items
// ******************ERRORS********************************
// Exceptions are thrown by insert, remove, and removeMin if warranted
/**
* Implements an unbalanced binary search tree.
* Note that all “matching” is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinarySearchTree {
/**
* Construct the tree.
*/
public BinarySearchTree( ) {
root = null;
}
/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( Comparable x ) {
root = insert( x, root );
}
/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( Comparable x ) {
root = remove( x, root );
}
/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) {
root = removeMin( root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( ) {
return elementAt( findMin( root ) );
}
/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public Comparable findMax( ) {
return elementAt( findMax( root ) );
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return root == null;
}
/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
throw new DuplicateItemException( x.toString( ) ); // Duplicate
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
*@return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;
return t;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match
}
return null; // Not found
}
/** The tree root. */
protected BinaryNode root;
// Test program
public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;
System.out.println( “Checking… (no more output means success)” );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );
for( int i = 1; i < NUMS; i+= 2 )
t.remove( new Integer( i ) );
if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
System.out.println( “FindMin or FindMax error!” );
for( int i = 2; i < NUMS; i+=2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( “Find error1!” );
for( int i = 1; i < NUMS; i+=2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( “Find error2!” );
}
}
}
// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of this package.
class BinaryNode {
// Constructors
BinaryNode( Comparable theElement ) {
element = theElement;
left = right = null;
}
// Friendly data; accessible by other package routines
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
/**
* Exception class for duplicate item errors
* in search tree insertions.
* @author Mark Allen Weiss
*/
public class DuplicateItemException extends RuntimeException {
/**
* Construct this exception object.
*/
public DuplicateItemException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message ) {
super( message );
}
}
/**
* Exception class for failed finds/removes in search
* trees, hash tables, and list and tree iterators.
* @author Mark Allen Weiss
*/
public class ItemNotFoundException extends RuntimeException {
/**
* Construct this exception object.
*/
public ItemNotFoundException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public ItemNotFoundException( String message ) {
super( message );
}
}
Fuente: Java-Tips.org, http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.htm
¿Por qué no debe usar el FTP normal un administrador?
La mayoría de la gente usa el FTP, que es inseguro para cargar y descargar archivos usando un programa FTP desde su casa. El problema es que su nombre de USUARIO y su CONTRASEÑA son enviados como texto puro por FTP, de modo que un hacker podría robar esta información con cierta facilidad y así tener acceso a su servidor.
¿Qué es el SFTP o FTP seguro?
Elimina la necesitad de usar FTP, usando SSH para conectarse a su servidor para cargar y descargar archivos. Conéctese usando SSH2 (como lo haría en todo caso con su programa SSH) y su conexión será segura.
¿Qué ventajas tiene el SFTP?
a) Su nombre de usuario y contraseñas circularán con seguridad.
1. Descargue e instale un cliente SFTP en su computadora doméstica.
El de mi preferencia es Filezilla
http://sourceforge.net/project/showfiles.php?group_id=21558
NOTA: Filezilla trabaja en parte con PUTTY, de modo que Ud. tendrá que instalar también PUTTY en su máquina.
2. Configure su cliente SFTP.
Si Ud. está usando Filezilla:
a. Abra el programa.
b. Pulse sobre Edit.
c. Pulse sobre Settings.
d. Abra el árbol de conexiones..
e. Pulse sobre SFTP settings.
f. Ponga “Use Compression” para ser usado por defecto.
g. Opte por usar SSH2 (es más seguro).
h. Pulse sobre OK.
i. Pulse sobre File.
j. Pulse sobre File Manager.
k. Pulse sobre New Site.
l. Entre la dirección IP de su SSH en Host.
m. En “ServerType” ponga SSH2, que funcionará por defecto con el puerto 22.
n. Cambie el número de puerto si ya tiene configurado algún otro para SSH.
o. En “LogonType” ponga Normal.
p. Entre con su nombre de USUARIO y CONTRASEÑA DE SSH.
q. Pulse sobre Save y Exit.
Y ya está. Ahora trate de conectarse con su servidor vía SSH2 usando su cliente SFTP, pulsando sobre el icono de conexión que está en la barra de tareas (en el extremo izquierdo). Debe funcionar. Si no funciona verifique nuevamente el IP de su SSH, Número de Puerto, Usuario y Contraseña.
Recuerde que se trata de los mismos datos que Ud. usa en su cliente SSH, como Putty, por ejemplo.
Al terminar, Ud. estará en condiciones de entrar mediante Filezilla (u otro cliente SFTP) y disfrutar de un acceso FTP seguro a su servidor, mediante conexión SSH. Su servidor ya no tendrá una puerta FTP activa y el servidor FTP
estará deshabilitado, lo que le ahorrará también algunos recursos.