感觉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);
}
}