Talk:Lowest common ancestor

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Computer science (Rated Start-class)
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field:  Discrete mathematics

[untitled][edit]

@David Eppstein: the binary tree in my implementation doesn't have to be balanced (I know that pictures suggest that), as long as nodes have proper numbering. (This isn't big problem, since the depth of BT can be remembered while building BT and BT depth can be used to for calculation of node's number). GiM 18:47, 13 June 2007 (UTC)

It does have to be balanced (by which I mean, not necessarily a complete binary tree, but having relatively small depth) because, if I understand it correctly, the numbering you use assumes that the depth of the tree is less than the number of bits per word. —David Eppstein 19:55, 13 June 2007 (UTC)
If I understand you correctly, yes. The maximum depth of BT is number_of_bits_in_word - 1 (so that would be 31, which is rather small). That is definitely limitation. Thanks for clearing this out. —GiM 10:35, 14 June 2007 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified one external link on Lowest common ancestor. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

As of February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete the "External links modified" sections if they want, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{sourcecheck}} (last update: 15 July 2018).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.


Cheers.—InternetArchiveBot (Report bug) 17:39, 7 January 2018 (UTC)