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.

Type parameters

  • T: S

    The type stored in the tree.

  • S

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

Hierarchy

  • Bst

Index

Constructors

Properties

Methods

Constructors

constructor

Properties

bst_root

bst_root: BstNode<T> | undefined = undefined

cmp

cmp: DualCompareFunction<S>

Methods

_getInorderSuccessor

  • _getInorderSuccessor(object: S, node?: BstNodePtr<T>): { data: T; ptr: BstNodePtr<T> } | 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 { data: T; ptr: BstNodePtr<T> } | 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

create_range_search

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

  • operateOnAll(operation: NodeOp<T>, sequential?: boolean, node?: BstNodePtr<T>): void

  • Perform an operation on all nodes.

    Parameters

    • operation: NodeOp<T>

      The function to run on each node.

    • Default value sequential: boolean = true

      If true, operation will be called sequentially. If false, operation will be called for the root node first, then children.

    • 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

  • operateOnAllGteq(value: S, operation: NodeOp<T>, sequential?: boolean, node?: BstNodePtr<T>): void

  • 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 sequential: boolean = true

      If true, operation will be called sequentially. If false, operation will be called for the root node first, then children.

    • 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

  • operateOnAllLteq(value: S, operation: NodeOp<T>, sequential?: boolean, node?: BstNodePtr<T>): void

  • 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 sequential: boolean = true

      If true, operation will be called sequentially. If false, operation will be called for the root node first, then children.

    • 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(object: S, filter?: (data: T) => boolean, node?: BstNodePtr<T>): void

  • 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 filter: (data: T) => boolean = (): boolean => true

      An optional function that has the final say in whether a node is removed. While an object is provided for quick tree traversal, it is not always desirable to remove every node with that particular value. This function allows the user to override that behavior.

        • (data: T): boolean

        • Parameters

          • data: T

          Returns boolean

    • 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

search

  • Parameters

    • search: RangeSearch<S>
    • Default value node: BstNodePtr<T> = new MemberPtr(this, 'bst_root')
    • Default value map: {} = {}
      • [key: string]: T[]

    Returns {}

    • [key: string]: T[]

toString

  • toString(): string

Generated using TypeDoc