How to implement a binary tree in vjass?

[MyPad]

I'm coding a Binary Tree Binary Heap down below.

library BinaryAssortment

	module MyAlloc
		private static thistype instance = 0
		private thistype recNext
		
		static method allocate takes nothing returns thistype
			local thistype this
			if thistype(0).recNext == 0 then
				set instance = instance + 1
				return instance
			endif
			set this = thistype(0).recNext
			set thistype(0).recNext = this.recNext
			return this
		endmethod

		method deallocate takes nothing returns nothing
			set this.recNext = thistype(0).recNext
			set thistype(0).recNext = this
		endmethod
	endmodule

	module PrevNext
		thistype prev
		thistype next
		
		method push takes nothing returns nothing
			set this.next = 0
			set this.prev = thistype(0).prev
			set this.prev.next = this
			set this.next.prev = this
		endmethod
		
		method pop takes nothing returns nothing
			set this.prev.next = this.next
			set this.next.prev = this.prev
		endmethod
	endmodule
	
	private struct Interface extends array
		//has no method whatsoever
	endstruct
	
	private struct Node extends array
		implement MyAlloc
		implement PrevNext
		
		integer value
		integer index
		Interface Id
		
		static method getNodeUnknown takes integer index, Interface indexId returns thistype
			local thistype this = thistype(0).next
			loop
				exitwhen this == 0 or (this.index == index and this.Id == indexId)
				set this = this.next
			endloop
			return this
		endmethod
		
		static method getNode takes integer value, integer index, Interface indexId returns thistype
			local thistype this = thistype(0).next
			loop
				exitwhen this == 0 or (this.value == value and this.index == index and this.Id == indexId)
				set this = this.next
			endloop
			return this
		endmethod
		
		static method create takes integer value, integer index, Interface indexId returns thistype
			local thistype this = getNode(value, index, indexId)
			if this == 0 then
				set this = allocate()
				set this.index = index
				set this.Id = indexId
				call this.push()
			endif
			return this
		endmethod
		
		method destroy takes nothing returns nothing
			set this.value = 0
			set this.index = 0
			set this.Id = 0
			call this.pop()
			call this.deallocate()
		endmethod
	endstruct
	
	private struct Heap extends array
		implement MyAlloc
		implement PrevNext
		
		private Node root
		private integer index
		private Interface interface
		
		static method create takes integer root returns thistype
			local thistype this = allocate()
			set this.index = this.index + 1
			set this.interface = this
			set this.root = Node.create(root, this.index, this.interface)
			call this.push()
			return this
		endmethod
		
		method search takes integer value returns Node
			local integer i = 1
			loop
				exitwhen Node.getNodeUnknown(i, this.interface).value == value or i == this.index + 1
				set i = i + 1
			endloop
			if i == this.index + 1 then
				return 0
			endif
			return Node.getNodeUnknown(i, this.interface)
		endmethod
		
		method sortAdd takes Node whichNode returns nothing
			local Node curr = whichNode
			local Node head = Node.getNodeUnknown(curr.index / 2, this.interface)
			local integer index = 0
			loop
				exitwhen curr.value < head.value or head == 0
				set index = head.index
				set head.index = curr.index
				set curr.index = index
				set index = curr.value
				set curr.value = head.value
				set head.value = index
				set head = Node.getNodeUnknown(head.index / 2, this.interface)
			endloop
		endmethod
		
		method add takes integer value returns nothing
			local Node temp = this.root
			local Node new = Node.getNode(value, this.index, this.interface)
			if new == 0 then
				set this.index = this.index + 1
				set new = Node.create(value, this.index, this.interface)
				call this.sortAdd(new)
			endif
		endmethod
	endstruct
endlibrary

Any ideas as to how I can improve certain things about it?

 

[PurgeandFire]

In a basic sense (without going too much into the details), it'd look like this:

/**
 *    Example:
 *
 *        local BinaryTree tree = BinaryTree.create(10)
 *        call tree.add(5)
 *        call tree.add(10)
 *
 */

struct BinaryNode
    BinaryNode left     // Left child
    BinaryNode right     // Right child
    integer value         // Data for node

    static method create takes integer value returns thistype
        local thistype this = thistype.allocate()
        set this.value = value
        set this.left  = 0
        set this.right = 0
        return this
    endmethod
endstruct

struct BinaryTree
    BinaryNode root

    static method create takes integer rootValue returns thistype
        local thistype this = thistype.allocate()
        set this.root = BinaryNode.create(rootValue)
        return this
    endmethod

    method add takes integer value returns nothing
        local BinaryNode current = this.root
        local BinaryNode newNode = BinaryNode.create(value)

        loop
            exitwhen current == 0
            if data < current.value then
                if current.left == 0 then
                    set current.left = newNode
                else
                    set current = current.left
                endif
            else
                if current.right == 0 then
                    set current.right = newNode
                else
                    set current = current.right
                endif
            endif
        endloop
    endmethod

    method destroy takes nothing returns nothing
        // Loop through all nodes and destroy them
        call this.root.destroy()
        call thistype.deallocate()
    endmethod

endstruct

I didn't add much functionality (e.g. search, destroy) because I am not sure what you want to use it for in particular. But basically, you start with a root value for your tree, and every time you insert a node, you go "left" or "right" based on whether that value is larger or smaller than the current node you are looking at.

If you tell me what functions you need, I can give you a better answer. I just wrote this to give you a gist of how it'd look--dunno if it even compiles, lol.

 

[MyPad]

In a basic sense (without going too much into the details), it'd look like this:

/**
 *    Example:
 *
 *        local BinaryTree tree = BinaryTree.create(10)
 *        call tree.add(5)
 *        call tree.add(10)
 *
 */

struct BinaryNode
    BinaryNode left     // Left child
    BinaryNode right     // Right child
    integer value         // Data for node

    static method create takes integer value returns thistype
        local thistype this = thistype.allocate()
        set this.value = value
        set this.left  = 0
        set this.right = 0
        return this
    endmethod
endstruct

struct BinaryTree
    BinaryNode root

    static method create takes integer rootValue returns thistype
        local thistype this = thistype.allocate()
        set this.root = BinaryNode.create(rootValue)
        return this
    endmethod

    method add takes integer value returns nothing
        local BinaryNode current = this.root
        local BinaryNode newNode = BinaryNode.create(value)

        loop
            exitwhen current == 0
            if data < current.value then
                if current.left == 0 then
                    set current.left = newNode
                else
                    set current = current.left
                endif
            else
                if current.right == 0 then
                    set current.right = newNode
                else
                    set current = current.right
                endif
            endif
        endloop
    endmethod

    method destroy takes nothing returns nothing
        // Loop through all nodes and destroy them
        call this.root.destroy()
        call thistype.deallocate()
    endmethod

endstruct

I didn't add much functionality (e.g. search, destroy) because I am not sure what you want to use it for in particular. But basically, you start with a root value for your tree, and every time you insert a node, you go "left" or "right" based on whether that value is larger or smaller than the current node you are looking at.

If you tell me what functions you need, I can give you a better answer. I just wrote this to give you a gist of how it'd look--dunno if it even compiles, lol.

Thanks, all I really needed to know was how to implement it, unless create and destroy are considered as fundamental to the workings of a Binary Tree.

EDIT:

How was this moved into The Lab section? [insert surprise]

 

[KILLCIDE]

How was this moved into The Lab section?

I moved it. Triggers & Scripts is for where you go to get stuff debugged, which obviously requires you to post code. As you said in your initial post,

Sorry, no code given...

The Lab was a more appropriate forum.

 

[MyPad]

I moved it. Triggers & Scripts is for where you go to get stuff debugged, which obviously requires you to post code. As you said in your initial post,

​

The Lab was a more appropriate forum.

Okay, then. I removed the indication that it..

(A rhetorical question)

was not supposed to be answered.

Updating thread and question with code...

 

[MyPad]

Sorry for the great amount of delay. I hadn't had much time in my hands in coding.

Updating thread with new code...

//=======================================================//

Reply: @PurgeandFire​

//=======================================================//

I tried to do my own search method and my own remove method. What do you think?
Did I do it correctly?

 

[MyPad]

bumped this thread... :tongue out:

I'm trying to add some features. I bumped it so that I could see if I did it incorrectly.

Features added:

...Add method with sorting thereafter...
...Search method
...Remove method

I think this has almost reached completion so I'll just wait for some feedback, and corrections if needed.