Binary Tree Ontology

AI SEARCH

FLOW ALGEBRA — BINARY TREE ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/data-structures/binary-tree-ontology.html

FLOW BINARY_TREE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Binary Tree Ontology"
    PURPOSE = "Formalise binary trees, nodes, left and right child relations, roots, subtrees, structural forms, traversal, insertion, deletion, depth, height, invariants and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    BINARY_TREE
    ROOTED_BINARY_TREE
    FULL_BINARY_TREE
    COMPLETE_BINARY_TREE
    PERFECT_BINARY_TREE
    BALANCED_BINARY_TREE
    DEGENERATE_BINARY_TREE
    SKEWED_BINARY_TREE
    LEFT_SKEWED_TREE
    RIGHT_SKEWED_TREE
    BINARY_SEARCH_TREE
    NODE
    ROOT_NODE
    INTERNAL_NODE
    LEAF_NODE
    PARENT_NODE
    CHILD_NODE
    LEFT_CHILD
    RIGHT_CHILD
    SIBLING_NODE
    ANCESTOR
    DESCENDANT
    LEFT_SUBTREE
    RIGHT_SUBTREE
    EDGE
    VALUE
    KEY
    DEPTH
    HEIGHT
    LEVEL
    PATH
    NODE_COUNT
    LEAF_COUNT
    OPERATION
    CREATE
    INSERT
    DELETE
    SEARCH
    ACCESS
    UPDATE
    TRAVERSE
    PREORDER_TRAVERSAL
    INORDER_TRAVERSAL
    POSTORDER_TRAVERSAL
    LEVEL_ORDER_TRAVERSAL
    ROTATE_LEFT
    ROTATE_RIGHT
    INVARIANT
    ROOT_INVARIANT
    ACYCLICITY_INVARIANT
    CONNECTIVITY_INVARIANT
    PARENT_INVARIANT
    BINARY_ARITY_INVARIANT
    STRUCTURAL_INVARIANT
    ORDERING_INVARIANT
    BALANCE_INVARIANT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    POINTER
    REFERENCE
    MEMORY
    IMPLEMENTATION
    MUTABLE_BINARY_TREE
    IMMUTABLE_BINARY_TREE
    PERSISTENT_BINARY_TREE
    STRUCTURAL_SHARING
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_NODE
    HAS_ROOT
    HAS_EDGE
    HAS_KEY
    HAS_VALUE
    PARENT_OF
    CHILD_OF
    LEFT_CHILD_OF
    RIGHT_CHILD_OF
    SIBLING_OF
    ANCESTOR_OF
    DESCENDANT_OF
    HAS_LEFT_SUBTREE
    HAS_RIGHT_SUBTREE
    ROOT_OF
    CONNECTED_TO
    PRECEDES
    FOLLOWS
    HAS_DEPTH
    HAS_HEIGHT
    HAS_LEVEL
    HAS_PATH
    HAS_NODE_COUNT
    HAS_LEAF_COUNT
    INSERTS
    DELETES
    SEARCHES
    ACCESSES
    UPDATES
    TRAVERSES
    ROTATES
    HAS_INVARIANT
    HAS_ORDERING
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    POINTS_TO
    REFERENCES
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    BINARY_TREE_SPECIFICATIONS
    BINARY_TREE_IMPLEMENTATIONS
    SOURCE_CODE
    NODE_DATA
    KEY_AND_VALUE_DATA
    LEFT_AND_RIGHT_CHILD_DATA
    ROOT_DATA
    EDGE_DATA
    TRAVERSAL_TRACES
    SEARCH_TRACES
    INSERTION_TRACES
    DELETION_TRACES
    ROTATION_TRACES
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    MEMORY_DATA
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_BINARY_TREE_IDENTIFIERS
    NORMALISE_BINARY_TREE_TYPES
    NORMALISE_NODE_IDENTIFIERS
    NORMALISE_KEY_AND_VALUE_TYPES
    NORMALISE_LEFT_AND_RIGHT_CHILD_RELATIONS
    NORMALISE_PARENT_RELATIONS
    NORMALISE_DEPTH_HEIGHT_AND_LEVEL
    NORMALISE_TRAVERSAL_NAMES
    NORMALISE_OPERATION_NAMES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_TREE_NODE_AND_EDGE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS BINARY_TREE_REASONING_PIPELINE {
    BINARY_TREE_REFERENCE
      -> TREE_IDENTIFICATION
      -> BINARY_TREE_TYPE_RESOLUTION
      -> ROOT_RESOLUTION
      -> NODE_AND_LEFT_RIGHT_CHILD_MAPPING
      -> STRUCTURAL_PROPERTY_ANALYSIS
      -> OPERATION_MAPPING
      -> INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS STRUCTURE_REASONING {
    BINARY_TREE
      -> ROOT_NODE

    NODE
      -> OPTIONAL_LEFT_CHILD
      -> OPTIONAL_RIGHT_CHILD

    EACH_NODE
      -> CHILD_COUNT <= 2

    NONROOT_NODE
      -> PARENT_NODE

    NODE_AND_EDGE_SET
      -> CONNECTIVITY_AND_ACYCLICITY_CHECK
  }

  PROCESS SUBTREE_REASONING {
    NODE
      -> LEFT_CHILD

    LEFT_CHILD
      -> LEFT_SUBTREE

    NODE
      -> RIGHT_CHILD

    RIGHT_CHILD
      -> RIGHT_SUBTREE

    SUBTREE
      -> BINARY_TREE_RECURSIVE_STRUCTURE
  }

  PROCESS DEPTH_HEIGHT_REASONING {
    ROOT_NODE
      -> DEPTH = 0

    CHILD_NODE
      -> DEPTH = PARENT_DEPTH + 1

    LEAF_NODE
      -> HEIGHT = 0

    INTERNAL_NODE
      -> HEIGHT = 1 + MAX(LEFT_CHILD_HEIGHT, RIGHT_CHILD_HEIGHT)

    TREE_HEIGHT
      -> ROOT_HEIGHT
  }

  PROCESS STRUCTURAL_CLASSIFICATION {
    BINARY_TREE
      -> NODE_CHILD_COUNTS_AND_LEVELS

    ALL_INTERNAL_NODES_HAVE_TWO_CHILDREN
      -> FULL_BINARY_TREE_CANDIDATE

    ALL_LEVELS_FILLED_EXCEPT_POSSIBLY_LAST
      + LAST_LEVEL_FILLED_LEFT_TO_RIGHT
      -> COMPLETE_BINARY_TREE_CANDIDATE

    ALL_INTERNAL_NODES_HAVE_TWO_CHILDREN
      + ALL_LEAVES_SAME_DEPTH
      -> PERFECT_BINARY_TREE_CANDIDATE

    EACH_INTERNAL_NODE_HAS_ONE_CHILD
      -> DEGENERATE_BINARY_TREE_CANDIDATE
  }

  PROCESS TRAVERSAL_REASONING {
    PREORDER
      -> VISIT_NODE
      -> TRAVERSE_LEFT_SUBTREE
      -> TRAVERSE_RIGHT_SUBTREE

    INORDER
      -> TRAVERSE_LEFT_SUBTREE
      -> VISIT_NODE
      -> TRAVERSE_RIGHT_SUBTREE

    POSTORDER
      -> TRAVERSE_LEFT_SUBTREE
      -> TRAVERSE_RIGHT_SUBTREE
      -> VISIT_NODE

    LEVEL_ORDER
      -> VISIT_NODES_BY_INCREASING_DEPTH
  }

  PROCESS SEARCH_REASONING {
    GENERAL_BINARY_TREE_SEARCH
      -> TRAVERSAL_STRATEGY

    TRAVERSAL_STRATEGY
      -> VISIT_NODE

    VISIT_NODE
      -> TARGET_COMPARISON

    MATCH
      -> RETURN_NODE

    NO_MATCH
      -> CONTINUE_TRAVERSAL

    EXHAUSTED_TREE
      -> NOT_FOUND
  }

  PROCESS INSERTION_REASONING {
    INSERTION_REQUEST
      -> TREE_TYPE_SPECIFIC_INSERTION_POLICY

    INSERTION_POLICY
      -> TARGET_PARENT_AND_CHILD_POSITION

    NEW_NODE
      -> ATTACH_AS_LEFT_OR_RIGHT_CHILD

    ATTACH
      -> UPDATE_PARENT_RELATION

    RESULT
      -> RECOMPUTE_STRUCTURAL_PROPERTIES
      -> INVARIANT_CHECK
  }

  PROCESS DELETION_REASONING {
    TARGET_NODE
      -> TREE_TYPE_SPECIFIC_DELETION_POLICY

    DELETION
      -> DETACH_OR_REPLACE_NODE

    REPLACEMENT_IF_REQUIRED
      -> UPDATE_LEFT_RIGHT_AND_PARENT_RELATIONS

    RESULT
      -> RECOMPUTE_STRUCTURAL_PROPERTIES
      -> INVARIANT_CHECK
  }

  PROCESS ROTATION_REASONING {
    ROTATION_TARGET
      -> LOCAL_PARENT_CHILD_STRUCTURE

    LEFT_ROTATION
      -> PROMOTE_RIGHT_CHILD
      -> REASSIGN_INTERMEDIATE_SUBTREE

    RIGHT_ROTATION
      -> PROMOTE_LEFT_CHILD
      -> REASSIGN_INTERMEDIATE_SUBTREE

    RESULT
      -> UPDATE_PARENT_LEFT_AND_RIGHT_RELATIONS
      -> CHECK_BINARY_ARITY_AND_OTHER_INVARIANTS
  }

  PROCESS COMPLEXITY_REASONING {
    BINARY_TREE + OPERATION
      -> NODE_COUNT_AND_HEIGHT

    GENERAL_SEARCH
      -> VISITED_NODE_COUNT

    TRAVERSAL
      -> NODE_COUNT

    PATH_BASED_OPERATION
      -> PATH_LENGTH_OR_HEIGHT

    IMPLEMENTATION
      -> AUXILIARY_MEMORY_REQUIREMENTS

    COSTS
      -> TIME_AND_SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_BINARY_TREE_STATE(T1)
      + UPDATE
      -> NEW_TREE_STATE(T2)

    T2
      -> COPY_CHANGED_ROOT_TO_TARGET_PATH_IF_REQUIRED

    T1 + T2
      -> STRUCTURAL_SHARING

    T1
      -> PRESERVED
  }

  RULES {
    IF BINARY_TREE_IS_ASSERTED
    THEN REQUIRE EACH_NODE_HAS_AT_MOST_TWO_CHILDREN

    IF LEFT_CHILD_IS_ASSERTED
    THEN CHILD_MUST_BE_DISTINGUISHED_FROM_RIGHT_CHILD_IN_SAME_PARENT_CONTEXT

    IF NONROOT_NODE_EXISTS
    THEN REQUIRE ONE_PARENT_IN_STANDARD_TREE_CONTEXT

    IF FULL_BINARY_TREE_IS_ASSERTED
    THEN REQUIRE EACH_INTERNAL_NODE_HAS_EXACTLY_TWO_CHILDREN

    IF COMPLETE_BINARY_TREE_IS_ASSERTED
    THEN REQUIRE LEVEL_FILL_AND_LEFT_PACKING_CONDITION

    IF PERFECT_BINARY_TREE_IS_ASSERTED
    THEN REQUIRE FULL_STRUCTURE_AND_EQUAL_LEAF_DEPTH

    IF BINARY_SEARCH_TREE_ORDERING_IS_USED
    THEN DO_NOT GENERALISE_ORDERING_TO_ALL_BINARY_TREES

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND BINARY_TREE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        TREE_IDENTITY_CERTAINTY,
        BINARY_TREE_TYPE_CERTAINTY,
        NODE_IDENTITY_COMPLETENESS,
        LEFT_RIGHT_CHILD_COMPLETENESS,
        ROOT_CERTAINTY,
        OPERATION_TRACE_COMPLETENESS,
        INVARIANT_EVIDENCE_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF LEFT_OR_RIGHT_CHILD_DATA_IS_PARTIAL
    THEN REDUCE_STRUCTURE_AND_CLASSIFICATION_CONFIDENCE

    IF TREE_TYPE_IS_UNKNOWN
    THEN REDUCE_TYPE_SPECIFIC_OPERATION_CONFIDENCE

    IF COMPLETE_NODE_AND_EDGE_DATA_CONFIRM_STRUCTURE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        BINARY_TREE_IDENTIFIER,
        BINARY_TREE_TYPE,
        NODE_IDENTIFIER,
        KEY_OR_VALUE_TYPE,
        IMPLEMENTATION,
        LANGUAGE_RUNTIME_CONTEXT
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    BINARY_TREE != BINARY_SEARCH_TREE
    BINARY_TREE != BALANCED_BINARY_TREE
    FULL_BINARY_TREE != COMPLETE_BINARY_TREE
    COMPLETE_BINARY_TREE != PERFECT_BINARY_TREE
    BALANCED_BINARY_TREE != PERFECT_BINARY_TREE
    LEFT_CHILD != RIGHT_CHILD
    NODE != KEY
    NODE != VALUE
    ROOT_NODE != LEAF_NODE_IN_GENERAL
    DEPTH != HEIGHT
    INORDER_TRAVERSAL != SORTED_ORDER_FOR_GENERAL_BINARY_TREE
    ROTATION != GENERAL_REORDERING_WITHOUT_STRUCTURAL_CONTEXT
    BINARY_TREE_SEARCH != BINARY_SEARCH_TREE_SEARCH
    PERSISTENT_BINARY_TREE != MUTABLE_BINARY_TREE
    COMPLEXITY_DEPENDS_ON_STRUCTURE_HEIGHT_OPERATION_AND_IMPLEMENTATION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_BINARY_TREE_IDENTIFIER
    CHECK_BINARY_TREE_TYPE
    CHECK_ROOT
    CHECK_NODE_IDENTITIES
    CHECK_LEFT_CHILD_RELATIONS
    CHECK_RIGHT_CHILD_RELATIONS
    CHECK_PARENT_RELATIONS
    CHECK_BINARY_ARITY
    CHECK_CONNECTIVITY
    CHECK_ACYCLICITY
    CHECK_DEPTH_HEIGHT_AND_LEVEL
    CHECK_STRUCTURAL_CLASSIFICATION
    CHECK_TRAVERSALS
    CHECK_SEARCH
    CHECK_INSERTION_AND_DELETION
    CHECK_ROTATIONS
    CHECK_INVARIANTS
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PERSISTENCE
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_BINARY_TREE_ENTITIES
    BINARY_TREE_TYPE_RELATIONS
    ROOT_RELATIONS
    NODE_AND_EDGE_RELATIONS
    LEFT_AND_RIGHT_CHILD_RELATIONS
    PARENT_RELATIONS
    ANCESTOR_DESCENDANT_RELATIONS
    LEFT_AND_RIGHT_SUBTREE_RELATIONS
    DEPTH_HEIGHT_AND_LEVEL_RELATIONS
    STRUCTURAL_CLASSIFICATION_RELATIONS
    TRAVERSAL_RELATIONS
    SEARCH_RELATIONS
    INSERTION_RELATIONS
    DELETION_RELATIONS
    ROTATION_RELATIONS
    BINARY_TREE_STATE_TRANSITIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    PERSISTENCE_AND_STRUCTURAL_SHARING_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON BINARY_TREE_OPERATION {
      NORMALISE
      RESOLVE_TREE_NODE_AND_EDGE_IDENTITIES
      UPDATE_NODE_SET
      UPDATE_LEFT_RIGHT_AND_PARENT_RELATIONS
      UPDATE_ROOT_IF_REQUIRED
      RECOMPUTE_DEPTH_HEIGHT_AND_CLASSIFICATION
      RECHECK_INVARIANTS
      UPDATE_OPERATION_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON IMPLEMENTATION_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_COMPLEXITY
      RECHECK_TREE_TYPE_AND_INVARIANTS
      RECHECK_SEMANTIC_EQUIVALENCE
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_BINARY_TREE
      BY_TREE_TYPE
      BY_ROOT
      BY_NODE
      BY_LEFT_CHILD
      BY_RIGHT_CHILD
      BY_PARENT
      BY_SUBTREE
      BY_DEPTH
      BY_HEIGHT
      BY_TRAVERSAL
      BY_OPERATION
      BY_INVARIANT
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_BINARY_TREE_STRUCTURE
      ANALYSE_LEFT_AND_RIGHT_SUBTREES
      COMPUTE_DEPTH_AND_HEIGHT
      CLASSIFY_BINARY_TREE_STRUCTURE
      TRACE_TRAVERSALS
      ANALYSE_SEARCH
      TRACE_INSERTIONS
      TRACE_DELETIONS
      ANALYSE_ROTATIONS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_INVARIANTS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_BINARY_TREE_FROM_BINARY_SEARCH_TREE
      DISTINGUISH_FULL_COMPLETE_PERFECT_AND_BALANCED_FORMS
      DISTINGUISH_LEFT_FROM_RIGHT_CHILD_RELATIONS
      PRESERVE_TREE_TYPE_ROOT_STRUCTURE_IMPLEMENTATION_LANGUAGE_AND_RUNTIME_CONTEXT
      DISTINGUISH_GENERAL_BINARY_TREE_TRAVERSAL_FROM_ORDERED_SEARCH
      PRESERVE_BINARY_TREE_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_BINARY_TREE_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              BINARY_TREE_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW