感觉avl tree的插入不是O(lgn)啊# JobHunting - 待字闺中
l*a
1 楼
复习data structure时,发现插入后做rebalance需要height。网上能找到的getHeight
()函数的时间复杂度是O(n)的。插入不可能做到O(lgn)。
public int getHeight ()
{
if (this.leftChild == null && this.rightChild == null)
{
return 0;
}
else
{
int leftH = 0;
int rightH = 0;
if (this.leftChild != null)
{
leftH++;
leftH += this.getLeftChild().getHeight();
}
if (this.rightChild != null)
{
rightH++;
rightH += this.getRightChild().getHeight();
}
return Math.max(leftH,rightH);
}
}
()函数的时间复杂度是O(n)的。插入不可能做到O(lgn)。
public int getHeight ()
{
if (this.leftChild == null && this.rightChild == null)
{
return 0;
}
else
{
int leftH = 0;
int rightH = 0;
if (this.leftChild != null)
{
leftH++;
leftH += this.getLeftChild().getHeight();
}
if (this.rightChild != null)
{
rightH++;
rightH += this.getRightChild().getHeight();
}
return Math.max(leftH,rightH);
}
}