Ha! I thought that title would catch your attention. Anyway, I was sitting in work one day and, bored since I had completed everything, started to engage in one of my favorite pasttimes... thinking! Somehow, I ended up on the subject of data structures, particulary BSTs. I started thinking: "Man, wouldn''t it be great if I could produce a BST that sorted itself like a normal Linked List, that way I wouldn''t have to waste time with the possibility of an unbalanced tree?" The idea stuck with me, so I decided to do a few simple trial runs on a piece of paper to see how it would work. I definately seemed to... just take a double pointer linked list, with Head, Tail, and Mid pointers. When inserting an element, use the list as a normal Linked List in order to sort it. But when searching, start at the mid pointer and count down from that point to search de-facto like a BST, only one which is guarenteed to be almost perfectly balanced. As I looked at my little diagrams, I began thinking: "This is too simple. It''s GOT to have been done at some point in the past!" So, I started looking through my algorithim books. Nothing. I looked on the internet. Nothing. This confuses me. It doesn''t seem likely that I am the first person to devise this concept. Has ANYONE else out there heard of or scene anything like this? ANd, if so, does anyone know why they aren''t used? Does the overhead of having to walk down the linked list from the middle, rather than using direct pointers in a pure BST, commit too much overhead? BUt even with that, shouldn''t it ALWAYS be just /slightly/ below the time it would take to traverse a normal linked list? Thanks for your time, Sivle

I''m sure someone has made a data structure like that before. You can always design or change existing standard data structures to suit the task at hand. Use whatever offers the best blend of efficiency and speed...but it really depends on what you''re doing.

It sounds like you have an awesome job, Sivle. You finish early and get to sit around while still getting paid. What profession are you in? Sounds like the good life to me.


Alex
bigshot@austin.rr.com

The only way to get on your feet is to get off your ass.

Well, I''m a programmer. Right now we''re doing a root-canal of the existing SQL database which means that timing is essential. Finish early, and I have to wait for the others to get all the other changes done before we move onto the next step. That''s the reason I have the time to think.

Thanks for your answer, though. I just find it hard to believe that this data structure has never been thought of before. The reason I came up with it is because I was thinking about an AI project I''m working on. Basically, I want a behavior queue that is organized according to the importance of the behavior. The problem was that there should only be one type of behavior in the queue at one time, which means that if I need to insert, say... a "Bake Bread" behavior and there''s already one there, I have to set the timeout variable in the first Bake Bread action so it won''t be done when the queue is popped. This, of course, would mean a huge overhead to look through the list segment by segment... it would be great if I could make a queue that could be searched like a BST... which led me to the above data structure.

I know of a BST sorting routine.

i cant find my notes from that class right now though, but if i find them, i''ll post the algo.

===============================================
If there is a witness to my little life,
To my tiny throes and struggles,
He sees a fool;
And it is not fine for gods to menace fools.

Hmmm... That would be faster than a standard sorted linked list, but not a great deal: as the binary search algorithm can''t be used on linked lists, the average speed increase would only be a result of checking about half as many nodes on the average. So what you describe, if I understand it properly, would have an efficiency of O(n) in the average and worst case scenarios.

However, there are at least two variants of BST''s that automatically height-balance themselves with every insert or remove operation. I''ve implemented an AVL tree (which was unpleasant to say the least) and know that Red-Black trees work with similar efficiency. Both of those data structures have an efficiency of O(log n) in the average and worst case scenarios. You might want to look into either of those structures. I would provide a link, but I never found a really clear explanation of either online (which is why implementation of the AVL tree was so painful.)

Of course, if I misunderstood your description, tell me so. I''m always looking for new data structure ideas (even if I only understand some of them.)

aha!

found my old notes on AVL tree''s.

okay.

So, first off, you should know that you can only use the AVL algorithm on a tree which has had EVERY NODE inserted using the algorithm. So, taking a non-AVL sorted tree, and using the AVL algorithm on it will produce a meaningless result (and the algo just doesnt make sense in that case).

Algorithm for insetion into AVL Tree:

Perform insertion as in binary search treeSet current node to the newly inserted nodeWHILE the current node is not NULL    IF the tree starting at the current node is not height balanced,        Perform a rotation        set the current node pointer to NULL    ELSE        Move to the current node''s parent.END WHILE 

well, that didn''t help, did it? heh...

The algo for finding out if a node is not height balanced is:

count highest level of left childcount highest level of right childif abs( left level - right level ) > 1    Tree is unbalancedelse    tree is balancedend 

Don''t count nodes, just count the LEVEL of the nodes.

okay, now the real tough part of the algorithm is the rotations. There are four different cases: RR, RL, LL, and LR.

lets say you insert the numbers 10,20, 30 into an empty BST.

it creates a tree like this:
(level count of left node: 0; level count of right node: 2; abs(0 - 2) > 1; tree is unbalanced)

10  \  20    \    30 

This tree is not height balanced. It requires an RR rotation, since the out of place node (30) is a right node, and the node above it is also a right node. (NOTE: 20 is the first R and 30 is the second R. you''ll need to know this when figuring out RL and LR rotations).

the RR rotation algo is:
a is the node at which the imbalance occurs
b is the right child of a
p is the parent node of a

a.rightchild = b.leftchildb.leftchild  = aIF p is NULL THEN    // b is the new root of the treeELSE    p.whichever_child_was_a = bEND 

graphically:

10 is a
20 is b
p is NULL.

+---------+---------+--------+| 10      |   10    |   20   ||   \     |         |  /  \  ||   20    |  20     | 10  30 ||     \   |    \    |        ||     30  |    30   |        |+---------+---------+--------+| INITIAL | STEP 1  | Step 2 |+---------+---------+--------+ 

so, the tree is now height balanced. Cool, eh?
Lets try adding more numbers to this tree, for practice (wink wink).

insert: 40, then 50.
a regular binary tree insertion would produce:

   20  /  \ 10  30       \       40         \         50 

After inserting the 40, the tree is still height balanced. Lets look at the algorithm to make sure:

left height of 40: 0right height of 40: 0difference: 0, balanced.go up one levelleft height of 30: 0right height of 30: 1difference: 1, balanced.left height of 20: 1right height of 20: 2difference: 1, balanced. 

So, its still balanced. When you insert 50, an imbalance occurs at node 30, so we need another RR rotation. This time, p is not NULL, but the results are basically the same:

a is 30
b is 40
p is 20

a.rightchild = b.leftchild (NULL)
b.leftchild = a (30)
p.right(since ''a'' was a right child) = b (40)

now the tree is balanced again:

   20  /  \ 10  40    /  \   30   50 

yay!

There are three other cases:

+----------+---------+---------+|   RL:    |   LL:   |   LR:   |+----------+---------+---------+|   20     |   20    |   20    ||  /  \    |  /  \   |  /  \   || 10  30   | 10  50  | 10  50  ||       \  |     /   |     /   ||       50 |    40   |    30   ||       /  |   /     |     \   ||      40  |  30     |     40  |+----------+---------+---------+ 

Algorithm''s for each case:

RL:

a is the node at which the imbalance occurs  (30)b is the right child of a                    (50)c is the left child of b                     (40)p is the parent of a                         (20)b.leftchild  = c.rightchilda.rightchild = c.leftchildc.rightchild = bc.leftchild  = aIF p is NULL THEN    c is the new root of the treeELSE    p.whichever_child_was_a = cENDend graph:   20  /  \    10  40    /  \   30  50 

LL:

a is the node at which the imbalance occurs  (50)b is the left child of a                     (40)p is the parent of a                         (20)a.leftchild  = b.rightchildb.rightchild = aIF p is NULL THEN    b is the new root of the treeELSE    p.whichever_child_was_a = bENDend graph:   20  /  \    10  40    /  \   30  50 

RL:

a is the node at which the imbalance occurs  (50)b is the left child of a                     (30)c is the right child of b                    (40)p is the parent of a                         (20)b.rightchild = c.leftchilda.leftchild  = c.rightchildc.leftchild  = bc.rightchild = aIF p is NULL THEN    c is the new root of the treeELSE    p.whichever_child_was_a = cENDend graph:   20  /  \    10  40    /  \   30  50 

Thats it! Note: You shouldnt have to do more than one rotation per insert, because one insert will only cause one level of imbalance, which is easily fixed with one rotation.

Also, a reminder that using the AVL insert algorithm on a normal BST (one which hasnt had all its nodes inserted via AVL) will break the tree, causing it to break the BST rules, and you''ll never know what you will get when using a broken tree.

Using this algorithm ensures that you get a O(log n) search time all the time. In worst case BST scenario''s, the search time is O(n). That case will never happen with a AVL tree.


Final Note: I originally just started copying my notes, but im a crappy note-taker. So, I decided to write this in tutorial form. Its not very clean yet, but maybe i''ll fix it up and submit it to GDNet.

===============================================
If there is a witness to my little life,
To my tiny throes and struggles,
He sees a fool;
And it is not fine for gods to menace fools.

c_wraith:
Nope, you pretty much nailed the problem on the head there. I did look at self-balancing BSTs, but, like you... I really couldn''t find a clear explaination of their implementation. The other problem I had was regarding how I wanted to use the list. Basically, I want to have records inserted based on a Priority value, pop them off with highest Priority value first, and when inserting the same event, find if the node had already been inserted and change a Timeout variable. That probally isn''t too clear, so let me give you a theoretical example.

Lets say you have some NPC in a game who has to decide what to do next. Lets also say that the NPC has run through it''s internal logic and decided to "BAKE BREAD". This is not a critical event, so the Priority given to it is fairly low. Say... 3. So, the "BAKE BREAD" event is inserted into a sorted linked list at a Priority of 3. The NPC will now look at it''s current task and, if the Priority of the next event in the list is greater than the current assigned task, or if the current assigned task has timed out, then the new behavior will be selected. This behavior is then checked to see if it''s timed out and, if so, is discarded and the process continues until either a decision on what to do is made, or there are no more tasks to perform. The problem then become duplicate events. It''s possible for the decision routine to keep deciding to bake bread, and if that''s the case I don''t want to have several dozen "BAKE BREAD" nodes cued up and the NPC stuck. Thus, the desire to search the list as a BST, even if it isn''t.

Hmm... now that I think a bit more about it, the way I was imagining it to work was pretty darn stupid. It would be probally a lot easier to just have two lists, one a sorted queue and the other a BST with pointers to the nodes in the queue. That also would reduce the redunancy of having a whole bunch of "BAKE BREAD" events, most of which would be forcibly set to time out.

Thanks! You helped me come up with a better idea of how to do this!

-- Sivle

Mithrandir:
Wow! I must say I am impressed! That''s the clearest and most useful explaination I''ve ever heard for a self-balancing BST. I''m definately keeping your message in my files! Kudos to you!

-- Sivle