Sorry your browser is not supported!

How would I make a BST that has anywhere from 1-256 nodes at the first parent and first child then additional nodes for equivalent values.

Isn't the definition of a binary search tree that there are at most two direct child nodes for any parent node...?

I'm trying to use trees instead of array lists lets say there were 6 values max per level it would look like this
Root
/ / / \ \ \
1 8 15 22 29 36
///\\ / / /\ \ \ / / /\ \ \ / /\ \ \ \ \ \ / / /\ \ \
23456 91011121314 161718192021 2324252627 303132 373839404142

If there is no way to do this then:
How would I do a Tenary Search Tree(equal to,greater,less than) So I can goto T[256,256] without having to declare extra memory for empty nodes/array values.

Would Objects/structures be more efficient that lists in memory performance?

1. How are you going to construct a tree in a language that doesn't natively support them? You could emulate them in an array, but then you may as well just treat it as a list/array.

2. No, they wouldn't be more efficient in memory, but maybe in performance, depending on how these structures are going to be used. Lots of inserts during the running of your program may be slower if you are using an array, but maybe not.

Suggestion 1.
Use a binary search for searching for matches, and for finding the insertion point for new items.

The downside is that if you have a lot of insertions, it can be slow to shift all of that data around in the array if you have a large array (I'm talking 10's of thousands of items or more).

Suggestion 2.
Use a sorted array, with a binary search, and a 'dirty' flag...

When searching, if the dirty flag is set, then you sort the array and clear the flag, and then finally carry out your search. (If it's not set, then don't sort).

When inserting, append the new item to the end of the array and set the dirty flag.

That simply mechanism gives you relatively efficient bulk-insertion, and fast search. You can either code the sort yourself, or use the SORT ARRAY command in my plug-ins.


Neither suggestion includes a description of how to handle deletions, but it's the same for both. Locate the item you want to delete, then use the ARRAY DELETE ELEMENT command to remove it - it's a fairly efficient command, as all it does is shift pointers around behind the scenes.

That seems to suggest the "arrays" are really linked lists, in which case I don't see why an insertion should need to shift data around...?
Or is it some kind of hybrid sub-list table implementation?

Arrays are implemented as a table of pointers to items. When an item is deleted from the array, the pointers beyond the deleted item are moved back one place.