1,105,380 Community Members

What are the differences between an AVL tree and a Btree

Member Avatar
UberJoker
Junior Poster in Training
76 posts since Oct 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 6 [?]
Skill Endorsements: 0 [?]
 
-1
 

Hey guys. Last week I programmed a AVL tree. This week i am trying to build a Btree. Can someone explain the differences between a AVL tree and a Btree. They seem kind of similar in the sense that both need balancing, but how different are they when it comes to coding them? Can I possibly just modify my AVL tree code and make it a Btree? Any suggestion would be much appreciated. Thanks.

Member Avatar
bamcclur
Newbie Poster
20 posts since Nov 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 4 [?]
Skill Endorsements: 0 [?]
 
0
 

Well, Btrees can have more than two paths spanning from each node, so I think you could generally use your AVL tree, and do some modifications to it. Why not do some reading on how to balance your Btree http://en.wikipedia.org/wiki/Btree

Member Avatar
UberJoker
Junior Poster in Training
76 posts since Oct 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 6 [?]
Skill Endorsements: 0 [?]
 
-1
 

I have already read that...my question was can somebody point out the exact differences between the two and where the modifications need to be done in an AVL tree to make it a Btree.

Member Avatar
Nick Evan
Industrious Poster
4,827 posts since Oct 2006
Reputation Points: 4,005 [?]
Q&As Helped to Solve: 560 [?]
Skill Endorsements: 30 [?]
Team Colleague
Featured
 
0
 
Member Avatar
Narue
Bad Cop
12,139 posts since Sep 2004
Reputation Points: 5,693 [?]
Q&As Helped to Solve: 1,537 [?]
Skill Endorsements: 81 [?]
Team Colleague
 
0
 

>They seem kind of similar in the sense that both need balancing,
>but how different are they when it comes to coding them?

Barring the fact that they're both trees and they're both balanced, AVL and B-Trees are quite different. The biggest difference is that B-Trees usually have a higher order than AVL trees (which are generally strictly binary). B-Trees are generally external data structures rather than internal because the node structure is well-suited to more expensive access of secondary storage.

The balancing algorithms are very different as well. Rather than storing balance factors and rotating, B-Trees use a fill-factor (how much of the node is full) and then split or merge adjacent nodes accordingly.

>Can I possibly just modify my AVL tree code and make it a Btree?
Not really. You'll find it easier to start from scratch with a B-Tree rather than convert an AVL tree to a B-Tree...

Member Avatar
UberJoker
Junior Poster in Training
76 posts since Oct 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 6 [?]
Skill Endorsements: 0 [?]
 
0
 

I was trying to find a good explanation online as to how to code a Btree but I coudnt find anything ....can you possibly direct me to a good source to begin.

Member Avatar
Nick Evan
Industrious Poster
4,827 posts since Oct 2006
Reputation Points: 4,005 [?]
Q&As Helped to Solve: 560 [?]
Skill Endorsements: 30 [?]
Team Colleague
Featured
 
0
 

I was trying to find a good explanation online as to how to code a Btree but I coudnt find anything ....can you possibly direct me to a good source to begin.

You didn't click the link I gave you right?

Member Avatar
Narue
Bad Cop
12,139 posts since Sep 2004
Reputation Points: 5,693 [?]
Q&As Helped to Solve: 1,537 [?]
Skill Endorsements: 81 [?]
Team Colleague
 
0
 

>You didn't click the link I gave you right?
You mean the link to my AVL tree tutorial? Yea, that's a real good B-Tree resource... :icon_rolleyes:

p.s. A B-Tree tutorial is on my list, but I haven't written anything for it yet.

Member Avatar
Nick Evan
Industrious Poster
4,827 posts since Oct 2006
Reputation Points: 4,005 [?]
Q&As Helped to Solve: 560 [?]
Skill Endorsements: 30 [?]
Team Colleague
Featured
 
0
 

>You didn't click the link I gave you right?
You mean the link to my AVL tree tutorial? Yea, that's a real good B-Tree resource... :icon_rolleyes:

Well, err, yeah... I guess my brain misfired, sorry 'bout that one. :icon_sad:

Member Avatar
dilkash
Newbie Poster
1 post since Oct 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

luv u dear ma sweet heart muuuuaaaaaaaaaaahhhhhhhhhhhhhhh..........

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article