Please enable JavaScript.

Coggle requires JavaScript to display documents.

Data Structures - Coggle Diagram

- - - - Every node is either red or black.
      - The root is black.
      - Every leaf is NIL and is black.
      - If a node is red, then both its children are black.
      - For each node, all simple paths from the node to descendant leaves contain the same number of
      - black nodes.
- - - - D.Init() Initialize the hash table Θ(1) Θ(1) Θ(1)
        
        D.Insert(Key K, Data D) Append (K,D) to linked list at h(K) Θ(1) Θ(1) Θ(1)
        
        D.Retrieve(Key K) Return the data associated with key K Θ(1) Θ(1 + n
        
        m) Θ(n)
        
        D.Member(Key K) Return true if key K is in the table Θ(1) Θ(1 + n
        
        m) Θ(n)
        
        D.Add(Key K, int x) Add x to the data associated with key K Θ(1) Θ(1 + n
        
        m) Θ(n)
        
        D.Replace(Key K, Data D′) Replace data associated with K with D′Θ(1) Θ(1 + n
        
        m) Θ(n)
        
        D.Delete(Key K) Remove (K,D) from the table Θ(1) Θ(1 + n
        
        m) Θ(n)
  - - - Open Address Hashing Resolves collisions by rehashing
        
        D.Init() Initialize the hash table Θ(1) Θ(1) Θ(1)
        
        D.Insert(Key K, Data D) Insert (K,D) into table at h(K,j) Θ(1) Θ(1) Θ(n)
        
        D.Retrieve(Key K) Return the data associated with key K Θ(1) Θ(1) Θ(n)
        
        D.Member(Key K) Return true if key K is in the table Θ(1) Θ(1) Θ(n)
        
        D.Add(Key K, int x) Add x to the data associated with key K Θ(1) Θ(1) Θ(n)
        
        D.Replace(Key K, Data D′) Replace data associated with K with D′Θ(1) Θ(1) Θ(n)
        
        D.Delete(Key K) Flag (K,D) as deleted Θ(1) Θ(1) Θ(n)
        
        n = Number of elements in the Hash Table, m = Size of the Hash Table