Cheat Engine

[manc]

I have a binary search tree, an avl tree to be more specific, holding my data. Recursion is really the only way I know how to traverse the tree, as you can see in the code below. I want to create an array with all the items from the tree, in order.

[Dark Byte]

Add a "previous" and "next" to the item object

When adding items to the tree you could look up the previous and next item using recursion and then fill in the "previous" and "next" field to those items and adjust the next and previous field of the other two items to the newly added one
(a combination of a linked list and a tree, tree to quickly find a specific entry and the linked list to look around the area)

[manc]

Hmm, wouldn't I have to update the the tree after every insertion? If my tree gets unbalanced it automatically rotates some sub trees to maintain general balance ...I don't know if that would affect this method since things will be shifting around. Also, I was hoping to keep insert() at O(log n) complexity..

[Dark Byte]

as long as the identifier(key) of your object is unique you can search for the closest item with the current keyvalue and use that one's previous/next value to traverse where you wish to insert it.
That the tree rearranges stuff won't matter as long as the key values are unchanged

Also, are you going to do sequential inserts or random inserts?
If sequential, keep a pointer to the last added object and use that to update the linked list

[manc]

Multiple objects could have the same key value but all of their instance variables may not necessarily be the same.

Insertions will be random.

[manc]

[Dark Byte]

(not really sure why I wrote recursion, I tend to write words that I don't even know I'm writing them)

Linked list:
Previous is a pointer to the item in front of the current one, and next is a pointer to the item after the current one.
If previous is nil, it's the first item in the list, if next is nil, it's the last item in the list

When I add something to a tree I first look up if there is a entry with a key closest to the one I am going to add

When it returns an entry I check the key and determine if I should add it in front or after it in the list (if it returns nothing, set next and previous to nil)

If in front:
set the "next" field to the found item
set the "previous" field to the "previous" field of the found item
change next->previous to point to your object
if previous is not nil then change previous->next to point to your object

If after it:
set the "next" field to the "next" field of the found item
set the "previous" field to the found item
if next is not nil then change next->previous to point to your object
change previous->next to point to your object

Now add your object to the tree

[manc]

But I also need to remove things from the tree...which means I'll have to remove things from the List also. Currently I can remove things from the tree with O(log n) complexity , but if I have to search the list for the item I want to remove, it'll go up to O(n log n)

[Dark Byte]

No need to search through the list

When you remove an object from the tree, you look up the previous and next fields of the object you're going to delete
if previous is not null then change previous->next to "next" field of the object to delete (can be null)
if next is not null then change the next->previous to the "previous" field of the object to delete (can be null)

to visualize:

[manc]

Yeah, I understand how linked lists work and all, no problem there...

I'm mainly just confused on trying to figure out how the list is generated based on what you said above/before

Edit: I figured something out
Thanks for the help Dark Byte