A red–black tree is a data structure which is a type of self-balancing binary search tree.

Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.

Introduced classes

class RBTreeMap[K: Comparable, E: nullable Object]

trees :: RBTreeMap

Red-Black Tree Map
class RBTreeNode[K: Comparable, E: nullable Object]

trees :: RBTreeNode

RedBlackTree node (can be red or black)

All class definitions

class RBTreeMap[K: Comparable, E: nullable Object]

trees $ RBTreeMap

Red-Black Tree Map
class RBTreeNode[K: Comparable, E: nullable Object]

trees $ RBTreeNode

RedBlackTree node (can be red or black)
package_diagram trees::rbtree rbtree trees::bintree bintree trees::rbtree->trees::bintree trees::abstract_tree abstract_tree trees::bintree->trees::abstract_tree ...trees::abstract_tree ... ...trees::abstract_tree->trees::abstract_tree trees::trees trees trees::trees->trees::rbtree ai::search search ai::search->trees::trees trees::trie trie trees::trie->trees::trees ai::search... ... ai::search...->ai::search trees::trie... ... trees::trie...->trees::trie

Ancestors

module abstract_collection

core :: abstract_collection

Abstract collection classes and services.
module abstract_text

core :: abstract_text

Abstract class for manipulation of sequences of characters
module abstract_tree

trees :: abstract_tree

Introduce tree structures abstraction
module array

core :: array

This module introduces the standard array structure.
module bitset

core :: bitset

Services to handle BitSet
module bytes

core :: bytes

Services for byte streams and arrays
module circular_array

core :: circular_array

Efficient data structure to access both end of the sequence.
module codec_base

core :: codec_base

Base for codecs to use with streams
module codecs

core :: codecs

Group module for all codec-related manipulations
module collection

core :: collection

This module define several collection classes.
module core

core :: core

Standard classes and methods used by default by Nit programs and libraries.
module environ

core :: environ

Access to the environment variables of the process
module error

core :: error

Standard error-management infrastructure.
module exec

core :: exec

Invocation and management of operating system sub-processes.
module file

core :: file

File manipulations (create, read, write, etc.)
module fixed_ints

core :: fixed_ints

Basic integers of fixed-precision
module fixed_ints_text

core :: fixed_ints_text

Text services to complement fixed_ints
module flat

core :: flat

All the array-based text representations
module gc

core :: gc

Access to the Nit internal garbage collection mechanism
module hash_collection

core :: hash_collection

Introduce HashMap and HashSet.
module iso8859_1

core :: iso8859_1

Codec for ISO8859-1 I/O
module kernel

core :: kernel

Most basic classes and methods.
module list

core :: list

This module handle double linked lists
module math

core :: math

Mathematical operations
module native

core :: native

Native structures for text and bytes
module numeric

core :: numeric

Advanced services for Numeric types
module protocol

core :: protocol

module queue

core :: queue

Queuing data structures and wrappers
module range

core :: range

Module for range of discrete objects.
module re

core :: re

Regular expression support for all services based on Pattern
module ropes

core :: ropes

Tree-based representation of a String.
module sorter

core :: sorter

This module contains classes used to compare things and sorts arrays.
module stream

core :: stream

Input and output streams of characters
module text

core :: text

All the classes and methods related to the manipulation of text entities
module time

core :: time

Management of time and dates
module union_find

core :: union_find

union–find algorithm using an efficient disjoint-set data structure
module utf8

core :: utf8

Codec for UTF-8 I/O

Parents

module bintree

trees :: bintree

Binary Tree data-structure

Children

module trees

trees :: trees

General module for tree data structures

Descendants

module a_star-m

a_star-m

module puzzle

ai :: puzzle

The N-puzzle problem, modeled naively as a SearchProblem.
module search

ai :: search

Basic framework for search problems and solver.
module trie

trees :: trie

A trie (or prefix tree) is a datastructure used to perform prefix searches.
# A red–black tree is a data structure which is a type of self-balancing binary search tree.
#
# Balance is preserved by painting each node of the tree with one of two colors
# (typically called 'red' and 'black') in a way that satisfies certain properties,
# which collectively constrain how unbalanced the tree can become in the worst case.
# When the tree is modified, the new tree is subsequently rearranged and repainted
# to restore the coloring properties.
# The properties are designed in such a way that this rearranging and recoloring
# can be performed efficiently.
#
# The balancing of the tree is not perfect but it is good enough to allow it
# to guarantee searching in O(log n) time, where n is the total number of elements in the tree.
# The insertion and deletion operations, along with the tree rearrangement and recoloring,
# are also performed in O(log n) time.
module rbtree

import bintree

# Red-Black Tree Map
# Properties of a Red-Black tree map:
# * every node is either red or black
# * root is black
# * every leaf (null) is black
# * if a node is red, then both its children are black
# * for each node, all simple path from the node to descendant
#   leaves contain the same number of black nodes
#
# Operations:
# * search average O(lg n) worst O(lg n)
# * insert average O(lg n) worst O(lg n)
# * delete average O(lg n) worst O(lg n)
class RBTreeMap[K: Comparable, E]
	super BinTreeMap[K, E]

	redef type N: RBTreeNode[K, E]

	redef fun []=(key, item) do
		insert_node(new RBTreeNode[K, E](key, item))
	end

	redef fun insert_node(node) do
		super
		insert_fixup_case1(node)
	end

	# Case 1: node is root
	# color node as black
	# it adds a black node on every path so we do nothing else
	private fun insert_fixup_case1(node: N) do
		if node.parent == null then
			node.is_red = false
		else
			insert_fixup_case2(node)
		end
	end

	# Case 2: parent is black
	# it do not add black node so we do nothing else
	private fun insert_fixup_case2(node: N) do
		if node.parent.is_red then insert_fixup_case3(node)
	end

	# Case 3: node, parent and uncle are red
	# this is a LLr or RRr conflict
	# we recolor recursively the tree to the root
	private fun insert_fixup_case3(node: N) do
		if node.uncle != null and node.uncle.is_red then
			node.parent.is_red = false
			node.uncle.is_red = false
			node.grandparent.is_red = true
			insert_fixup_case1(node.grandparent.as(not null))
		else
			insert_fixup_case4(node)
		end
	end

	# Case 4: node and parent are red, uncle is black
	# this is a LRb or RLb conflict
	# we rotate the tree to balance it
	private fun insert_fixup_case4(node: N) do
		if node == node.parent.right and node.parent == node.grandparent.left then
			rotate_left(node.parent.as(not null))
			node = node.left.as(not null)
		else if node == node.parent.left and node.parent == node.grandparent.right then
			rotate_right(node.parent.as(not null))
			node = node.right.as(not null)
		end
		insert_fixup_case5(node)
	end

	# Case 5: node and parent are red, uncle is black
	# this is a LLb or RRb conflict
	# we rotate the tree to balance it
	private fun insert_fixup_case5(node: N) do
		node.parent.is_red = false
		node.grandparent.is_red = true
		if node == node.parent.left then
			rotate_right(node.grandparent.as(not null))
		else
			rotate_left(node.grandparent.as(not null))
		end
	end

	# TODO implement RBTree::delete
	redef fun delete(key) is abstract

	redef fun dot_down(node, f) do
		if node.left != null then dot_down(node.left.as(not null), f)
		f.write node.to_dot
		if node.parent != null then f.write "\"{node.parent.as(not null)}\" -> \"{node}\"[dir=back];\n"
		if node.right != null then dot_down(node.right.as(not null), f)
	end
end

# RedBlackTree node (can be red or black)
class RBTreeNode[K: Comparable, E]
	super BinTreeNode[K, E]

	redef type N: RBTreeNode[K, E]

	# Is the node red?
	private var is_red = true

	redef fun to_dot do
		if is_red then
			return "\"{self}\"[style=filled,fillcolor=red,fontcolor=white];\n"
		else
			return "\"{self}\"[style=filled,fillcolor=black,fontcolor=white];\n"
		end

	end
end
lib/trees/rbtree.nit:15,1--146,3