Red-Black Tree: Difference between revisions
Jump to navigation
Jump to search
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..." |
No edit summary |
||
| 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. | '''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 == | ||
Latest revision as of 18:54, 3 June 2018
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.
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. That is why, the Red-Black Tree is height-balanced.
Resources
| 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/ |