Binary Search Trees and Their Operations

Binary Search Tree (BST)

A binary tree optimized for searching items.

Node Properties

Node's value is bounded by its subtrees.

Record

Group of related fields, not same type.

Field

Data element within a record.

Search Key

Identifies a record within a collection.

KeyedItem Class

Contains search key and access method.

Traversal Types

Preorder, inorder, postorder for BST.

Deletion Cases

Leaf, one child, or two children scenarios.

BinarySearchTree Class

Extends BinaryTreeBasis with additional features.

Efficiency of Operations

Height determines max comparisons for operations.

Minimum Height Theorem

Minimum height is ⌈log2(n+1)⌉.

Treesort Efficiency

Average: O(n * log n), Worst: O(n²).

General Tree

An n-ary tree with n children per node.

Shape Efficiency

Tree shape affects operation efficiency.