未正确旋转AVL树,JAVA
这是我的作业
编写一个Java类,该类使用AVL树来存储泛型值和键
方法
- 建造师
- 列表项
- 插入
- 删除
- 查找键的值
- InOrder-按顺序返回值的数组
- PostOrder-返回一个数组,其中的值按PostOrder顺序排列
- PreOrder-返回一个数组,数组中的值按预排序
- 使用包含键和值的内部节点类李>
- 对遍历返回的数组使用ArrayList李>
我想我已经有了基本的想法,但是我的树没有得到正确的平衡。此外,inorder、preorder和postored也在工作中,在实现ArrayList之前,我会尝试确保其排序正确
任何帮助或修复都将是巨大的。这是我到目前为止所拥有的
public class AVLTree {
Node root;
public class Node{ //subclass of Node in AVL tree
private Node left;
private Node right;
int height = 1;
int key;
public Node(int n)
{
this.key = n;
height = 1;
}
}
public int height(Node n){
if(n == null)
return 0;
return n.height;
}
public void in(int key)
{
root = insert(root, key);
}
public Node insert(Node node, int key) //insert
{
if(node == null)
{
node = new Node(key);
}
else if(key < node.key)
{
node.left = insert(node.left, key);
if(height(node.left)- height(node.right) == 2) {
if(key < node.left.key)
{
node = rotateLeft(node);
}
else {
node.left = rotateRight(node.left);
rotateLeft(node);
}
}
}
else if(key > node.key)
{
node.right = insert(node.right, key);
if(height(node.right)- height(node.left) == 2) {
if(key < node.right.key)
{
node = rotateRight(node);
}
else {
node.right = rotateLeft(node.right);
rotateRight(node);
}
}
}
else {
node.height = Math.max(height(node.left), height(node.right)) + 1; //increase height of the node
}
return node;
}
public Node delete(Node root, int key) {
if(root == null)
return root;
Node temp;
if (key < root.key) {
root.left = delete(root.left, key);
}
else if(key > root.key) {
root.right = delete(root.right,key);
}
else if(key == root.key){
if(root.left == null || root.right == null){ //root has one child
if(root.left != null)
temp = root.left;
else
temp = root.right;
if( temp == null) { // no child
temp = root;
root = null;
}
else
root = temp;
temp = null;
}
else {
temp = minNode(root.right);
root.key = temp.key;
root.right = delete(root.right, temp.key);
}
}
if(root == null)
return root;
root.height = Math.max(height(root.left), height(root.right)) + 1;
//once deleted we must rebalance it
int balance = height(root.left) - height(root.right); //check balance of top node
if(balance > 1 && key < root.left.key) //left left rotation
return rotateRight(root);
else if(balance < -1 && key > root.right.key) //right right
return rotateLeft(root);
else if(balance > 1 && key > root.left.key) //left righ
return rotateRight(root);
else if(balance > -1 && key < root.right.key) //right left
return rotateRight(root);
return root;
}
private Node rotateLeft(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y; //rotates
x.height = Math.max(height(x.left), height(x.right))+1;
y.height = Math.max(height(y.left), height(y.right))+1;
return x;
}
private Node rotateRight(Node x)
{
Node y = x.right;
x.right = y.left;
y.left = x; //rotates
x.height = Math.max(height(x.left), height(x.right))+1;
y.height = Math.max(height(y.left), height(y.right))+1;
return y;
}
void TpreOrder(Node node)
{
if (node != null)
{
System.out.print(node.key + " ");
TpreOrder(node.left);
TpreOrder(node.right);
}
}
void TpostOrder(Node node)
{
if (node != null)
{
TpreOrder(node.left);
TpreOrder(node.right);
System.out.print(node.key + " ");
}
}
public void TinOrder(Node root)
{
if(root != null) {
TinOrder(root.left);
System.out.print(root.key+" ");
TinOrder(root.right);
}
}
public void inOrder(Node root, ArrayList<Integer> pre)
{
if(root != null) {
inOrder(root.left, pre);
pre.add(root.key);
pre.add(root.key);
inOrder(root.right, pre);
}
}
public ArrayList<Integer> toArray() {
ArrayList<Integer> result = new ArrayList<Integer>();
inOrder(root, result);
return result;
}
public void preOrder(Node root, ArrayList<Integer> in)
{
if(root != null) {
preOrder(root.left, in);
in.add(root.key);
preOrder(root.right, in);
}
}
public void postOrder(Node root, ArrayList<Integer> post)
{
if(root != null) {
postOrder(root.right, post);
post.add(root.key);
postOrder(root.left, post);
}
}
private Node minNode(Node node) {
Node cur = node;
while(cur.left != null)
cur = cur.left;
return cur;
}
}
# 1 楼答案
也许这会帮助你:
重新计算树的高度:
返回平衡因子:
平衡节点: