Anyone helps for document? I want comments public class AVLTree> extends BinaryS
ID: 3903389 • Letter: A
Question
Anyone helps for document? I want comments
public class AVLTree> extends BinarySearchTree
{
private static final int ALLOWED_IMBALANCE = 1;
private boolean shouldPrintRotations;
public AVLTree()
{
this(false);
}
public AVLTree(boolean shouldPrintRotations)
{
this.shouldPrintRotations = shouldPrintRotations;
}
public boolean isBalanced()
{
return isBalanced(root);
}
private boolean isBalanced(BinaryNode root)
{
if(root == null)
{
return true;
}
else
{
int leftHeight = height(root.getLeft());
int rightHeight = height(root.getRight());
return Math.abs(leftHeight - rightHeight) <= 1;
}
}
@Override
protected BinaryNode insert(T data, BinaryNode root)
{
return balance(super.insert(data, root));
}
@Override
protected BinaryNode remove(T data, BinaryNode root)
{
return balance(super.remove(data, root));
}
private BinaryNode balance(BinaryNode root)
{
if(root == null)
{
return null;
}
if(height(root.getLeft()) - height(root.getRight()) > 1)
{
if(height(root.getLeft().getLeft()) >= height(root.getLeft().getRight()))
{
root = singleRightRotation(root);
}
else
{
root = doubleLeftRightRotation(root);
}
}
else if(height(root.getRight()) - height(root.getLeft()) > 1)
{
if(height(root.getRight().getRight()) >= height(root.getRight().getLeft()))
{
root = singleLeftRotation(root);
}
else
{
root = doubleRightLeftRotation(root);
}
}
return root;
}
private BinaryNode singleRightRotation(BinaryNode k2)
{
if(shouldPrintRotations)
{
System.out.println("Single Right Rotation: " + k2.getData());
}
BinaryNode k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight(k2);
k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1);
k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1);
return k1;
}
private BinaryNode singleLeftRotation(BinaryNode k1)
{
if(shouldPrintRotations)
{
System.out.println("Single Left Rotation: " + k1.getData());
}
BinaryNode k2 = k1.getRight();
k1.setRight(k2.getLeft());
k2.setLeft(k1);
k1.setHeight(Math.max(height(k1.getLeft()), height(k1.getRight())) + 1);
k2.setHeight(Math.max(height(k2.getRight()), k1.getHeight()) + 1);
return k2;
}
private BinaryNode doubleLeftRightRotation(BinaryNode k3)
{
if(shouldPrintRotations)
{
System.out.println("Double Left-Right Rotation: " + k3.getData());
}
k3.setLeft(singleLeftRotation(k3.getLeft()));
return singleRightRotation(k3);
}
private BinaryNode doubleRightLeftRotation(BinaryNode k1)
{
if(shouldPrintRotations)
{
System.out.println("Double Right-Left Rotation: " + k1.getData());
}
k1.setRight(singleRightRotation(k1.getRight()));
return singleLeftRotation(k1);
}
}
----------------------------------------------------------------------------
import java.util.Comparator;
import java.util.Random;
public class BinarySearchTree> {
protected BinaryNode root;
public BinarySearchTree() {
root = null;
}
public void empty() {
root = null;
}
public boolean isEmpty(){
return root == null;
}
public BinaryNode getRoot(){
return root;
}
public int height() {
return height(root);
}
protected int height(BinaryNode root) {
if(root == null) {
return -1;
}
else {
return Math.max(height(root.getLeft()), height(root.getRight())) + 1;
}
}
public boolean contains(T data){
return contains(data, root);
}
protected boolean contains(T data, BinaryNode root){
if(root == null){
return false;
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0){
return contains(data, root.getLeft());
}
else if(compareResult < 0){
return contains(data, root.getRight());
}
else{
return true;
}
}
public T findMin() {
BinaryNode node = findMin(root);
return node == null ? null : node.getData();
}
protected BinaryNode findMin(BinaryNode root) {
if(root == null) {
return null;
}
else if(root.getLeft() == null) {
return root;
}
else {
return findMin(root.getLeft());
}
}
public T findMax() {
BinaryNode node = findMax(root);
return node == null ? null : node.getData();
}
protected BinaryNode findMax(BinaryNode root) {
if(root == null) {
return null;
}
else if(root.getRight() == null) {
return root;
}
else {
return findMin(root.getRight());
}
}
public void insert(T data) {
root = insert(data, root);
}
protected BinaryNode insert(T data, BinaryNode root) {
if(root == null) {
return new BinaryNode<>(data);
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0) {
root.setLeft(insert(data, root.getLeft()));
}
else if(compareResult < 0) {
root.setRight(insert(data, root.getRight()));
}
return root;
}
public void remove(T data) {
root = remove(data, root);
}
protected BinaryNode remove(T data, BinaryNode root) {
if(root == null) {
return null;
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0) {
root.setLeft(remove(data, root.getLeft()));
}
else if(compareResult < 0) {
root.setRight(remove(data, root.getRight()));
}
else if(root.getLeft() != null && root.getRight() != null) {
root.setData(findMin(root.getRight()).getData());
root.setRight(remove(root.getData(), root.getRight()));
}
else {
root = root.getLeft() != null ? root.getLeft() : root.getRight();
}
return root;
}
public void printTree() {
printTree(root);
}
protected void printTree(BinaryNode root) {
if(root != null) {
printTree(root.getLeft());
System.out.println(root.getData());
printTree(root.getRight());
}
}
}
---------------------------------------------------------------
public class BinaryNode>
{
private T data;
private int height;
private BinaryNode left;
private BinaryNode right;
public BinaryNode(T data)
{
this(data, null, null);
}
public BinaryNode(T data, BinaryNode left, BinaryNode right)
{
this.data = data;
this.left = left;
this.right = right;
this.height = 0;
}
public T getData()
{
return data;
}
public void setData(T data)
{
this.data = data;
}
public BinaryNode getLeft()
{
return left;
}
public void setLeft(BinaryNode left)
{
this.left = left;
}
public BinaryNode getRight()
{
return right;
}
public void setRight(BinaryNode right)
{
this.right = right;
}
public int getHeight()
{
return height;
}
public void setHeight(int height)
{
this.height = height;
}
}
Explanation / Answer
//AVL tree class definition
public class AVLTree> extends BinarySearchTree
{
//Variables declarations
private static final int ALLOWED_IMBALANCE = 1;
private boolean shouldPrintRotations;
//Contructor without any arguments
public AVLTree()
{
this(false);
}
//Overloaded constructor
public AVLTree(boolean shouldPrintRotations)
{
this.shouldPrintRotations = shouldPrintRotations;
}
//Calls isBalanced overloaded method and returns the result
public boolean isBalanced()
{
return isBalanced(root);
}
//MEthod to check whether the tee is balanced or not
private boolean isBalanced(BinaryNode root)
{
if(root == null)
{
return true;
}
else
{
int leftHeight = height(root.getLeft());
int rightHeight = height(root.getRight());
return Math.abs(leftHeight - rightHeight) <= 1;
}
}
//Overriden method to insert data into AVK tree
@Override
protected BinaryNode insert(T data, BinaryNode root)
{
return balance(super.insert(data, root));
}
//Overriden method to remove data from a node
@Override
protected BinaryNode remove(T data, BinaryNode root)
{
return balance(super.remove(data, root));
}
//Method to balance the AVL tree
private BinaryNode balance(BinaryNode root)
{
if(root == null)
{
return null;
}
if(height(root.getLeft()) - height(root.getRight()) > 1)
{
if(height(root.getLeft().getLeft()) >= height(root.getLeft().getRight()))
{
root = singleRightRotation(root);
}
else
{
root = doubleLeftRightRotation(root);
}
}
else if(height(root.getRight()) - height(root.getLeft()) > 1)
{
if(height(root.getRight().getRight()) >= height(root.getRight().getLeft()))
{
root = singleLeftRotation(root);
}
else
{
root = doubleRightLeftRotation(root);
}
}
return root;
}
//MEthod to perform single rotaion operation to right side
private BinaryNode singleRightRotation(BinaryNode k2)
{
if(shouldPrintRotations)
{
System.out.println("Single Right Rotation: " + k2.getData());
}
BinaryNode k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight(k2);
k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1);
k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1);
return k1;
}
//MEthod to perform single rotaion operation to left side
private BinaryNode singleLeftRotation(BinaryNode k1)
{
if(shouldPrintRotations)
{
System.out.println("Single Left Rotation: " + k1.getData());
}
BinaryNode k2 = k1.getRight();
k1.setRight(k2.getLeft());
k2.setLeft(k1);
k1.setHeight(Math.max(height(k1.getLeft()), height(k1.getRight())) + 1);
k2.setHeight(Math.max(height(k2.getRight()), k1.getHeight()) + 1);
return k2;
}
//Performs double left right rotation operation
private BinaryNode doubleLeftRightRotation(BinaryNode k3)
{
if(shouldPrintRotations)
{
System.out.println("Double Left-Right Rotation: " + k3.getData());
}
k3.setLeft(singleLeftRotation(k3.getLeft()));
return singleRightRotation(k3);
}
//Performs double right left rotation operation
private BinaryNode doubleRightLeftRotation(BinaryNode k1)
{
if(shouldPrintRotations)
{
System.out.println("Double Right-Left Rotation: " + k1.getData());
}
k1.setRight(singleRightRotation(k1.getRight()));
return singleLeftRotation(k1);
}
}
-----------------------------------------------------------------------------------------------------------------------------------
//Imports
import java.util.Comparator;
import java.util.Random;
//BinerySearch class definition
public class BinarySearchTree> {
protected BinaryNode root; //Instance variable to store root
public BinarySearchTree() { //Constructor to initialize binary tree
root = null;
}
public void empty() { // This fuction will clear the binary tree
root = null;
}
public boolean isEmpty(){ //CHecks whether the tree is empty or not
return root == null;
}
public BinaryNode getRoot(){ //Returns root element
return root;
}
public int height() { //Calls height funtion and returns the result
return height(root);
}
protected int height(BinaryNode root) { //Private method to calculate height
if(root == null) {
return -1;
}
else {
return Math.max(height(root.getLeft()), height(root.getRight())) + 1;
}
}
public boolean contains(T data){//Calls contains overloaded method and returns result
return contains(data, root);
}
//Checks whether an element present in the binary search tree or not
protected boolean contains(T data, BinaryNode root){
if(root == null){
return false;
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0){
return contains(data, root.getLeft());
}
else if(compareResult < 0){
return contains(data, root.getRight());
}
else{
return true;
}
}
public T findMin() { //Call findMin overloaded method and returns the result
BinaryNode node = findMin(root);
return node == null ? null : node.getData();
}
protected BinaryNode findMin(BinaryNode root) {//Returns the smallest element of the binary tree
if(root == null) {
return null;
}
else if(root.getLeft() == null) {
return root;
}
else {
return findMin(root.getLeft());
}
}
public T findMax() { //Calls findMax overloaded method and returns the result
BinaryNode node = findMax(root);
return node == null ? null : node.getData();
}
//Calls maximum element in the binary tree
protected BinaryNode findMax(BinaryNode root) {
if(root == null) {
return null;
}
else if(root.getRight() == null) {
return root;
}
else {
return findMin(root.getRight());
}
}
//Calls insert overloded method to insert the element
public void insert(T data) {
root = insert(data, root);
}
//Inserts an element into the binary search tree
protected BinaryNode insert(T data, BinaryNode root) {
if(root == null) {
return new BinaryNode<>(data);
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0) {
root.setLeft(insert(data, root.getLeft()));
}
else if(compareResult < 0) {
root.setRight(insert(data, root.getRight()));
}
return root;
}
public void remove(T data) {//Calls remove overloaded method
root = remove(data, root);
}
//Removes the element given to this fuction
protected BinaryNode remove(T data, BinaryNode root) {
if(root == null) {
return null;
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0) {
root.setLeft(remove(data, root.getLeft()));
}
else if(compareResult < 0) {
root.setRight(remove(data, root.getRight()));
}
else if(root.getLeft() != null && root.getRight() != null) {
root.setData(findMin(root.getRight()).getData());
root.setRight(remove(root.getData(), root.getRight()));
}
else {
root = root.getLeft() != null ? root.getLeft() : root.getRight();
}
return root;
}
public void printTree() {//Calls printTree overloaded method
printTree(root);
}
//Function that prints all the elements of the binary tree
protected void printTree(BinaryNode root) {
if(root != null) {
printTree(root.getLeft());
System.out.println(root.getData());
printTree(root.getRight());
}
}
}
---------------------------------------------------------------
//Class to definition of Node
public class BinaryNode>
{
//Instance variables
private T data;
private int height;
private BinaryNode left;
private BinaryNode right;
//Constructor to initialize the variables
public BinaryNode(T data)
{
this(data, null, null);
}
//Overloaded constructor
public BinaryNode(T data, BinaryNode left, BinaryNode right)
{
this.data = data;
this.left = left;
this.right = right;
this.height = 0;
}
//Nethod to get the data at some node
public T getData()
{
return data;
}
//Method to set the data at some node
public void setData(T data)
{
this.data = data;
}
//Method to get left pointer of a node
public BinaryNode getLeft()
{
return left;
}
//Method to set the left pointer
public void setLeft(BinaryNode left)
{
this.left = left;
}
//Method to get right pointer
public BinaryNode getRight()
{
return right;
}
//Method to set right pointer
public void setRight(BinaryNode right)
{
this.right = right;
}
//Method to return height of the tree
public int getHeight()
{
return height;
}
//Method to set the height of the tree.
public void setHeight(int height)
{
this.height = height;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.