Write Code In Java AVL Tree Objective: Create an instance of an AVL tree of inte

Question

Write Code In Java

AVL Tree

Objective:

Create an instance of an AVL tree of integers. An AVL tree is a type of binary tree which has a self-balancing property, which requires rotations of sub trees. More information can be found here:

http://en.wikipedia.org/wiki/AVL_tree

Demonstrate your tree works with a driver file which will create an AVL tree of 20 integers.

Explanation / Answer

class Node { int key, height; Node left, right; Node(int d) { key = d; height = 1; } } class AVLTree { static Node root; int height(Node N) { if (N == null) { return 0; } return N.height; } int max(int a, int b) { return (a > b) ? a : b; } Node rightRotate(Node y) { Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; y.height = max(height(y.left), height(y.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; return x; } Node leftRotate(Node x) { Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; x.height = max(height(x.left), height(x.right)) + 1; y.height = max(height(y.left), height(y.right)) + 1; return y; } int getBalance(Node N) { if (N == null) { return 0; } return height(N.left) - height(N.right); } Node insert(Node node, int key) { if (node == null) { return (new Node(key)); } if (key 1 && key node.right.key) { return leftRotate(node); } if (balance > 1 && key > node.left.key) { node.left = leftRotate(node.left); return rightRotate(node); } if (balance < -1 && key

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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