Binary Search Trees

These flashcards cover key concepts related to Binary Search Trees (BSTs), their operations, and important characteristics as discussed in the lecture.

What is a Binary Search Tree (BST)?

A binary tree in symmetric order where each node's key is larger than all keys in its left subtree and smaller than all keys in its right subtree.

What operations can be supported by a Symbol Table in BSTs?

Ordered operations like insert, delete, get, floor, ceiling, rank, and select.

How is a node represented in a BST in Java?

A node is composed of a key, a value, references to left and right subtrees, and may include a count of nodes in its subtree.

What is the time complexity for search operations in an unsorted array?

O(n) for worst-case scenarios.

What does the term 'height of a tree' refer to?

The maximum depth among all its nodes.

What do the terms 'floor' and 'ceiling' refer to in the context of BSTs?

Floor is the largest key in the BST that is less than or equal to a given key, while ceiling is the smallest key that is greater than or equal to the given key.

What happens when inserting keys into a BST in a random order regarding expected height?

The expected height of the resulting BST is approximately ~ log(n) where n is the number of keys inserted.

What is the Hibbard deletion in a BST?

A method for deleting a node in a BST where you search for the node containing the key and handle cases based on its children.

What is the purpose of storing subtree counts in BST nodes?

To efficiently compute the rank of a key and facilitate select operations.

How is 'rank' defined in the context of a BST?

Rank is defined as the count of keys that are less than a given key.

What characteristics of applications make them suitable for using BSTs?

Dynamic data insertions, updates, deletions, and operations like finding max/min or rank.

What is the worst-case performance for search and insert operations in a BST?

O(n) when the tree is unbalanced.

What is an important feature of inorder traversal in a BST?

It yields the keys in ascending order.

What does a 'successful search' in a BST entail?

Starting at the root, navigate left for lesser keys and right for greater keys until the key is found.