Cs520 Advanced Analysis of Algorithms and Complexity



Yüklə 198 Kb.
səhifə2/3
tarix17.09.2023
ölçüsü198 Kb.
#144546
1   2   3
CH02- ADT and its specification

Operations for ADT

ADT Design e.g. Lists

    • Every computable function can be computed using Lists as the only data structure!
  • IntList cons(int newElement, IntList oldList)
    • Precondition: None.
    • Postconditions: If x = cons(newElement, oldList) then 1. x refers to a newly created object; 2. x != nil; 3. first(x) = newElement; 4. rest(x) = oldList
  • int first(IntList aList) // access function
    • Precondition: aList != nil
  • IntList rest(IntList aList) // access function
    • Precondition: aList != nil
  • IntList nil //constant denoting the empty list.

Binary Tree

  • A binary tree T is a set of elements, called nodes, that is empty or satisfies:
    • 1. There is a distinguished node r called the root
    • 2. The remaining nodes are divided into two disjoint subsets, L and R, each of which is a binary tree. L is called the left subtree of T and R is called the right subtree of T.
  • There are at most 2d nodes at depth d of a binary tree.
  • A binary tree with n nodes has height at least Ceiling[lg(n+1)] – 1.
  • A binary tree with height h has at most 2h+1 –1 nodes

Stacks

  • A stack is a linear structure in which insertions and deletions are always make at one end, called the top.
  • This updating policy is call last in, first out (LIFO)

Yüklə 198 Kb.

Dostları ilə paylaş:
1   2   3




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin