class AVLTree
1: //AVLTree.java
3: class AVLTree
4: {
5: private Node root;
7: public AVLTree()
8: {
9: root = null;
10: }
12: public Node getRoot()
13: {
14: return root;
15: }
17: // Performs a left rotation at the given node. Returns the
18: // subtree's new root.
19: public Node rotateLeft(Node node)
20: {
21: // Define a convenience pointer to the right child of the
22: // left child.
23: Node rightLeftChild = node.right.left;
25: // Step 1 - the right child moves up to the node's position.
26: // node is temporarily detached from the tree, but will be reattached
27: // later.
28: if (node.parent != null)
29: {
30: node.parent.replaceChild(node, node.right);
31: }
32: else // node is root
33: {
34: root = node.right;
35: root.parent = null;
36: }
38: // Step 2 - the node becomes the left child of what used
39: // to be node's right child, but is now node's parent. This will
40: // detach rightLeftChild from the tree.
41: node.right.setChild(Node.Child.LEFT, node);
43: // Step 3 - reattach rightLeftChild as the right child of node.
44: node.setChild(Node.Child.RIGHT, rightLeftChild);
46: return node.parent;
47: }
49: // Performs a right rotation at the given node. Returns the
50: // subtree's new root.
51: public Node rotateRight(Node node)
52: {
53: // Define a convenience pointer to the left child of the
54: // right child.
55: Node leftRightChild = node.left.right;
57: // Step 1 - the left child moves up to the node's position.
58: // node is temporarily detached from the tree, but will be reattached
59: // later.
60: if (node.parent != null)
61: {
62: node.parent.replaceChild(node, node.left);
63: }
64: else // node is root
65: {
66: root = node.left;
67: root.parent = null;
68: }
70: // Step 2 - the node becomes the right child of what used
71: // to be node's left child, but is now node's parent. This will
72: // detach leftRightChild from the tree.
73: node.left.setChild(Node.Child.RIGHT, node);
75: // Step 3 - reattach leftRightChild as the right child of node.
76: node.setChild(Node.Child.LEFT, leftRightChild);
78: return node.parent;
79: }
81: // Updates the given node's height and rebalances the subtree if
82: // the balancing factor is now -2 or +2. Rebalancing is done by
83: // performing a rotation. Returns the subtree's new root if
84: // a rotation occurred, or the node if no rebalancing was required.
85: public Node rebalance(Node node)
86: {
87: // First update the height of this node.
88: node.updateHeight();
90: // Check for an imbalance.
91: if (node.getBalance() == -2)
92: {
93: // The subtree is too big to the right.
94: if (node.right.getBalance() == 1)
95: {
96: // Double rotation case. First do a right rotation
97: // on the right child.
98: rotateRight(node.right);
99: }
101: // A left rotation will now make the subtree balanced.
102: return rotateLeft(node);
103: }
104: else if (node.getBalance() == 2)
105: {
106: // The subtree is too big to the left
107: if (node.left.getBalance() == -1)
108: {
109: // Double rotation case. First do a left rotation
110: // on the left child.
111: rotateLeft(node.left);
112: }
114: // A right rotation will now make the subtree balanced.
115: return rotateRight(node);
116: }
118: // No imbalance, so just return the original node.
119: return node;
120: }
122: // Searches for a node with a matching key. Does a regular
123: // binary search tree search operation. Returns the node with the
124: // matching key, or null if no matching key exists in the tree.
125: public Node search(int desiredKey)
126: {
127: Node currentNode = root;
128: while (currentNode != null)
129: {
130: // Return the node if the key matches
131: if (currentNode.key == desiredKey)
132: {
133: return currentNode;
134: }
136: // Navigate to the left if the search key is
137: // less than the node's key.
138: else if (desiredKey < currentNode.key)
139: {
140: currentNode = currentNode.left;
141: }
143: // Navigate to the right if the search key is
144: // greater than the node's key.
145: else
146: {
147: currentNode = currentNode.right;
148: }
149: }
151: // The key was not found in the tree.
152: return null;
153: }
155: public void insert(Node node)
156: {
157: // Check if tree is empty
158: if (root == null)
159: {
160: root = node;
161: }
162: else
163: {
164: // Step 1 - do a regular binary search tree insert.
165: Node currentNode = root;
166: while (currentNode != null)
167: {
168: // Choose to go left or right
169: if (node.key < currentNode.key)
170: {
171: // Go left. If left child is null, insert the new
172: // node here.
173: if (currentNode.left == null)
174: {
175: currentNode.left = node;
176: node.parent = currentNode;
177: currentNode = null;
178: }
179: else
180: {
181: // Go left and do the loop again.
182: currentNode = currentNode.left;
183: }
184: }
185: else
186: {
187: // Go right. If the right child is null, insert the
188: // new node here.
189: if (currentNode.right == null)
190: {
191: currentNode.right = node;
192: node.parent = currentNode;
193: currentNode = null;
194: }
195: else
196: {
197: // Go right and do the loop again.
198: currentNode = currentNode.right;
199: }
200: }
201: }
203: // Step 2 - Rebalance along a path from the new node's parent up
204: // to the root.
205: node = node.parent;
206: while (node != null)
207: {
208: rebalance(node);
209: node = node.parent;
210: }
211: }
212: }
214: // Attempts to remove a node with a matching key. If no node has a matching
215: // key then nothing is done and false is returned; otherwise the node is
216: // removed and true is returned.
217: public boolean removeKey(int key)
218: {
219: Node node = search(key);
220: if (node == null)
221: {
222: return false;
223: }
224: else
225: {
226: return removeNode(node);
227: }
228: }
230: private boolean removeNode(Node nodeToRemove)
231: {
232: // # Base case:
233: if (nodeToRemove == null)
234: {
235: return false;
236: }
238: // Parent needed for rebalancing.
239: Node parent = nodeToRemove.parent;
241: // Case 1: Internal node with 2 children
242: if (nodeToRemove.left != null && nodeToRemove.right != null)
243: {
244: // Find successor
245: Node successorNode = nodeToRemove.right;
246: while (successorNode.left != null)
247: {
248: successorNode = successorNode.left;
249: }
251: // Copy the value from the node
252: nodeToRemove.key = successorNode.key;
254: // Recursively remove successor
255: removeNode(successorNode);
257: // Nothing left to do since the recursive call will have rebalanced
258: return true;
259: }
261: // Case 2: Root node (with 1 or 0 children)
262: else if (nodeToRemove == root)
263: {
264: if (nodeToRemove.left != null)
265: {
266: root = nodeToRemove.left;
267: }
268: else
269: {
270: root = nodeToRemove.right;
271: }
273: if (root != null)
274: {
275: root.parent = null;
276: }
278: return true;
279: }
281: // Case 3: Internal with left child only
282: else if (nodeToRemove.left != null)
283: {
284: parent.replaceChild(nodeToRemove, nodeToRemove.left);
285: }
287: // Case 4: Internal with right child only OR leaf
288: else
289: {
290: parent.replaceChild(nodeToRemove, nodeToRemove.right);
291: }
293: // nodeToRemove is gone. Anything that was below nodeToRemove that
294: // has persisted is already correctly balanced, but ancestors ofr
295: // nodeToRemove may need rebalancing.
296: nodeToRemove = parent;
297: while (nodeToRemove != null)
298: {
299: rebalance(nodeToRemove);
300: nodeToRemove = nodeToRemove.parent;
301: }
303: return true;
304: }
305: }