Binary Tree Restructuring

Last updated Jan 2, 2022 Edit Source

• Cs data structures
• Cs algorithms
• Cs trees

Sometimes, when creating a balanced tree, rotations may not be sufficient. In this case, a technique called trinode structuring comes in, which is essentially one or two rotations combined. The operation of restructuring from a node $x$ involves these steps:

1
2
3
4
5

restructure(x):
	let y be the parent and z be the grandparent of x
	let (a, b, c) be these nodes in in-order traversal
	let T1...T4 be the subtrees of each of these nodes.
	restructure the tree so that:

Ignore the colors, here this figure is from an explanation of red-black trees.