[ABANDONED] South-Paw AVL Tree

[Sarah]

---

I wrote this BST a while back in C# for a Unity project, and I've been considering creating such a library for an array replacement for ZScript Windows; I could use some improved methods of storage for stuff. So I wondered if I could just port my old AVL tree over, and with a bit of tweaking, sure enough yes!

---

Oh yeah, what's a BST, let alone an AVL one? A BST is a Binary Search Tree, a storage system that is more efficient with large amounts of data than an array.
You know that AllClasses array? I've haven't checked but I bet searching that array with large mods can actually be pretty time consuming because, in the worst case, to search the array you have to iterate through Every - Single - Object to get the one you actually need. A binary search tree, by it's very nature attempts to eliminate this problem by not being a linear list of objects, it's a tree. A node in the tree has left and right children, the left being of an arbitrary lesser value than the parent, and the right being of an arbitrary greater value than the parent. This means that searching will eliminate 50% of its possible results with each iteration; I"m not super good with Big O but I do know that this makes the time complexity logarithmic, O(log n), but often O(1). There is one gotcha though for binary trees: presorted data. Data that has been sorted by the same rules the tree uses to determine location can cause the tree to become a linked list, which is basically an array.

AVL, named after inventors Adelson-Velsky and Landis, is a binary search tree variant that includes height balancing algorithms to ensure that the tree maintains its structure. This only has to be done during operations like Insert and Delete, as well as any bulk operations such as a Split or Join. Nodes in the tree have a balance factor, which may be as great as +-1, however a +-2 balance results in a rotation of the nodes. Unlike arrays, where a node is in the tree does not matter, access is always done with a Find method.

Couple of things:

1. It's called a South-Paw tree because I'm left handed and I made a small mistake in the code: left values are positive and right are negative. It's usually the other way around. No I'm not fixing it, the programmer I was working with on the Unity project coined the name, not me.
2. There's no Delete method - there is, but it does nothing. I never finished it. Height balancing binary search trees are mind bending - like the Matrix with the spoon but it's your brain - levels of hard understand under the hood. If you get it, then you have my respect, this tree took me about 5 weeks originally and a notebook of doodled trees from the Visual Studio debugging trying to get the algorithms right. And it's only a few hundred lines of code!!!
3. I'm not 100% sure it perfectly balances the tree. I have suspicions that left and right of the root may become imbalanced and never corrected but overall the tree maintains a level of balance that should keep searching with O(log n) times.
4. With the last 2 things, if you'd like to contribute I'd be interested to see your code!
5. No significant testing has been done as of right now when this post was made. I know the C# version works, used it in Unity for several years now. I saw GZDoom load, I haven't started using it yet, so it may require changes. If you have problems or see problems, please let me know!

Github Repo South-paw AVL Tree

Update!
I have done some testing and yep, it works! I have also implemented a Count and a Delete method, the former of which is just for information, the latter of which does not height balance the tree. I haven't tested Delete yet, I might be making some bad assumptions about ZScript and references, so still some testing yet to do.

Use:

• It's two classes, the tree and the nodes.
  • Implemented Tree Methods:
  • Insert - inserts and object into the tree
  • Find - locates a node in the tree
  • Delete - removes a node from the tree, currently does not height balance (accepting PRs). Associated object is not deleted; like if you got your own list of monsters and you delete a node for some imp that imp isn't going to self destruct in the level unless you do it yourself.
  I can look into supporting Split and Join if someone needs them.

• One thing to note is that it'll work just like an array in regards to access. So if using this in say an EventHandler, manipulating at the correct time will be crucial. Found that out the hard way with ZScript Windows; RenderOverlay is not a fan of arrays that change their contents while it's trying to read it
  Some Basic Instructions:
  It works pretty much like using any other class. Declare an instance of the tree, initialize with "new" and call "Init".

  Code: Select all

  ZABST binaryTree = new("ZABST").Init();

  Adding things to the tree is just as easy (whatever you're putting in the tree needs to inherit from Object, be it an Actor, a Thinker, etc., etc.). You call insert on the tree, and give it the object's reference and a name. The name is needed for searching.

  Code: Select all

  binaryTree.Insert(object, "theObjectNamedGerald")

  Now to find something again, well you just call the find method on the tree. And this is where you need that name you gave the object. You don't get the object, you get the tree node.

  Code: Select all

  ZABST_Node geraldNode = binaryTree.Find("theObjectNamedGerald");

  And if you want to get at the data in the actual object, all you have to do is access the data member of the node.

  Code: Select all

  int geraldsTid = geraldNode.Data.TID;

  Finally, once you don't need Gerald anymore, you call the delete method and Gerald is gone! This doesn't destroy the actual object, just removes the reference from the tree.

  Code: Select all

  binaryTree.Delete("theObjectNamedGerald");

My South-paw AVL Tree is no longer available on the ZDoom Forums. Thank you.

My mods are available on my GitHub.