BST Algorithm

I am trying to design an algorithm that will remove the second largest value from a Binary Search Tree with time of O(height). Can anyone give me some insight witht this? It doesn't seem like it should be that hard but I think I am just hitting a mental block.

[268 byte] By [mdorison@a] at [2007-10-2 5:05:00]

«« How to create bookmarks by using J2ME
»» how to make code more understandable?

# 1

remove 1stremove 2ndre-add 1storimplement getNextSmallest method and getLargest methodx = getLargest();remove(getNextSmallest(x));

rkippena at 2007-7-16 1:08:27 >

top of Java-index,Other Topics,Algorithms...

# 2

First off, thank you for the input!I don't think the first will do exactly what I want because it won't preserve the original formation of the BST. The second I believe should work though I am not positive that its time is O(height). Is it?

mdorison@a at 2007-7-16 1:08:27 >

# 3

Actually, the first should work because the actual structure of the tree is not going to matter to me but is that definately O(height)?

mdorison@a at 2007-7-16 1:08:27 >

# 4

Remove first is clearly O(height) and doesn't increase the height. Remove second is really a second remove first, so is also O(height). Add first is again O(height). So yes.

YAT_Archivista at 2007-7-16 1:08:27 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

BST Algorithm

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified