An algorithm has been designed to optimize balancing a binary search tree at all

Question

An algorithm has been designed to optimize balancing a binary search tree at all times and uses the following node structure:
class Node
{
          int key;
    Node parent;
    Node left;
    Node right;

};
The project team has determined that one of the keys parts to the algorithm is the ability to swap a parent node with a designated child node. The team lead found out you took this awesome Data Structures class at SJCC and requested you write the swap algorithm.
The function call for the swap has the following signature:
public void swap (Node parent, Node child)
Code this function. It doesn%u2019t have to be syntactically perfect but enough to show accuracy of the algorithm. Keep in mind the following:
1)    If the parent node has a parent, the appropriate left or right child pointer of it must be handled appropriately
2)    The parent node might be the root node (a.k.a. a node with no parent) so that case should be handled
3)    A swap usually requires the need for a temp. The temp node in this case should make sure all 3 of its Node pointers are set properly

Explanation / Answer

public void swap (Node parent, Node child) {

if( child.right != null ) child.right.parent = parent;

if( child.left !=null) child.left.parent = parent;

if( child == parent.left ) {

Node tmp = child.right;

child.right = parent.right;

parent.right = tmp;

parent.left = child.left;

child.left = parent;

} else {

Node tmp = child.left;

child.left= parent.left;

parent.left= tmp;

parent.right= child.right;

child.right = parent;

}

child.parent = parent.parent;

parent.parent = child;

if( child.parent != null ) {

if( child.parent.right == parent)

child.parent.right = child;

else

child.parent.left = child;

}

if( child.left ) child.left.parent = child;

if( child.right ) child.right.parent = child;

if( parent.left ) parent.left.parent = parent;

if( parent.right ) parent.right.parent = parent;

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.