Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
computers:arduino:avl_tree [23-May-2019 12:04] – Steve Joyntcomputers:arduino:avl_tree [02-Feb-2025 16:14] (current) – external edit 127.0.0.1
Line 1: Line 1:
 ====== AVL Tree ====== ====== AVL Tree ======
 +
 +This is currently a work in progress. Some source has been released, but it still needs some work. See the end of the page for details.
  
 As always on the Arduino platform, the library would need to use as little memory and program space as possible. The SD card memory is a solid state device, so accessing a file in random order does not add a significant amount of time to the process, although the link between the SD card and the Arduino is relatively slow, and there is no caching on the Arduino side to speed things up. As always on the Arduino platform, the library would need to use as little memory and program space as possible. The SD card memory is a solid state device, so accessing a file in random order does not add a significant amount of time to the process, although the link between the SD card and the Arduino is relatively slow, and there is no caching on the Arduino side to speed things up.
Line 5: Line 7:
 What we need is a quick algorithm for finding one item in a large list. What we need is a quick algorithm for finding one item in a large list.
  
-Choose a number between 1 and 1000. What if I bet you $1000 that I can discover your number by asking you no more than ten questions? Obviously my first question would be "what is your number?". But now we restrict my questions to simply guessing a number, and your reply to be "higher", "lower", or "yes". Would I still be guaranteed to win in ten guesses or less? Surprisingly, I would win every time (assuming you always told the truth). +Choose a number between 1 and 1000. What if I bet you $1000 that I can discover your number by asking you no more than ten questions? Obviously my first question would be "what is your number?" LOL. But now we restrict my questions to simply guessing a number, and your reply will be "higher", "lower", or "yes". Would I still be guaranteed to win in ten guesses or less? Surprisingly, I would win every time (assuming you always told the truth). 
  
 It's difficult to find a needle in a haystack, but if the haystack is half the size, the task is twice as easy. So my first guess will be "is it 500?" and depending on your answer, my next guess will be 250 or 750. Each time I guess, I eliminate half as many possibilities as the previous guess, as I "home in" on your number. So in ten guesses I can check 2x2x2x2x2x2x2x2x2x2 possibilities, which is two to the power of ten, or 1024. It's difficult to find a needle in a haystack, but if the haystack is half the size, the task is twice as easy. So my first guess will be "is it 500?" and depending on your answer, my next guess will be 250 or 750. Each time I guess, I eliminate half as many possibilities as the previous guess, as I "home in" on your number. So in ten guesses I can check 2x2x2x2x2x2x2x2x2x2 possibilities, which is two to the power of ten, or 1024.
Line 15: Line 17:
 Wikipedia has a nice description of [[https://en.wikipedia.org/wiki/AVL_tree|AVL Trees]], and enough pseudo code to get me started along the right path. Wikipedia has a nice description of [[https://en.wikipedia.org/wiki/AVL_tree|AVL Trees]], and enough pseudo code to get me started along the right path.
  
 +The first version of the library is now {{:arduino:avl_tree.zip|available to download}}. You can find the documentation (such as it is) in the header file. There's no proper documentation yet, and no examples of how to use it. This is a pre-alpha release, and is not intended to be used for anything other than experimentation. Do not store important data using it, it will very probably break and you'll lose it.
  • computers/arduino/avl_tree.1558613093.txt.gz
  • Last modified: 02-Feb-2025 16:12
  • (external edit)