[ZScript] South-Paw AVL Tree

Post your example zscripts/ACS scripts/etc here.

[ZScript] South-Paw AVL Tree

Postby Nero » Mon Aug 31, 2020 2:32 pm

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!

Spoiler: "If you don't know what this even is:"


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 :P
    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 allExpand view
    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 allExpand view
    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 allExpand view
    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 allExpand view
    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 allExpand view
    binaryTree.Delete("theObjectNamedGerald");
User avatar
Nero
Royal Boredom....Why can't I do this in Windows?
 
Joined: 06 Sep 2006
Location: Middle of Nowheresville Il.

Return to Script Library

Who is online

Users browsing this forum: No registered users and 0 guests