2-4 trees in C Post: 302366722

Sponsored Content

Top Forums Programming 2-4 trees in C Post 302366722 by bashuser2 on Friday 30th of October 2009 07:36:10 AM

10-30-2009

Registered User

2-4 trees in C

i am trying to write a program in order to learn how to work with trees and especially 2-4 trees.
the general idea is that each node is represented by 4 cells and 5 pointers? (maybe 2 arrays then? )
let's suppose that we insert simply int numbers in all cells.
firstly we initialize the root (==null ? )
then we fill up all 4 cells of the first node and we must have its 4 int numbers in numerical order?and what happens when we want to insert a 5th element?

of course i don't expect every question answered(as there is only 1 total answer i suppose) but a brief explanation would really help.maybe a link to a tutorial would also be very helpful.

//important: how can i separate internal nodes from leaf nodes?let's suppose that each pointer in the leaf level must point to another array(one level lower that is)which may contain also 4 cells with another type(int or char * etc)...how can i write and create this separation?maybe two structs or can i do that with just one struct and flag variables?

bashuser2

View Public Profile for bashuser2

Find all posts by bashuser2

5 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Best way to diff two huge directory trees

Hi I have a job that will be running nightly incremental backsup of a large directory tree. I did the initial backup, now I want to write a script to verify that all the files were transferred correctly. I did something like this which works in principle on small trees: diff -r -q...

2. Shell Programming and Scripting

CGI , Perl and Trees

I have been trying to get this for weeks now but maybe someone knows or has a snippet of code to display a collapsible tree view. something like this: +Yahoo! -/site.html -/site2.html +Google -/site.php -/site2.php

3. Shell Programming and Scripting

How to copy very large directory trees

I have constant trouble with XCOPY/s for multi-gigabyte transfers. I need a utility like XCOPY/S that remembers where it left off if I reboot. Is there such a utility? How about a free utility (free as in free beer)? How about an md5sum sanity check too? I posted the above query in another...

4. Slackware

What is the medium usually used to backup large trees?

Hi: What's asked.

5. What is on Your Mind?

From little Acorns big trees grow...

Hi all... This is mainly for Corona688: Do yo remember your translation of a DFT into AWK code? Well it reached 130 dls inside the first 14 days, but take a look at it now. Aminet - dev/gcc/DFT-FFT.awk.txt

LEARN ABOUT MOJAVE

skiplist

struct::skiplist(n)						Tcl Data Structures					       struct::skiplist(n)

__________________________________________________________________________________________________________________________________________________

NAME

       struct::skiplist - Create and manipulate skiplists

SYNOPSIS

       package require Tcl  8.2

       package require struct::skiplist  ?1.3?

       skiplistName option ?arg arg ...?

       skiplistName delete node ?node...?

       skiplistName destroy

       skiplistName insert key value

       skiplistName search node ?-key key?

       skiplistName size

       skiplistName walk cmd

_________________________________________________________________

DESCRIPTION

       The ::struct::skiplist command creates a new skiplist object with an associated global Tcl command whose name is skiplistName. This command
       may be used to invoke various operations on the skiplist. It has the following general form:

       skiplistName option ?arg arg ...?
	      Option and the args determine the exact behavior of the command.

       Skip lists are an alternative data structure to binary trees. They can be used to maintain ordered lists over any  sequence  of	insertions
       and  deletions.	Skip lists use randomness to achieve probabilistic balancing, and as a result the algorithms for insertion and deletion in
       skip lists are much simpler and faster than those for binary trees.

       To read more about skip lists see Pugh, William.  Skip lists: a probabilistic alternative to balanced trees In: Communications of the  ACM,
       June 1990, 33(6) 668-676.

       Currently,  the key can be either a number or a string, and comparisons are performed with the built in greater than operator.  The follow-
       ing commands are possible for skiplist objects:

       skiplistName delete node ?node...?
	      Remove the specified nodes from the skiplist.

       skiplistName destroy
	      Destroy the skiplist, including its storage space and associated command.

       skiplistName insert key value
	      Insert a node with the given key and value into the skiplist. If a node with that key already exists, then the that node's value	is
	      updated and its node level is returned. Otherwise a new node is created and 0 is returned.

       skiplistName search node ?-key key?
	      Search  for  a  given  key  in  a skiplist. If not found then 0 is returned.  If found, then a two element list of 1 followed by the
	      node's value is retuned.

       skiplistName size
	      Return a count of the number of nodes in the skiplist.

       skiplistName walk cmd
	      Walk the skiplist from the first node to the last. At each node, the command cmd will be evaluated with the key  and  value  of  the
	      current node appended.

BUGS, IDEAS, FEEDBACK
       This  document,	and the package it describes, will undoubtedly contain bugs and other problems.  Please report such in the category struct
       :: skiplist of the Tcllib SF Trackers [http://sourceforge.net/tracker/?group_id=12883].	Please also report any ideas for enhancements  you
       may have for either package and/or documentation.

KEYWORDS

       skiplist

CATEGORY

       Data structures

COPYRIGHT

       Copyright (c) 2000 Keith Vetter

struct									1.3						       struct::skiplist(n)