Red–black tree: Difference between revisions

Revision as of 12:23, 13 May 2003

Revision as of 12:24, 13 May 2003

Line 9:

When nodes are removed or deleted, the tree must be transformed to keep these properties. This is done by repainting or [[Tree_rotation|rotating]] nodes.

A newly added node should be red by default. If the parent node is black, the tree is still valid. If both the parent node is red, and there exists a red uncle node, then they should be repainted black, and the grandparent node should be repainted red. (It may be necessary to continue repainting up to the root.) Otherwise, [[tree rotation|rotations]] are neccesarynecessary. If the root ends up red, it should be repainted black.

See Also: [[B tree]]