Page 1 of 1
Simple btree lib
Posted: Wed Mar 12, 2008 5:00 pm
by inx
Hello all. In a previous thread, I was asking about finding free PIDs, and through some divergence on a few tangents in the thread, it was recommended to me by a few to move away from linear searches.
Over the last day or so, I threw together a generic binary tree 'lib' that I'm using in my kernel's stdlib. The binary tree nodes store a numeric ID and a void * for attaching any data you might need associated with it (I use it for my task and memObject structs).
There are functions for adding, removing, and searching for nodes by ID, getting a count of the nodes in the tree and filling an unsigned long array with the IDs of all nodes in the tree, and disassembling a tree completely from the root node. It requires a standard-interface malloc() and free(). It also requires a decently-sized stack, as it relies heavily on recursion.
Anyway, my point is that I was hoping to be able to give something somewhat useful back to the community, I'm not very good at answering questions, and this is something I figured there might be some demand for. If anyone's interested, I can clean up the code a little and post a link. Otherwise, just disregard this message. lol
Thanks.
Posted: Thu Mar 13, 2008 2:13 am
by JamesM
Hi,
What algorithm do you implement for keeping the tree balanced?
Cheers,
James
Posted: Thu Mar 13, 2008 3:38 am
by DeletedAccount
Hi,
R u using an AVL tree or a Red Black tree ? . The recursion can removed by using an explicaot stack or use a level order traversal using a queue .. ( this nothing but a breadth first search
)
Posted: Fri Mar 14, 2008 7:34 pm
by inx
@JamesM: Honestly, the balancing isn't very good. I need to figure a not-too-heavy way to sort the tree that I can call from the btreeRemoveNode() function. If you have any direction you could steer me, it would be much appreciated.
@SandeepMatthew: I've never heard of either of those. I'm too poor ATM to buy any books, and I'm strictly self-taught. I can't afford university. Personally, I like the recursion. It keeps my code clean and concise while being able to branch different directions very easily.
Posted: Sat Mar 15, 2008 5:32 am
by Paw
inx wrote:@JamesM: Honestly, the balancing isn't very good. I need to figure a not-too-heavy way to sort the tree that I can call from the btreeRemoveNode() function. If you have any direction you could steer me, it would be much appreciated.
@SandeepMatthew: I've never heard of either of those. I'm too poor ATM to buy any books, and I'm strictly self-taught. I can't afford university. Personally, I like the recursion. It keeps my code clean and concise while being able to branch different directions very easily.
You were already provided with the right pointers for balancing algorithms. Just search the web, there is plenty of information around about red-black, AVL etc.
By the way, the term B-Tree does actually mean something different than "binary tree". It is a tree data structure, which supports a definable amount of minimum and maximum child nodes for each node and is typically used for quick data lookup/manipulation in databases.
Recursion can be converted to iteration, especially in such simple cases like searching a binary tree for a particular node.
If you have the spare money somewhen, I suggest buying a (used copy) of:
Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein). It contains invaluable information about that stuff, and gives you the right tools for run-time analysis and generally prevents the re-invention of the wheel.
By the way, the link I provided above, leads to an MIT "course-ware" homepage, which contains a whole university semester worth of information about the matter
for free 
. You can watch all lecture videos, download real exercise sheets (and solutions) and the final exam for it (with solution):
http://ocw.mit.edu/OcwWeb/Electrical-En ... /index.htm
EDIT:
An abstract example in pseudo-code (EDIT2: Whoa... I just notice it happens to be perfectly valid JavaScript. I'm getting old) for looking up a binary tree for a certain value (key), assuming that left children contain higher (and equal) values and right children smaller values:
Code: Select all
// Recursive
function searchKey(node, key) {
if(node.key == key) return true;
if(node.key > key) {
if(node.right != null) return searchKey(node.right, key);
} else {
if(node.left != null) return searchKey(node.left, key);
}
return false;
}
This can be converted into an iteration the following way:
Code: Select all
// Iterative
function searchKey(node, key) {
while(node != null) {
if(node.key == key) return true;
if(node.key > key) {
node = node.right;
} else {
node = node.left;
}
}
return false;
}
I hope I didn't mess up the example. It isn't supposed to work correctly anyway, it should just show the idea behin the conversion from recursion to iteration.
Posted: Sat Mar 15, 2008 11:12 am
by Meor
I liked skiplists instead of trees since they're a little more straightforward and, with high probability, don't need balancing.
Posted: Sat Mar 15, 2008 3:25 pm
by Paw
Meor wrote:I liked skiplists instead of trees since they're a little more straightforward and, with high probability, don't need balancing.
I agree, they are good. Unfortunately they are not covered in "Introduction to Algorithms". At least not in the edition I have :-/
So another thing to google for
Posted: Sat Mar 15, 2008 5:59 pm
by inx
Paw: Thank you for the information you provided, and I'll take note of that book title for later reference. Also, I did end up searching for the mentioned algorithms, I was just meaning that I hadn't yet heard of them and had not been able to find anything specific rather than 8-page articles about what btrees are philosophically before Sandeep's post.
Posted: Sat Mar 15, 2008 11:38 pm
by elderK
Erm...
If anyone needs a flexible (and horrendously minimal) implementation of the AVL Tree, email me and I will upload the sources.
Fully iterative, No explicit stack - No recursion...
Balance is stored in two bits.
Plenty of space for your data, ANSI C89 compliant.
~Z