SCC.121: Fundamentals of Computer Science - Sorting, Trees and Graphs

Flashcards covering dictionary ADT, binary search trees, and self-balancing search trees.

Dictionary (Map) ADT

An ADT with operations insert, delete, and find.

insert(Key k, Value v)

Stores an entry with the key-value pair (k, v). Error if k is already present.

delete(Key k)

Deletes the entry associated with key k. Error if it does not exist.

find(Key k)

Determines whether there is an entry associated with key k. Returns the associated value if it exists, otherwise returns null.

Common implementations of dictionary ADT

Sorted arrays, Search trees, Hashing

Naïve implementation of Dictionary ADT

Storing entries in a linear array without sorting, resulting in O(n) time for find.

Sorted array implementation of Dictionary ADT

Sorting the entries and performing a binary search, resulting in O(log n) time for find but O(n) for updates.

Binary Tree

A tree with at most two children per node: left child and right child.

Binary Search Tree (BST)

A binary tree where each node has a key-value pair, and nodes are sorted by their keys.

Sorted in BST

For every node, its key is greater or equal to all keys in its left subtree and strictly smaller than all keys in its right subtree.

Time Complexity of Find in BST

The worst-case complexity of find() is O(h), where h is the height of the BST.

Height of BST

BST height is between log n and n.

BST Insertion

If x is null, insert new node. If x has key, give error. Else if key < x’s key, recurse left. Else recurse right

Time Complexity of Insertion in BST

For a BST of height h, worst-case time complexity = O(h)

BST Deletion

Find the node to delete. If it's a leaf, remove it. If it has one child, replace it with the child. If it has two children, find the successor, replace the node with the successor, and delete the successor.

Successor of a node

Node in tree with value just above that of provided node value

Operations on a BST

All operations have a worst-case time complexity of O(h), where h is the height.

Self-Balancing Search Trees

Self-balancing search trees that maintain a balanced height to ensure efficient operations.

Examples of Self-Balancing Search Trees

2-3 trees, AVL trees, Red-black trees, B-trees, Splay Trees, Treaps

2-nodes

Nodes with 1 key and 2 children.

3-nodes

Nodes with 2 keys and 3 children.

Find in 2-3 trees

Works almost just as in BSTs.

Insertion in 2-3 Trees

Either a 2-node is transformed into a 3-node, or a 3-node is split into three 2-nodes

Cons of 2-3 Trees

Are quite inconvenient to implement with different types of nodes requiring multiple compares and moving back up the tree to split 4-nodes