2014-05-12
Practice Final #4.
Originally Posted By: ahmed93
Group Members: Kunal Palwankar, Ahmed Syed, Nirav Patel, Manbir Randhawa
Properties of Red-Black Tree:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black. (a little like fullness)
5. For each node, all simple paths from the node to descendant leaves contains the same number of black nodes. (a little like comparing left and right heights)
Example of red-black tree: Inserting values 5,10,15
Step 1: Inserting 5, which will be the root and its color is black
5
Step 2: Inserting 10, which will be the right child of root and its color is red
5
\
10
Step 3: Inserting 15, which will be the right child of value 10 and its color is red
5
\
10
\
15
Step 4: Now rotation occurs to maintain the property of redblack tree.
Value 10 will be the root and its color will be black. Value 5 and 15 will be left and right child respectively and their color will be red.
10
/ \
5 15
Properties of Red-Black Tree:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black. (a little like fullness)
5. For each node, all simple paths from the node to descendant leaves contains the same number of black nodes. (a little like comparing left and right heights)
Example of red-black tree: Inserting values 5,10,15
Step 1: Inserting 5, which will be the root and its color is black
5
Step 2: Inserting 10, which will be the right child of root and its color is red
5
\
10
Step 3: Inserting 15, which will be the right child of value 10 and its color is red
5
\
10
\
15
Step 4: Now rotation occurs to maintain the property of redblack tree.
Value 10 will be the root and its color will be black. Value 5 and 15 will be left and right child respectively and their color will be red.
10
/ \
5 15
'''Originally Posted By: ahmed93'''
Group Members: Kunal Palwankar, Ahmed Syed, Nirav Patel, Manbir Randhawa<br><br>Properties of Red-Black Tree:<br>1. Every node is either red or black.<br>2. The root is black.<br>3. Every leaf (NIL) is black.<br>4. If a node is red, then both its children are black. (a little like fullness)<br>5. For each node, all simple paths from the node to descendant leaves contains the same number of black nodes. (a little like comparing left and right heights)<br><br>Example of red-black tree: Inserting values 5,10,15<br>Step 1: Inserting 5, which will be the root and its color is black<br><br> 5<br><br>Step 2: Inserting 10, which will be the right child of root and its color is red<br><br> 5<br> \<br> 10<br><br>Step 3: Inserting 15, which will be the right child of value 10 and its color is red<br> 5<br> \<br> 10<br> \<br> 15<br>Step 4: Now rotation occurs to maintain the property of redblack tree. <br>Value 10 will be the root and its color will be black. Value 5 and 15 will be left and right child respectively and their color will be red.<br><br> 10<br> / \<br> 5 15
(c) 2024 Yioop - PHP Search Engine