[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

Red Black Tree Applet

Prof. e colegas,

Acho que esta página é uma boa fonte para o esclarecimento das dúvidas
que possam ter surgido
na última aula sobre árvores rubro-negras.

http://www.cdf.toronto.edu/~g6ngower/378/rbt.html

Lennon Machado
18/5/99 7h45min
Title: Red Black Tree Applet

Red Black Tree in Java

About Red Black Trees

Red Black Trees are a special kind of Binary Search Tree, similar to AVL Trees. There are three differences between Red Black Trees and simple Binary Search Trees:

  1. Smarter insertion algorithm.
  2. Smarter deletion algorithm.
  3. Nodes store a colour in addition to key and branch information.
The idea behind the colouring of nodes is that by assigning a node a colour (red or black), one can store some information about the balance of tree in each node. This information is then used by the insertion and deletion algorithms to reorganize the tree after each insertion or deletion to maintain reasonable balance. Reasonable balance in a Red Black Tree is defined such that the longest path from root to leaf is no more than twice the length of the shortest path. Thus, the time required for any search in the tree is within a constant factor of the ideal (balanced) tree's search time.

Red Black Trees maintain the four red-black properties:

  1. Every node is either red or black.
  2. Every leaf (nil pointers are considered leaves) is black.
  3. If a node is red, then both it's children are black.
  4. Every simple path from a node to a descendant leaf contains the same number of black nodes.

About the Applet

The applet will accept any integer (up to 9 digits) as a new key for the tree, which you can insert by pressing the insert button. There is no error checking on the input, so if you enter nonsense (i.e. non-integers) your input will be ignored. Also, the draw routines allow you to keep drawing even if there is no room for the new node. This means that if your tree gets too wide or deep you may have trouble seeing the new nodes.

neil.gower@utoronto.ca