general b-tree idea

This is a discussion on general b-tree idea within the C++ Programming forums, part of the General Programming Boards category; I have a question regarding the b-tree. For a binary tree, i usually declare a node like: Code: struct node ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    general b-tree idea

    I have a question regarding the b-tree.
    For a binary tree, i usually declare a node like:
    Code:
    struct node
    {
    	char value;
    
    	node *left;
    	node *right;
    	node *parent;
    };
    For a b-tree with a four key reference, it might look like:
    Code:
                          [1][D][2][T][3][ ][4][ ]
                          /          \
                         /            \
                        /              \ 
    [1][A][2][C][3][D][4][ ]    [1][S][2][T][3][ ][4][ ]
    So, would i declare a node like:
    Code:
    struct node
    {
    	char value1;
    	char value2;
    	char value3;
    	char value4;
    
    	node *one
    	node *two;
    	node *three;
    	node *four;
            node *parent;
    };
    So, it's like a binary tree, except with more values and pointers. Is this the proper way to do this?

    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    That looks like the basic idea, although perhaps one, two, three, and four aren't the world's best names. (You could maybe make it an array, node *children[4] or something.)

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    You'd have two arrays.
    Code:
    struct node
    {
      node *links[CARDINALITY];
      boost::optional<VALUE> values[CARDINALITY - 1];
    };
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. finding the value and derivative of a math function
    By silenceee in forum C++ Programming
    Replies: 8
    Last Post: 05-30-2011, 05:40 AM
  2. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  3. Weight Balanced Tree - Implementation
    By paulovitorbal in forum C Programming
    Replies: 1
    Last Post: 10-31-2007, 02:28 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 01:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21