感觉avl tree的插入不是O（lgn）啊 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 感觉avl tree的插入不是O（lgn）啊

相关主题
● 请问一个简单的面试题	● 问个算法题
● 弱问怎么判断两个binary tree相同？	● 问个复杂度的初级问题
● 如何计算recursion的空间复杂度	● 扔鸡蛋的问题
● 算法题：如何判断二叉树是AVL？	● Google校园面试题
● G的一道考题	● FB两次电面
● how to solve this google interview question	● 贡献一个NV的verification面经
● 也问一个median的问题	● 问到G家题
● 请教一道Amazon面世题	● 问个问题post order traveral using interation

相关话题的讨论汇总
话题: getheight话题: lefth话题: righth话题: null话题: 插入

进入JobHunting版参与讨论

1

(共1页)

l*****a 发帖数: 559	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); } }
a********m 发帖数: 15480	2 高度可以存在结点上。
e*****r 发帖数: 93	3 getHeight复杂度是O(lgN)还有可以插入的时候就顺便更新了

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 问个问题post order traveral using interation	● G的一道考题
● 问到linked list 的题目	● how to solve this google interview question
● 一道老题	● 也问一个median的问题
● 讨论下面试题的难度分布？	● 请教一道Amazon面世题
● 请问一个简单的面试题	● 问个算法题
● 弱问怎么判断两个binary tree相同？	● 问个复杂度的初级问题
● 如何计算recursion的空间复杂度	● 扔鸡蛋的问题
● 算法题：如何判断二叉树是AVL？	● Google校园面试题

相关话题的讨论汇总
话题: getheight话题: lefth话题: righth话题: null话题: 插入

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)