Options
All
  • Public
  • Public/Protected
  • All
Menu

Class Bst<T, S>

A binary search tree implementation for finding ranges within the tree and finding neighboring nodes.

template

T - The type stored in the tree.

template

S - The type used by search functions, but that cannot be added to the tree. It defaults to T.

Type parameters

  • T: S

  • S

Hierarchy

  • Bst

Index

Constructors

constructor

Properties

bst_root

bst_root: BstNode<T> | undefined = undefined

cmp

Methods

_getInorderSuccessor

  • _getInorderSuccessor(object: S, node?: BstNodePtr<T>): object | undefined
  • A method designed mostly for internal use that finds the next element in the tree if all of the elements were placed in order.

    Parameters

    • object: S

      The object or search type to find the successor of

    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    Returns object | undefined

add

  • Add an element to the tree.

    Parameters

    • object: T

      The object to add to the tree.

    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    Returns void

eqcmp

  • eqcmp(a: S, b: S): boolean

getGteq

  • Get all the objects greater than or equal to an object or search type.

    Parameters

    • value: S

      The search type or object at which to start a search.

    Returns BstNode[]

getLteq

  • Get all the objects less than or equal to an object or search type.

    Parameters

    • value: S

      The search type or object at which to end a search.

    Returns BstNode[]

getRange

  • getRange(start: S, endm1: S): BstNode[]
  • Get all the objects in a range.

    Parameters

    • start: S

      The search type or object at which to start a search.

    • endm1: S

      The search type or object at which to end a search inclusively. The name is endm1 to stand for END Minus 1 since the search is performed inclusively.

    Returns BstNode[]

gtcmp

  • gtcmp(a: S, b: S): boolean

gteqcmp

  • gteqcmp(a: S, b: S): boolean

operateOnAll

  • Perform an operation on all nodes.

    Parameters

    • operation: NodeOp<T>

      The function to run on each node.

    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    Returns void

operateOnAllGteq

  • Perform an operation on all of the elements greater than or equal to a search type or object.

    Parameters

    • value: S

      The search type or object at which to start a search.

    • operation: NodeOp<T>

      The function to run on each node.

    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    Returns void

operateOnAllLteq

  • Perform an operation on all of the elements less than or equal to a search type or object.

    Parameters

    • value: S

      The search type or object at which to end a search.

    • operation: NodeOp<T>

      The function to run on each node.

    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    Returns void

operateOnAllRange

  • operateOnAllRange(start: S, endm1: S, operation: NodeOp<T>, node?: BstNode<T>, undef?: boolean): void
  • Perform an operation on all of the elements in a range.

    Parameters

    • start: S

      The search type or object at which to start a search.

    • endm1: S

      The search type or object at which to end a search inclusively. The name is endm1 to stand for END Minus 1 since the search is performed inclusively.

    • operation: NodeOp<T>

      The function to run on each node.

    • Default value node: BstNode<T> = this.bst_root

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    • Default value undef: boolean = false

      TODO: Fix

    Returns void

remove

  • Remove an element from the tree.

    Parameters

    • object: S

      The object to remove or a search type that is evaluated to the same value as an object in the tree. Equivalence is determined exclusively using the compare function.

    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')

      The node in the tree where the search can be started. It's optional and does not need to be changed for nearly all use cases.

    Returns void

toString

  • toString(): string

Generated using TypeDoc