 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Trees Part 2: Binary Trees |
|
 |
Gaiiden GDNet Content Lead Member since: 8/30/2000 From: Lincroft, NJ, United States |
|||
 Posted - 6/29/2001 4:01:04 PM |
||||
| wow, what a heap of info! I'm going to have to take some time to digest it all. Luckily I read through the trees chapter in LaMothe's Guru's book so this all makes some sense to me. Keep up the good work. ============================== "Need more eeenput..." - #5, "Short Circuit" ============================== |
||||
|
||||
 |
iwasbiggs Member since: 3/11/2000 From: CA, USA |
|||
 Posted - 6/29/2001 5:03:49 PM |
||||
| good show. Looking forward to the next article. |
||||
|
||||
|
Anonymous Poster |
|||
 Posted - 6/29/2001 10:01:20 PM |
||||
| I NJEEED HELP WITH THIS HOW DO I MAKE A GAME WITH THIS? WHERE DO I TYPE THIS IN TO USE IT? PLEASE HELP ME, NO ONE IS HEPLING ME I REALLY NEED HELP!! |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 6/30/2001 12:42:45 AM |
||||
Greetings, Just wanted to offer up my support on the article as a step in the right direction. Data structures are an important part of any good software engineer's arsenal. Great presentation. I did want to make a quick note about the notion of the "leftness" of a tree. Just as an FYI, there is a formal term for what you described. For a given binary tree T with the root situated at level 0, a tree is said to be "complete" if all nodes in the tree from level 0 to (n-1) are full and the remaining nodes of the tree at level n are filled in partially from left to the right. As an example:
O
/ \
O O
/ \
O O
Just like in your example in the article, the root is at level 0, level 1 is full and level 2 is filled in partially from left to right. |
||||
|
||||
|
Mithrandir Member since: 9/14/1999 |
|||
|
Posted - 6/30/2001 10:18:10 AM |
||||
| Ah, i knew there had to be a technical term somewhere! I've never actually seen it discussed in any of the books or tutorial's I've seen, but it is quite an important notion for arrayed tree's. Thanks for the info. I'll be sure to update the section on Heaps in the next article. |
||||
|
||||
|
Mithrandir Member since: 9/14/1999 |
|||
|
Posted - 6/30/2001 10:20:53 AM |
||||
quote: Yes, Lamothe's TOTWPG had a good basic introduction on trees. I felt that more in depth information was needed, and it kind of annoyed me how he kept referring to Binary Tree's as B-tree's (yes, I know the book's market was aimed at moderate level game programmers, not software engineers, heh). Interestingly enough, this particular article I had to split up into two pieces  |
||||
|
||||
|
Mithrandir Member since: 9/14/1999 |
|||
|
Posted - 6/30/2001 10:22:02 AM |
||||
quote: Thank you! I've already got all the source code worked out and 90% of the AVL section worked out too. |
||||
|
||||
|
zhang_zhou Member since: 11/27/2000 From: China |
|||
 Posted - 7/2/2001 9:39:01 AM |
||||
| Hey,a good article... And can you please give us more example(source code) on the actual games whose using the "tree" data structure in the coming one or more article? Thanks,anyway. ============================= Hey,I just wanna know WHY! ============================= |
||||
|
||||
|
Bobtree Member since: 8/1/2000 |
|||
|
Posted - 7/3/2001 3:03:42 PM |
||||
| there is a very cool and little known alternative to balanced binary trees called Skip Lists. they are not normal trees persay, but achieve the same effect via randomized insertion and probabilistic balancing. iirc, a worst case search is linear, but the odds of it are astronomical - and they average well and have very fast insert/delete, which is where they outperform a normal tree that would need constant re-balancing. also, a nice side effect is that the algorithms to operate on Skip Lists are typically much simpler than those for balanced trees. very cool stuff. check out the original paper at http://www.cs.umd.edu/~pugh/ |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 7/11/2001 3:15:33 PM |
||||
| I guess computer science has a lot of interpretation involved, because here is yet another interpretation of the two properties of heap trees called "fullness" and "leftness". The property of binary trees that you called "leftness" and someone else called "complete" is also known as "dense" in many other textbooks. Thus, a binary tree that is "dense" has the following properties: If the maximum tree depth is n (Where root is at depth 0), then at depth n-1: - There is only one node that has only one child, and that child is the node's left child. - All nodes with two children appear to the left of the node with one child or leaf nodes. - The node with only one child appears to the left of the leaf nodes. - Above the n-1 level, all nodes must have 2 children. I first saw this definition in the textbook _Introduction to Data Structures and Algorithms Analysis with C++_. In that textbook, "fullness" was also described slightly differently: -- A tree is "full" if all nodes with fewer than two children must occur at level n or n-1, where n is the deepest level of the tree.-- They used this definition consistently, so I assume that their definition is also valid. lieten lieten@dragonmount.com |
||||
|
||||
|
ALH Member since: 8/22/1999 From: Sao Paulo, SP, Brazil |
|||
|
Posted - 10/22/2001 3:39:25 PM |
||||
| I´ve got a nasty problem trying to instatialize a binary tree class inside another class. The problem is working straightly Object Oriented. When I try to create a tree with a specific object of mine, I am unable to create a void* function (functor) with a method! Anyone had a similar problem? And more likely a solution...  Thanks, Alan |
||||
|
||||
|
Mithrandir Member since: 9/14/1999 |
|||
|
Posted - 5/26/2002 3:44:43 PM |
||||
| Sorry for not completing the series, folks, but I've been a bit busy. I'm writing an entire book on Data Structures now, and I should have more details when I finish writing it this summer =). Stay tuned! |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 6/11/2002 8:13:30 PM |
||||
| The recursive removeFull() function can be massively simplified if you change its semantics and the semantics of removeNotFull() to NOT delete the removed node. Now when you find the largest left subtree node (l) you can simply call removeNotFull() on it, since we know it's not a full node, then relink it into x's position. The removeNotFull() function does all the work for us. This will only work if the remove functions don't delete the node but just detach them from the tree. You can of course then write another wrapper function that removes the node and then deletes it (to avoid mem leak). Please advise if my logic is bogus. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
