0
Привет, ребята, я пытался реализовать дерево AVL, но не удалось. Я практикую, чтобы получить концепцию. Пока мне удалось вставить дерево, получить высоту дерева, проверить, сбалансировано ли оно, количество узлов в дереве, найти значения min и Max в трех и проверить, находится ли значение в дереве. Теперь я пытаюсь сбалансировать дерево, вставляя новый узел в дерево, но не добившись успеха. Пожалуйста, не могли бы вы посоветовать мне, в чем я ошибся. Ниже мой код с моим результатом. Пожалуйста, имейте и спасибо. Ниже мой класс узел: BinaryNode.javaПроблема с созданием дерева avl в java
public class BinaryNode<T> {
private T data;
private BinaryNode<T> rightChild;
private BinaryNode<T> leftChild;
public BinaryNode(){}
public BinaryNode(T data){
this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> leftChild, BinaryNode<T> rightChild){
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public void setLeftChild(BinaryNode<T> leftChild){
this.leftChild = leftChild;
}
public void setRightChild(BinaryNode<T> rightChild){
this.rightChild = rightChild;
}
public BinaryNode<T> getRightChild() {
return rightChild;
}
public BinaryNode<T> getLeftChild() {
return leftChild;
}
public T getData(){
return data;
}
public int Height(){
return getHeight(this);
}
//returns the height of the tree
private int getHeight(BinaryNode<T> root){
if(root == null){
return -1;
}
else
return 1+Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()));
}
//functions get the number of nodes availabe in the tree
protected int getNumberOfNodes(){
int a=0,b=0;
if(leftChild!=null){
a = leftChild.getNumberOfNodes();
}
if(rightChild!=null){
b = rightChild.getNumberOfNodes();
}
return a+b+1;
}
public void balance(){
balance(this);
}
private void balance(BinaryNode<T> root){
int balance = getHeight(root.getLeftChild())-getHeight(root.getRightChild());
if(balance>2){
if(getHeight(root.getLeftChild())>=getHeight(root.getRightChild())){
rotateRight(root);
}
else{
doubleRotateRight(root);
}
}
else if(balance<-2){
if(getHeight(root.getRightChild())>=getHeight(root.getLeftChild())){
rotateLeft(root);
}
else{
doubleRotateLeft(root);
}
}
else{
getHeight(root);
}
}
//right right rotation
private BinaryNode<T> rotateRight(BinaryNode<T> root){
BinaryNode<T> nodeA = root.getLeftChild();
root.setLeftChild(nodeA.getRightChild());
nodeA.setRightChild(root);
return nodeA;
}
//left left rotation
private BinaryNode<T> rotateLeft(BinaryNode<T> root){
BinaryNode<T> nodeA = root.getRightChild();
root.setRightChild(nodeA.getLeftChild());
nodeA.setLeftChild(root);
return nodeA;
}
//right left rotation
private BinaryNode<T> doubleRotateLeft(BinaryNode<T> root){
BinaryNode<T> nodeA = root.getLeftChild();
root.setRightChild(rotateRight(nodeA));
return rotateLeft(root);
}
//left right rotation
private BinaryNode<T> doubleRotateRight(BinaryNode<T> root){
BinaryNode<T> nodeA = root.getRightChild();
root.setLeftChild(rotateLeft(nodeA));
return rotateRight(root);
}
}
BinarySearchTree:
public class BinarySearchTree<T extends Comparable<? super T>> {
private BinaryNode<T> root;
public BinarySearchTree() {}
public BinarySearchTree(T data){
root = new BinaryNode<T>(data);
}
public void insert(T data){
BinaryNode<T> newNode = new BinaryNode<T>(data);
if(isEmpty()){
root = newNode;
}
else
insertElements(root, newNode);
}
private void insertElements(BinaryNode<T> root, BinaryNode<T> newNode){
if(newNode.getData().compareTo(root.getData())<0){
if(root.getLeftChild()==null){
root.setLeftChild(newNode);
}
else
insertElements(root.getLeftChild(), newNode);
//balance(root.getLeftChild());
}
else{
if(root.getRightChild()==null){
root.setRightChild(newNode);
}
else{
insertElements(root.getRightChild(), newNode);
//balance(root.getRightChild());
}
}
balance(root);
}
public void balance(BinaryNode<T> root){
root.balance();
}
public boolean isEmpty(){
return (root==null);
}
public void preOrder(){
preOrder(root);
}
private void preOrder(BinaryNode<T> root){
if(root == null){
return;
}
else{
System.out.println(root.getData());
preOrder(root.getLeftChild());
preOrder(root.getRightChild());
}
}
public int getHeight(){
return root.Height();
}
//gets the number of nodes in the tree
public int getNumberOfNodes(){
return root.getNumberOfNodes();
}
//returns true or false if tree is balanced
public boolean isBalanced(){
if(root==null){
return true;
}
if(checkHeight(root)==-1){
return false;
}
else{
return true;
}
}
//checks to see if the tree is balanced.
private int checkHeight(BinaryNode<T> root){
if(root==null){
return 0;
}
int left = checkHeight(root.getLeftChild());
int right = checkHeight(root.getRightChild());
if(left==-1||right==-1){
return -1;
}
if(Math.abs(left-right)>1){
return -1;
}
else
return Math.max(left, right)+1;
}
public T findMin(){
return findMin(root);
}
private T findMin(BinaryNode<T> root){
if(root==null){
return null;
}
else if(root.getLeftChild()==null){
return root.getData();
}
else
return findMin(root.getLeftChild());
}
public T findMax(){
return findMax(root);
}
private T findMax(BinaryNode<T> root){
if(root==null){
return null;
}
else if(root.getRightChild()==null){
return root.getData();
}
else return findMax(root.getRightChild());
}
public boolean contains(T entry){
return contains(root, entry);
}
private boolean contains(BinaryNode<T> root, T entry){
if(root == null){
return false;
}
else if(entry.compareTo(root.getData())<0){
return contains(root.getLeftChild(), entry);
}
else if(entry.compareTo(root.getData())>0){
return contains(root.getRightChild(), entry);
}
else{
if(entry.compareTo(root.getData())==0){
return true;
}
else
return false;
}
}
public void makeEmpty(){
this.root = null;
}
}
испытаний Класс:
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
tree.insert(5);
tree.insert(10);
tree.insert(20);
tree.preOrder(); //prints out the tree in a pre-order list
System.out.println("Height of tree: " +tree.getHeight());
System.out.println("Number of Nodes: "+tree.getNumberOfNodes());
System.out.println("Balanced: "+tree.isBalanced());
System.out.println("Find max: "+ tree.findMax());
System.out.println("Find min: "+tree.findMin());
System.out.println("Contains: "+tree.contains(1));
}
}
Ниже результат. Но я ошибаюсь, поскольку дерево не сбалансировано. Кажется, что-то не так. Поскольку каждый раз, когда я вставляю новый узел, я также уравновешиваю попытку сбалансировать дерево. Пожалуйста, может кто-то помочь мне и определить, что я делаю неправильно. Я извиняюсь, если код длинный. Результат:
5
10
20
Height of tree: 2
Number of Nodes: 3
Balanced: false
Find max: 20
Find min: 5
Contains: false