BST

1.0

BST.ps1


<#PSScriptInfo
 
.VERSION 1.0
 
.GUID 21e4c4a1-f8ea-47f7-b7d6-78026b8ec8d0
 
.AUTHOR Igor Iric, IricIgor@GMail.com
 
.COMPANYNAME
 
.COPYRIGHT
 
.TAGS PowerShell Class Binary Search Tree
 
.LICENSEURI
 
.PROJECTURI https://www.linkedin.com/pulse/my-powershell-modules-igor-iric
 
.ICONURI https://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Binary_Search_Tree_-_Remove_Step_3.svg/320px-Binary_Search_Tree_-_Remove_Step_3.svg.png
 
.EXTERNALMODULEDEPENDENCIES
 
.REQUIREDSCRIPTS
 
.EXTERNALSCRIPTDEPENDENCIES
 
.RELEASENOTES
 
 
#> 

<#
 
.DESCRIPTION
BST - Binary Search Tree class is example class build according to PowerShell 5 class syntax.
    It can be used for fast processing of large data structures, where standard PowerShell filtering will be inefficient. Example can be large structures with more than 10,000 elements.
    For more information read Wikipedia article https://en.wikipedia.org/wiki/Binary_search_tree
 
#> 


class BST {

#region Properties


#
# Properties
#

$Value            # property containing value which is compared to other nodes, can be any comparable object i.e. int, decimal, string, etc.
[psobject]$Data   # property containing data which will be displayed to user
$Prev             # reference to previous node in the tree
$Next             # reference to next node in the tree
#endregion

#region Constructors


#
# Constructors
#

#
#
# Constructor with 1 argument
# value : creates one node with value and without data
# array : creates BST with array with Value,Data pairs
#
#

BST ($Value) {

    if ($Value -isnot [array]) {

    #
    # one argument, no array
    # only value information
    #
        $this.Value  = $Value
        $this.Data   = $null

    } else {

    #
    # one argument, array
    # array with .value and .data properties
    #

        if (($Value.Value) -and ($Value.Data)) {
            $this.Value  = $Value[0].Value
            $this.Data   = $Value[0].Data
            $Value | Select-Object -Skip 1 | % {$this.Add($_.Value,$_.Data)}
        } else {
            throw 'Constructor array has to have Value and Data properties'
        }
    }    
}


#
#
# Constructor with 2 arguments
# value, value : creates one node with value and data properties
# array, array : creates tree from value and data arrays
#
#

BST ($Value,$Data) {

    if (($Value -isnot [array]) -and ($data -isnot [array])) {
    #
    # two arguments, no array
    # Constructor with two simple values
    #
        $this.Value  = $Value
        $this.Data   = $Data

    } elseif (($Value -is [array]) -and ($data -is [array])) {
    #
    # two arguments, both arrays
    # Constructor from two arrays
        if ($Value.Count -ne $Data.Count) {
            throw 'Array constructor must be used with same sized arrays'
        }
        
        $this.Value = $Value[0]
        $this.Data  = $Data[0]
        for ($i=1; $i -lt ($Value.Count); $i++) {
            $this.Add($Value[$i],$Data[$i])
        }

    } else {
        # one array, one simple value
        throw 'Constructor cannot be called with one array and one primitive value'
    }
}


#
#
# Constructor with 3 arguments
# array,array,$false : creates the same as 2 arg constructor
# array,array,$true : creates balanced tree from sorted array
#
#

BST ($ValueArray,$DataArray,[bool]$Sorted) {

    # arguments validation, first two arguments must be same sized arrays
    if (($ValueArray -isnot [array]) -or ($DataArray -isnot [array])) {
        throw 'Array constructor must be used with two arrays'
    }

    if ($ValueArray.Count -ne $DataArray.Count) {
        throw 'Array constructor must be used with two identically sized arrays'
    }

    if (!($Sorted)) {
    #
    # array, array, $false creates BST from non sorted array
    #

        $this = [BST]::new($ValueArray,$DataArray)
    } else {
    #
    # array, array, $true
    # Create balanced tree from sorted array
    #
        $Last = $ValueArray.Count -1
        $MidEl = [int]($Last /2)

        $this.Value = $ValueArray[$MidEl]
        $this.Data  = $DataArray[$MidEl]

        if ($MidEl -gt 0) {
            $Arr = 0..($MidEl-1)
            $this.Prev = [ref]([BST]::new($ValueArray[$Arr],$DataArray[$Arr],$true))
        }

        if ($MidEl -lt $Last) {
            $Arr = ($MidEl+1)..$Last
            $this.Next = [ref]([BST]::new($ValueArray[$Arr],$DataArray[$Arr],$true))
        }

    }
}
#endregion


#region Node Methods


#
#
# Methods working on Node
# Methods return properties reading only value of provided node, not entire tree
#
#


#
# [psobject]Node
# returns pair (value, data) for one node
#
[psobject]Node () {
    return ($this | Select Value,Data)
}

#
# [string] Direction
# determines to which direction next value should be added
#

[string]Direction ($Value) {
    if ($Value -lt ($this.Value)) {
        Return 'Prev'
    } else {
        Return 'Next'
    }
}

#endregion

#region Tree Properties Methods

#
#
# Tree Properties Methods
# Methods return certain properties of tree, without updating it
#
#


#
# [int]Count
# Return count of nodes in the tree
#

[int]Count () {
    
    if ($this.Prev -ne $null) {$P = ($this.Prev.Value).Count()} else {$P=0}
    if ($this.Next -ne $null) {$N = ($this.Next.Value).Count()} else {$N=0}

    Return ($P + $N + 1)
}


#
# [psobject]Find ($Value)
# Finds element in the tree, and return its data
#

[psobject]Find ($Value) {
    if (($this.Value) -eq $Value) {
        Return ($this.Data)
    } else {
        $Direction = $this.Direction($Value)
        if (($this.($Direction)) -eq $null) {
            Return $null
        } else {
            Return ($this.($Direction).Value).Find($Value)
        }
    }
}


#
# [psobject]FindAll ($Value)
# Finds element(s) in the tree, and return their data
#

[psobject]FindAll ($Value) {
    $Found = @()
    if (($this.Value) -eq $Value) {
        $Found += $this.Data
    }

    $Direction = $this.Direction($Value)
    if ($this.($Direction)) {
        $Found += ($this.($Direction).Value).FindAll($Value)
    }

    Return $Found
}



#
# [psobject]FindNode ($Value)
# Finds element in the tree, and return its reference object
#

[psobject]FindNode ($Value) {
    if (($this.Value) -eq $Value) {
        Return $this
    } else {
        $Direction = $this.Direction($Value)
        if (($this.($Direction)) -eq $null) {
            Return $null
        } else {
            Return ($this.($Direction).Value).FindNode($Value)
        }
    }
}


#
# [psobject]FindNodes ($Value)
# Finds element(s) in the tree, and return its reference object(s)
#

[psobject]FindNodes ($Value) {
    $Found = @()
    if (($this.Value) -eq $Value) {
        $Found += $this
    } 
    $Direction = $this.Direction($Value)
    if ($this.($Direction)) {
        $Found += ($this.($Direction).Value).FindNodes($Value)
    }
    Return $Found
}

#
# [BST[]]Print
# Returns sorted array of elements in format value, data
#

[psobject[]]Print () {
    
    $Arr = @()
    if ($this.Prev) {$Arr += ($this.Prev.Value).Print()}
    $Arr += $this.Node()
    if ($this.Next) {$Arr += ($this.Next.Value).Print()}

    Return $Arr        
}


#
# Depth
# [int] returns depth of the tree
#

[int]Depth () {
    
    if ($this.Prev) {$P = ($this.Prev.Value).Depth()} else {$P=0}
    if ($this.Next) {$N = ($this.Next.Value).Depth()} else {$N=0}

    if ($P -gt $N) {
        Return ($P+1)
    } else {
        Return ($N+1)
    }
}


#
# Level
# [psobject[]] Returns elements on n-th level
#

[psobject[]]Level ([int]$n) {

    $Arr = @()

    if ($n -lt 0) {
        throw 'BST Level has to be zero or more'
    } elseif ($n -eq 0) {
        $Arr += $this.Node()
    } else {
        if ($this.Prev) {$Arr += ($this.Prev.Value).Level($n-1)}
        if ($this.Next) {$Arr += ($this.Next.Value).Level($n-1)}
    }

    return $Arr
}

#
# [decimal]Balance
# Return value which indicates how well tree is balanced
# values -1/+1 means tree is completly disbalanced to prev/next side
# 0 means tree is perfectly balanced
#

[decimal]Balance () {

    if ($this.Prev) {$P = ($this.Prev.Value).Count()} else {$P=0}
    if ($this.Next) {$N = ($this.Next.Value).Count()} else {$N=0}
    if ($P+$N -gt 0) {
        Return ($N-$P)/($N+$P)
    } else {
        Return $null
    }
}

[string[]]ToString () {
    $Result = @()
    $R = '|'+($this.Data.ToString())+'|'
    if ($this.Prev) {$P = ($this.Prev.Value).ToString()} else {$P=@()}
    if ($this.Next) {$N = ($this.Next.Value).ToString()} else {$N=@()}
    $PL = $P[0].Length
    $NL = $N[0].Length
    $Result += ((' '*$PL) + $R + (' '*$NL))
    while ($P.Count -lt $N.Count) {$P += ' '*$PL}
    while ($N.Count -lt $P.Count) {$N += ' '*$NL}
    for ($i=0; $i -lt ($P.Count); $i++) {$Result += $P[$i] +'|'+ (' '*($R.Length-2))+ '|'+ $N[$i]}
    return $Result
}


#
# [BST]ToBalanced ()
# Returns balanced BST
#

[BST]ToBalanced () {
    $Array = $this.Print()
    return ([BST]::new($Array.Value,$Array.Data,$true))
}


#
# [bool]IsBST ()
# Verifies if given tree is really BST
#

[bool]IsBST () {
    $Result = $true
    if ($Result -and ($this.Prev)) {     # check previous node
        $PValue = $this.Prev.Value.Value # value of previous node
        if ($this.Direction($PValue) -ne 'Prev') {$Result = $false}
    }
    if ($Result -and ($this.Next)) {     # check next node
        $NValue = $this.Next.Value.Value # value of next node
        if ($this.Direction($NValue) -ne 'Next') {$Result = $false}
    }
    if ($Result -and ($this.Prev)) {     # check previous tree
        $Result = $this.Prev.Value.IsBST()
    }
    if ($Result -and ($this.Next)) {     # check next tree
        $Result = $this.Next.Value.IsBST()
    }
    return $Result
}

#
# [BST]Parent ([BST]$root)
# Returns parent node while starting search from $root node
#

[BST]Parent ([BST]$root) {
    $Node = $root
    $Parent = $null
    do {
        $Direction = $Node.Direction($this.Value)
        $Child = $Node.$Direction.Value
        if ($Child) {
            if ($Child -eq $this) {$Parent = $Node}
            else {$Node = $Child}
        }
    } while ($Child -and (!($Parent)))

    return $Parent
}

#endregion

#region Tree Updating Methods

#
#
# Tree Updating Methods
# Methods which update tree
#
#

#
# [void]Add
# Adding new node to the tree
#

Add($Value,$Data) {
    
    # Determine direction of adding
    $Direction = $this.Direction($Value)

    if (($this.($Direction)) -eq $null) {
        # if direction is empty, add it directly
        $this.($Direction) = [ref]([BST]::new($Value,$Data))
    } else {
        # if direction is not empty, call adding to that node
        ($this.($Direction).Value).Add($Value,$Data)
    }
}

#
# [void]Delete
# Deleting node from the tree
#

Delete([BST]$root) { # delete node from a tree
    $PrevN = $this.Prev
    $NextN = $this.Next
    $Parent = $this.Parent($root)
    $Direction = $Parent.Direction($this.Value)

    if ((!($PrevN)) -and (!($NextN))) {
        # just delete if no children
        $Parent.$Direction = [PSObject]$null
    } elseif ((!($PrevN)) -or (!($NextN))) {
        # one child, replace it
        if ($PrevN) {$Child = $this.Prev.Value}
        else {$Child = $this.Next.Value}
        $Parent.$Direction = $Child
    } else {
        # two children, do the magic
    }
}

Delete([string]$Direction) { # delete child node
    if ($this.($Direction)) {
        $this.($Direction) = $null
    }
}



#endregion

} # end of BST class