data structures - AVL tree worst case number of rotations during insertion and deletion -


in avl tree, worst case number of rotations during insertion , deletion of n elements ?

i think insertion should o(n) , deletion should o(nlogn). however, not sure deletion .

am correct?

for both operations - inserting or deleting of node x, there cases require rotations made on nodes x root. since height of tree n nodes o(log n), worst case both operations take o(log n) rotations. n insert/delete operations gives o(n log n).


Comments

Post a Comment

Popular posts from this blog

sql - Time in datatime field -

i have field stores date , time need extract shows time shows date 01/01/1900 . i can extract time using below need include data of 01/01/1900 convert(varchar(12), w.created, 114) if using sql server, can do: select cast('1900-01-01' datetime) + cast(cast(w.created time) datetime) this returns value datetime . sql server has time data type. unclear why want add in fake date, can.
Read more

javascript - How to split the success output from an Ajax post? -

i have ajax post php file returns table on success. use whole success output fill div in main html page. pretty simple. however, result table huge , takes long display results @ once or fails(google chrome 'aw snap error'). so, split output , load user scrolls down. let's say, ajax success got 1000 results , want fill first 20 , display rest user scrolls down. $.ajax({ url:"xxxxxx.php", data: { xxxxxxxxx }, type: "post", success:function(result){ document.getelementbyid("cdr").innerhtml = result; }); you should 20 records each request. loading records not approach. imagine situation when result contains 1 million records? to so, in ajax's data setting, can add parameter called "page_number" , increase each ajax request javascript, on server processing (your .php file), take "page_number" parameter , process result ta...
Read more

java - sharing object across different classes -

i need "design" advise. have static jdbc objects , "main entry class" shared among other classes. my mainclass looks this: public static jdbc db1; public static jdbc db2; connectdb(makedirectconnection) // depending on runtime passed argument public static connectdb(boolean makedirectconnection) { if(makedirectconnection) // use direct connection db1 = jdbcfactory.getinstance("db/config/main/db1.properties"); db2 = jdbcfactory.getinstance("db/config/main/db2.properties"); } else { // connect using via ssh tunnel (different host , port) db1 = jdbcfactory.getinstance("db/config/tunnel/db1.properties"); db2 = jdbcfactory.getinstance("db/config/tunnel/db2.properties"); } jdbcfactory maintains map of instances. it kinda works ok, if want make unit test classes db1 or db2 being used null pointer exception if unit test don't mainclass.dbconnect() make thing worse - test classes need 1 more dif...
Read more