Nestharus
o-o
- Reaction score
- 84
So, here's some c# code I whipped up today for an AVL BST. Jesus4Lyf, you can implement AVL easily into your BST now >.<, you can virtually copy my code here ;o.
So... should I translate into vJASS to be used? : p.
Oh, and I'm not really sure on the practical applications of this, heh. Really, you can have maxed array sized trees without a three crash due to the interface idea of compare, but if you converted that into a plain function call, you could run into a op limit very quickly ;o.
As for practical uses... AI =D, but would need a standard BST and an AVL BST, one for wide scope of decisions and the other for dynamic decision making, or something ;o.
Anyways, you'd be making a seriously advanced AI if you were using this, lol... actually an interesting project could be a generic AI that could learn the game by analyzing information given about the game ;o. That'd be really cool =). Also making AI for specific heroes or spells ;o, like an AI module to run a spell and would work inside of an AI framework. Could use an AVL BST to add your stuff to the AI's decision making =).
Actually, I might start up this AI framework now for OO shared design. That's kinda what I'm doing with my Spawn framework atm, people build modules and put them inside of a framework that runs those modules regardless of what they are. The framework just provides a standard API so everything can interact =).
Yum, AI framework sounds like a good idea : O.
Code:
/* Author: Me
*
* namespace System.Collections.Generic
*
* public class BST
* private Node root;
* public Node Root
*
* public void Add(object obj)
* public void Clear()
*
* private class Node
* private object obj;
* private Node left;
* private Node right;
* private int offset
*
* internal Node(object obj)
*
* public Node Left
* public Node Right
* public int Height
* public object Obj
*
* private void UpdateHeight()
* private Node RotateRight()
* private Node RotateLeft()
* private Node Balance()
* private Node Insert(object obj)
* internal Node Add(object obj)
*/
using System;
using System.Linq;
using System.Text;
namespace System.Collections.Generic
{
public class BST
{//simple self balancing BST without a search and with prevention of equal values
private Node root;
public Node Root
{
get
{
return root;
}//get
}//property Root
public void Add(object obj)
{
switch (root == null)
{
case true:
root = new Node(obj);
break;
case false:
root = root.Add(obj);
break;
}//switch
}//method insert
public void Clear()
{
root = null;
}//method Clear
//because I can
public class Node
{//all work beautifully for range and single operations
//recursive methods as BST is expected to be small, so simplicity + speed adv
private object obj; //payload
private Node left;
private Node right;
private Node root;
private int height;
internal Node(object obj)
{//new node
this.obj = obj;
}//constructor Node(object obj)
public object Obj
{
get
{
return obj;
}//get
}//property Obj
public Node Left
{
get
{
return left;
}//get
}//property Left
public Node Right
{
get
{
return right;
}//get
}//property Right
public int Height
{
get
{
return height;
}//get
}//property Height
//Adder Methods
//////////////////////////////////////////////////////////
internal Node Add(object obj)
{//Add does inserting and balancing, it acts as the traversal portion
//completely recursive
//on calls inwards (=) it will attempt to insert
//on calls outwards (return) it will balance
//*crazy* memory hog but very efficient
//only use on small BSTs unless you want to die
//compare this.obj to obj (<, >, ==)
int comparison = ((IComparable)this.obj).CompareTo(obj);
Node node = this;
if (comparison > 0)
{//<
left = Insert(left, obj); //insert delving in
node = Balance(left); //balance winding out
UpdateHeight(); //height has to be updated *after setting leaves
}//if
else if (comparison < 0)
{//>
right = Insert(right, obj); //insert delving in
node = Balance(right); //balance winding out
UpdateHeight();
}//else if
return node;
}//method Insert
private Node Insert(Node leaf, object obj)
{//insertion portion
if (leaf == null) //leaf empty?
{
leaf = new Node(obj);
leaf.root = this;
int level = 0; //for updating levels
for (Node node = this; node != null; node = node.root)
if (node.height < ++level) node.height = level;
return leaf;
}//if
return leaf.Add(obj); //continue delving in
}//method Insert
//Balancing Methods
//////////////////////////////////////////////////////////
private void UpdateHeight()
{//recursively update height of entire tree
if (left == null && right == null)
height = 0;
else if (left == null) height = right.height + 1;
else if (right == null) height = left.height + 1;
else
if (left.height > right.height) height = left.height + 1;
else height = right.height + 1;
if (root != null) root.UpdateHeight();
}//method UpdateHeight
private Node RotateRight() //returns pivot
{//decrease left side by 1
left.root = root; //update left's root
root = left; //update this root
if (root.right != null)
{//if pivot has right leaf, make this point to it
left = root.right; //root's old left
left.root = this; //make left point to this
}//if
else left = null;
root.right = this;
return root;
}//method RotateRight
private Node RotateLeft() //returns pivot
{//decrease right side by 1
right.root = root; //update right's root
root = right; //update this root
if (root.left != null)
{//if pivot has left leaf, make this point to it
right = root.left; //root's old left
right.root = this; //make right point to this
}//if
else right = null;
root.left = this;
return root;
}//method RotateLeft
private Node Balance(Node leaf) //returns root
{//balancing portion
if (leaf != null)
{//only do something if there is a new leaf
if (right != null && left != null)
{
if (left.height - right.height > 1) return RotateRight();
if (right.height - left.height > 1) return RotateLeft();
}//if
else
{
if (right == null && left.height >= 1) return RotateRight();
if (left == null && right.height >= 1) return RotateLeft();
}//else
}//if
return this;
}//method Balance
}//class Node
}//class BST
}//namespace System.Collections.GenericSo... should I translate into vJASS to be used? : p.
Oh, and I'm not really sure on the practical applications of this, heh. Really, you can have maxed array sized trees without a three crash due to the interface idea of compare, but if you converted that into a plain function call, you could run into a op limit very quickly ;o.
As for practical uses... AI =D, but would need a standard BST and an AVL BST, one for wide scope of decisions and the other for dynamic decision making, or something ;o.
Anyways, you'd be making a seriously advanced AI if you were using this, lol... actually an interesting project could be a generic AI that could learn the game by analyzing information given about the game ;o. That'd be really cool =). Also making AI for specific heroes or spells ;o, like an AI module to run a spell and would work inside of an AI framework. Could use an AVL BST to add your stuff to the AI's decision making =).
Actually, I might start up this AI framework now for OO shared design. That's kinda what I'm doing with my Spawn framework atm, people build modules and put them inside of a framework that runs those modules regardless of what they are. The framework just provides a standard API so everything can interact =).
Yum, AI framework sounds like a good idea : O.
