最近在学习树，遇到了AVL树。我在学习这些概念时参考了 YouTube 上的 Kunal Kushwaha。我已经在下面的代码中实现了 AVL 树，我正在粘贴我的完整 AVL java 类
问题是当我尝试通过 Main 方法向树中添加 1000 个元素（值）时，高度应该为 3，因为高度为 log(n) -> log (1000) -> 3 但我得到12 作为输出而不是 3，但在 Kunal 的视频中，他实现的代码产生了 3，而我几乎实现了相同的代码却得到了不同的输出。我花了两个小时找出错误所在，但找不到任何错误。我什至提到了 ChatGPT 但我没用。非常感谢您帮助找出错误。
我发布了下面的 2 个代码
public class AVL_Trees {
//i dont know why code when i insert 1000 elements
//expected height is 3 but i get 12 i tried via ChatGPT and cross checked my self but still can't find the solution on where the error is
//post on reddit or stackoverflow
private class Node{
private int value;
private Node left;
private Node right;
private int height;
public Node(int value){
this.value = value;
}
public int getValue() {
return value;
}
}
private Node root;
public AVL_Trees(){} //constructor
public int height() {
return height(root);
}
public int height(Node node) { //helper function
if (node == null) {
return -1;
}
return node.height;
}
public boolean isEmpty(Node node){
return node == null;
}
public void prettyDisplay(){
prettyDisplay(root,0);
System.out.println("Height "+height(root));
}
private void prettyDisplay(Node node,int level){
if(node == null){
return;
}
prettyDisplay(node.right,level+1);
if(level!=0){
for(int i=0;i<level;i++){
System.out.print("|\t\t");
}
System.out.println("|--->" + node.value);
}
else {
System.out.println("|--->" + node.value);
}
prettyDisplay(node.left,level+1);
}
public void insert(int value){
root = insert(root,value);
}
private Node insert(Node node, int value){
if(node==null){
return new Node(value);
}
if(value < node.value){
node.left = insert(node.left,value);
}
if(value > node.value){
node.right = insert(node.right,value);
}
node.height = Math.max(height(node.left),height(node.right)) + 1;
return rotate(node);
}
//for arrays as input
public void populate(int[] nums){
for(int i : nums){
insert(i);
}
}
public void populateSorted(int[] nums){ //incase if input array is sorted
populateSorted(nums,0, nums.length);
}
private void populateSorted(int[] nums,int start,int end){
if(start>=end){
return;
}
int mid = start + (end - start)/2;
insert(nums[mid]);
populateSorted(nums,0,mid);
populateSorted(nums,mid+1,end);
}
public boolean balanced(){
return balanced(this.root);
}
private boolean balanced(Node node){
if(node == null){
return true;
}
// condition for balance is both child node's height difference
//should be less than or equal to 1
return Math.abs(height(node.left) - height(node.right)) <=1 && balanced(node.left) && balanced(node.right);
}
public void display(){
display(root,"The root Node is ");
}
private void display(Node node , String details){ //just a way of representing
if(node == null){
return;
}
System.out.println(details + node.value);
display(node.left,"The left node of "+node.value+" is: ");
display(node.right,"The right node of "+node.value+" is: ");
}
private Node rotate(Node node){
if(height(node.left) - height(node.right) > 1){
//left heavy
if(height(node.left.left) - height(node.left.right) > 0 ){
//put 0, not 1 or -1 think about it!
//left-left case
return rightRotate(node);
}
if(height(node.left.left) - height(node.left.right) < 0){
//left-right case
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if(height(node.left) - height(node.right) < -1){
//right heavy
if(height(node.right.left) - height(node.right.right) < 0){
//right-right case
return leftRotate(node);
}
if(height(node.right.left) - height(node.right.right) > 0){
//right-left case
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
private Node rightRotate(Node p){
Node c = p.left;
Node t = c.right;
c.right = p;
p.left = t;
//updating heights
p.height = Math.max(height(p.left),height(p.right))+1;
c.height = Math.max(height(c.left),height(c.right))+1;
return c;
}
private Node leftRotate(Node c){
Node p = c.right;
Node t = p.left;
p.left = c;
c.right = t;
//updating heights
p.height = Math.max(height(p.left),height(p.right))+1;
c.height = Math.max(height(c.left),height(c.right))+1;
return p;
}
}
2.Kunal的正确代码：
//this is the correct code for AVL tree where it can balance and height is 3 when adding 1000 elements
public class KunalAVL {
public class Node {
private int value;
private Node left;
private Node right;
private int height;
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
private Node root;
public KunalAVL() {
}
public int height() {
return height(root);
}
private int height(Node node) {
if (node == null) {
return -1;
}
return node.height;
}
public void insert(int value) {
root = insert(value, root);
}
private Node insert(int value, Node node) {
if (node == null) {
node = new Node(value);
return node;
}
if (value < node.value) {
node.left = insert(value, node.left);
}
if (value > node.value) {
node.right = insert(value, node.right);
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
return rotate(node);
}
private Node rotate(Node node) {
if (height(node.left) - height(node.right) > 1) {
// left heavy
if(height(node.left.left) - height(node.left.right) > 0) {
// left left case
return rightRotate(node);
}
if(height(node.left.left) - height(node.left.right) < 0) {
// left right case
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if (height(node.left) - height(node.right) < -1) {
// right heavy
if(height(node.right.left) - height(node.right.right) < 0) {
// right right case
return leftRotate(node);
}
if(height(node.right.left) - height(node.right.right) > 0) {
// left right case
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
public Node rightRotate(Node p) {
Node c = p.left;
Node t = c.right;
c.right = p;
p.left = t;
p.height = Math.max(height(p.left), height(p.right) + 1);
c.height = Math.max(height(c.left), height(c.right) + 1);
return c;
}
public Node leftRotate(Node c) {
Node p = c.right;
Node t = p.left;
p.left = c;
c.right = t;
p.height = Math.max(height(p.left), height(p.right) + 1);
c.height = Math.max(height(c.left), height(c.right) + 1);
return p;
}
public void populate(int[] nums) {
for (int i = 0; i < nums.length; i++) {
this.insert(nums[i]);
}
}
public void populatedSorted(int[] nums) {
populatedSorted(nums, 0, nums.length);
}
private void populatedSorted(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
this.insert(nums[mid]);
populatedSorted(nums, start, mid);
populatedSorted(nums, mid + 1, end);
}
public void display() {
display(this.root, "Root Node: ");
}
private void display(Node node, String details) {
if (node == null) {
return;
}
System.out.println(details + node.value);
display(node.left, "Left child of " + node.value + " : ");
display(node.right, "Right child of " + node.value + " : ");
}
public boolean isEmpty() {
return root == null;
}
public boolean balanced() {
return balanced(root);
}
private boolean balanced(Node node) {
if (node == null) {
return true;
}
return Math.abs(height(node.left) - height(node.right)) <= 1 && balanced(node.left) && balanced(node.right);
}
}
当我尝试通过 Main 方法向树中添加 1000 个元素（值）时，高度应该是 3
请注意，在高度为 3 的二叉树（即 AVL）中，您只能容纳最 15 个元素。
对于高度1，最多可以存储3个节点。对于高度 2，即 7 个节点，对于高度 3，最大值为 15：
height=1 height=2 height=3
O O ____O____
/ \ / \ / \
O O O O O O
/ \ / \ / \ / \
O O O O O O O O
/ \ / \ / \ / \
O O O O O O O O
显然你无法在高度为 3 的二叉树中存储 1000 个元素。
...因为高度是 log(n) -> log (1000) -> 3 但我得到 12 作为输出而不是 3
您似乎误解了 log𝑛 的意图。它不是 log10𝑛，而是 log2𝑛。更准确地说，𝑛 节点的 AVL 树可以具有的最大高度以 1.44 log2𝑛为界。
如果你有一个有 1000 个节点的 AVL 树，它的高度可能高达 13。
但在 Kunal 的视频中，他实现的代码产生了 3
那是因为您作为 Kunal 的代码提供的代码存在错误。事实上它输出了 3，但如上所示，这不可能是正确的。
您提供的第二个版本在旋转功能
leftRotaterightRotatemaxp.height = Math.max(height(p.left), height(p.right) + 1);
// ^^^^^^
...而 1 应该添加到 max 调用的
result中。在您提供的第一个版本中，这是正确完成的（对您有好处！）。
两个版本的代码中
leftRotateleftRotatepcleftRotatecp因此将其修复为：
private Node leftRotate(Node c){
Node p = c.right;
Node t = p.left;
p.left = c;
c.right = t;
//updating heights: *** but first C!!!!
c.height = Math.max(height(c.left),height(c.right))+1;
p.height = Math.max(height(p.left),height(p.right))+1;
return p;
}
注意：在
rightRotate当我将数字 1 到 1000 按排序顺序插入到树中时，报告的高度为 9，这完全没问题。这意味着树已尽可能保持平衡。按随机顺序插入，高度大部分为 11...这符合预期。