Savoundg at 18:54, 3 June 2018

2018-06-03T18:54:24Z

← Older revision		Revision as of 18:54, 3 June 2018
Line 1:		Line 1:
	Red-Black Tree is a self-balancing Binary Search Tree.		Red-Black Tree is a self-balancing height-balanced Binary Search Tree.

	Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion and deletion time are also in O(log n) even in the worst case. This data structure is valuable for time-sensitive application such as real-time applications.		Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion and deletion time are also in O(log n) even in the worst case. This data structure is valuable for time-sensitive application such as real-time applications.
Line 9:		Line 9:
	# A red node cannot have a red parent or children.		# A red node cannot have a red parent or children.
	# The number of black nodes from the root to a given node is called the '''black depth'''. Every paths from root to the leaves have the same black depth and it is called the '''black-height'''.		# The number of black nodes from the root to a given node is called the '''black depth'''. Every paths from root to the leaves have the same black depth and it is called the '''black-height'''.
	'''Property:''' the path from the root to the farthest left is no more than twice as long as the path from the root to the nearest leaf. ~~Hence~~, the Red-Black Tree is height-balanced.		'''Property:''' the path from the root to the farthest left is no more than twice as long as the path from the root to the nearest leaf. That is why, the Red-Black Tree is height-balanced.

	== Resources ==		== Resources ==

Savoundg: Created page with "Red-Black Tree is a self-balancing Binary Search Tree. Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion..."

2018-06-03T18:42:44Z

Created page with "Red-Black Tree is a self-balancing Binary Search Tree. Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion..."

New page

Red-Black Tree is a self-balancing Binary Search Tree.

Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion and deletion time are also in O(log n) even in the worst case. This data structure is valuable for time-sensitive application such as real-time applications.

'''Requirements:'''
# Each node is either red or black.
# The root and the leaf nodes are black.
# The leaf node does not contain data.
# A red node cannot have a red parent or children.
# The number of black nodes from the root to a given node is called the '''black depth'''. Every paths from root to the leaves have the same black depth and it is called the '''black-height'''.
'''Property:''' the path from the root to the farthest left is no more than twice as long as the path from the root to the nearest leaf. Hence, the Red-Black Tree is height-balanced.

== Resources ==
{| class="wikitable"
!
|-
|https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
|-
|http://www.computepatterns.com/problem-solving/data-structures/binary-tree/binary-search-tree-bst/splay-tree-and-red-black-tree/
|}

Red-Black Tree - Revision history

Savoundg at 18:54, 3 June 2018

Savoundg: Created page with "Red-Black Tree is a self-balancing Binary Search Tree. Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion..."