Danny said:
Today I decided I'd talk about Binary trees, and I apologize in advance, my week this week is again going to be pretty busy.
What is a binary tree? It is a type of data structure that generally will take on an "upside down" tree shape. Entries in a binary tree are called nodes, and each node will have at most two children nodes. (Hence the name binary tree).
One of the common uses is to have a binary search tree, where the nodes are ordered in some fashion. Say, larger elements go to the right side, and smaller elements go the left side. By example, lets say I have the following numbers:
5,3,7,8,1,9,10, and 4.
Then if we place our numbers into the tree in the order they are listed we get a tree that looks like:
5
/ \
/ \
/ \
3 7
/ \ / \
1 4 8
/ \
9
/ \
10
This particular tree would be unbalanced, because one side is longer by more than one level than the other side, but, the advantage of searching a binary tree in general is that, if I were looking for the number 8, then I'd only need to look down the right portion of the tree tree to find it, as I know that 8 is larger than 5. So I can cut my search times in half based on the number of elements in the tree, assuming a perfectly balanced tree.
Generally though, the runtime of the tree will following a function like n log n.
Generally you'll find useful functions of a binary tree to be: insert, remove, find, and a reordering type of method, which will balance the tree out.
Other types of trees include: red-black trees, AVL trees, splay trees, and several others.
Next time I'll talk about skip lists a little bit.
What is a binary tree? It is a type of data structure that generally will take on an "upside down" tree shape. Entries in a binary tree are called nodes, and each node will have at most two children nodes. (Hence the name binary tree).
One of the common uses is to have a binary search tree, where the nodes are ordered in some fashion. Say, larger elements go to the right side, and smaller elements go the left side. By example, lets say I have the following numbers:
5,3,7,8,1,9,10, and 4.
Then if we place our numbers into the tree in the order they are listed we get a tree that looks like:
5
/ \
/ \
/ \
3 7
/ \ / \
1 4 8
/ \
9
/ \
10
This particular tree would be unbalanced, because one side is longer by more than one level than the other side, but, the advantage of searching a binary tree in general is that, if I were looking for the number 8, then I'd only need to look down the right portion of the tree tree to find it, as I know that 8 is larger than 5. So I can cut my search times in half based on the number of elements in the tree, assuming a perfectly balanced tree.
Generally though, the runtime of the tree will following a function like n log n.
Generally you'll find useful functions of a binary tree to be: insert, remove, find, and a reordering type of method, which will balance the tree out.
Other types of trees include: red-black trees, AVL trees, splay trees, and several others.
Next time I'll talk about skip lists a little bit.
Vaughn Tolle said:
DOJ "approves" immunity deal with the current Monica, to be presented to the Court Friday for its approval and order.
http://www.washingtonpost.com/wp-dyn/content/artic...
http://www.washingtonpost.com/wp-dyn/content/artic...
Vaughn Tolle said:
Binary searches; very efficient, in my limited experience.
Danny, good try on the visual on the tree; I don't know how to help with this, or I would, given you are busy (as am I, but could work it out over lunch if I had a clue...)
Danny, good try on the visual on the tree; I don't know how to help with this, or I would, given you are busy (as am I, but could work it out over lunch if I had a clue...)
Vaughn Tolle said:
Simplistic example of a binary search, not involving a tree (Danny reminded me of this). We used to play a game with our girls, they would pick a number between 1 and 100, with parents guessing. The rule was, once the guess was made, the "number picker" had to say "higher" or "lower" until the number was ascertained. Thus, the first guess would be 50; assuming the response was lower, the next would be 25; and so on, essentially dividing the remaining possibilities in half each time until the answer was apparent.
Danny said:
Vaughn,
That is pretty much true, in a balanced tree, that as you navigate the tree you cut your search in half. However, in worst case, you could have a tree where all the elements follow only one branch, thus have a linear traversal time. On average, a binary tree would have a n log n search time, which is pretty decent.
That is pretty much true, in a balanced tree, that as you navigate the tree you cut your search in half. However, in worst case, you could have a tree where all the elements follow only one branch, thus have a linear traversal time. On average, a binary tree would have a n log n search time, which is pretty decent.
Vaughn Tolle said:
Danny, I think I understand the worst case, as I managed to venture there once when doing some "just for fun" coding. As you say, the average search time on a binary tree is pretty decent. I am enjoying your "lessons", BTW.
lindainks55 said:
Danny, I'm here listening. You would need to start with more basic than your mind could go to bring me up to speed. Not that I couldn't learn, more like I choose not to apply myself. I'm a bum and have to be really interested before I'm willing to put in the effort. But, I am tickled pink there are people like you in the world and I get to enjoy the fruits of your labors. ;-)
OK, I'll quit interrupting. Cary on you smart guys!
OK, I'll quit interrupting. Cary on you smart guys!
Rox said:
Way, WAY over my head, too, Linda. You see, there were numbers in his first post...
Yes, yes. Dum(b) de dum(b). <---me and math
Yes, yes. Dum(b) de dum(b). <---me and math
gster said:
Danny: RE On average, a binary tree would have a n log n search time, which is pretty decent. "
How is Th's result evaluated? Isn't it a function of the CPU speed?
How is Th's result evaluated? Isn't it a function of the CPU speed?
Julie said:
k, I'm trying to follow the binary tree explanation but you're lips are moving and all I hear is Charlie Brown's teachers voice.
I think this may be a left brain/right brain thing, or maybe it's a girl/guy thing. I know my hubby would pick up and run with this, understanding instantly.
I did understand VT's post at 12:26 (so I'm not completely lost).
:)
I think this may be a left brain/right brain thing, or maybe it's a girl/guy thing. I know my hubby would pick up and run with this, understanding instantly.
I did understand VT's post at 12:26 (so I'm not completely lost).
:)
Danny said:
Gster,
n log n represents running time ignoring specific machine characteristics. Meaning, a faster machine would be faster, because it can do processing more quickly, but how many times does it go through say a loop to process the tree? This is really what this particular equation would represent.
n then is the number of elements in the tree. As a result, I get an expected running time, which could then be applied to specific hardware.
Linda,
I could do something more simple. I just like to share some of the interesting topics, I could also go much more complicated(not my goal really). So perhaps next week I'll talk about a linked list, then talk about a skip list, would make more sense to do it in that order anyway.
n log n represents running time ignoring specific machine characteristics. Meaning, a faster machine would be faster, because it can do processing more quickly, but how many times does it go through say a loop to process the tree? This is really what this particular equation would represent.
n then is the number of elements in the tree. As a result, I get an expected running time, which could then be applied to specific hardware.
Linda,
I could do something more simple. I just like to share some of the interesting topics, I could also go much more complicated(not my goal really). So perhaps next week I'll talk about a linked list, then talk about a skip list, would make more sense to do it in that order anyway.
Loading....