Please enable JavaScript.

Coggle requires JavaScript to display documents.

MM7 - Coggle Diagram

- - - - All the vertices on the simple path from the root to the vertex v
    - - Where the vertix itself is not an ancestor of itself
    - - Last vertix before the vertix
    - - First vertix after the parent vertix
    - - Vertix without children
    - - All the descendants of a vertix
  - - - Ordered tree with no more than two children (left child and right child)
      - Binary Search Tree
        
        Every vertex is assigned a number and each parental vertex is larger than all the numbers in its left subtree
        
        Efficiency depends on the tree's height
        
        n = nodes / h = height
        
        Implemented using nodes
- - - - The root is visited before the left and right subtrees are visited
    - - the root is visited after visiting its left subtree but before visiting the right subtree
    - - the root is visited after visiting the left and right subtrees
- - - - If the tree is empty, the search ends in failure
      - If the tree is not empty, we compare v with the tree's root K(r)
      - If v and K(r) match, a desired element is found and the search is stopped
      - If they do not match, we continue with the search in the left subtree of the root if v < K(r) and in the right subtree if v > K(r)
    - - worst case: Θ(n)
      - avarage case: Θ( log n)