class Node
1: //Node.java
3: class Node
4: {
5: public enum Child
6: {
7: LEFT, RIGHT
8: }
10: public int key;
11: public Node parent;
12: public Node left;
13: public Node right;
14: public int height;
16: // Constructor with a key parameter creates the Node object.
17: public Node(int nodeKey)
18: {
19: key = nodeKey;
20: parent = null;
21: left = null;
22: right = null;
23: height = 0;
24: }
26: // Calculate this nodes' balance factor, defined as
27: // height(left subtree) - height(right subtree)
28: public int getBalance()
29: {
30: // Get current height of left subtree, or -1 if null
31: int leftHeight = -1;
32: if (left != null)
33: {
34: leftHeight = left.height;
35: }
37: // Get current height of right subtree, or -1 if null
38: int rightHeight = -1;
39: if (right != null)
40: {
41: rightHeight = right.height;
42: }
44: // Calculate the balance factor.
45: return leftHeight - rightHeight;
46: }
48: // Recalculate the current height of the subtree rooted at
49: // the node, usually called after a subtree has been
50: // modified.
51: public void updateHeight()
52: {
53: // Get current height of left subtree, or -1 if null
54: int leftHeight = -1;
55: if (left != null)
56: {
57: leftHeight = left.height;
58: }
60: // Get current height of right subtree, or -1 if null
61: int rightHeight = -1;
62: if (right != null)
63: {
64: rightHeight = right.height;
65: }
67: // Assign height with calculated node height.
68: height = Math.max(leftHeight, rightHeight) + 1;
69: }
71: // Assign either the left or right data member with a new
72: // child. Returns true if the new child is successfully
73: // assigned to this node, false otherwise.
74: public boolean setChild(Child whichChild, Node child)
75: {
76: // Assign the left or right data member.
77: if (whichChild == Child.LEFT)
78: {
79: left = child;
80: }
81: else
82: {
83: right = child;
84: }
86: // Assign the parent data member of the new child,
87: // if the child is not null.
88: if (child != null)
89: {
90: child.parent = this;
91: }
93: // Update the node's height, since the subtree's structure
94: // may have changed.
95: updateHeight();
96: return true;
97: }
99: // Replace a current child with a new child. Determines if
100: // the current child is on the left or right, and calls
101: // setChild() with the new node appropriately.
102: // Returns true if the new child is assigned, false otherwise.
103: public boolean replaceChild(Node currentChild, Node newChild)
104: {
105: if (left == currentChild)
106: {
107: return setChild(Child.LEFT, newChild);
108: }
109: else if (right == currentChild)
110: {
111: return setChild(Child.RIGHT, newChild);
112: }
114: // If neither of the above cases applied, then the new child
115: // could not be attached to this node.
116: return false;
117: }
118: }