AVL Tree Module

Resources Community Resources
#1

Here, I’ve created a Module for AVL Trees in Lua.

What are AVL Trees?

AVL Trees are a data structure with O(n) space, and O(log n) insert, and O(log n) delete. They store data in a Binary Tree structure with the left branches having a lower value than the right branches. AVL Trees are a type of Binary Tree that is balanced to have the height of the left branch be the height of the right branch give or take 1 of any node.


AVL Trees are balanced to make searching more efficient.

Installation

Download the .lua file, insert it into your game as a Module Script, then use require(PATH TO MODULE) to require the module in one of your scripts.

Example Usage

local AVL = require(script.Parent.AVL_Tree)

-- Initializes the AVL Tree with the values 12, 5, 18, 4, 11, 17, 20
-- 12 also has the extra data "kiwis"
local Tree = AVL.new({4, 11, {12, "kiwis"}, 20, 18, 17, 5, 8}) 

-- Inserts a node with the value 6 and extra data "watermelons"
Tree:Insert(6, "austrailian jalapenos")
Tree:Insert(7) -- Inserts a node with the value 7 and no extra data

-- Gets the first Node with the value 6 and outputs the data
local Node = Tree:Get(Root, 6)
print(Node.Value, Node.Extra) -- Prints "6 austrailian jalapenos"

-- Removes the first Node with the value 4, in this case, the "austrailian jalapenos" node
Tree:Remove(Root, 7)
-- Attempts to get the node with the value 7, but outputs nil because it has been removed
local Node = Tree:Get(Root, 7)
print(Node) -- Prints nil

Resources

AVL Tree.lua (6.9 KB)

6 Likes
#2

cn u explain this more simply for people unaware of datastructures

#3

I don’t think people unaware of data structures would need this
you’d usually just use this if you need to work with a huge amount of data

1 Like
#4

AVL Trees are a decent way to organize data for sure!
One thing though, is this should be more optimized.

For example, doing

local Root
Root = AVL.Insert(Root, 1)
Root = AVL.Insert(Root, 2)
Root = AVL.Insert(Root, 3, "kiwis")
Root = AVL.Insert(Root, 4, "austrailian jalapenos")
Root = AVL.Insert(Root, 4)

is incredibly repetitive.

I would recommend the following changes:

  • Allow initializing AVLs with arrays of variable dimensions
  • Object-oriented style
  • camelCase method name style.
#5

What did you mean by repetitive? How should I change that?
And what did you mean by initializing with an array of variable dimensions? I don’t think it’s possible to pre-allocate space for an AVL because of the structure and because Lua doesn’t allow using pointers

#6

The first two suggestions I gave should solve that ^-^

I mean instead, maybe something like:

AVL.init( { [1] = {"nil"}, [2] = {"nil"}, [3] = {"kiwis"}, [4] = {"austrailian jalapenos", "nil"} } )
1 Like
#7

Thanks, I’ll setup making the root an object and allow initializing soon

1 Like
#8

Thank u for this, I’m making a polygon triangulation module trying to get to O(nlogn) max time. This module is perfect for this!

1 Like