binary search trees

binary search trees

• each node is greater than every node in its left subtree

• each node is less than every node in its left subtree

what are the BST operations?

1. insert

2. search

3. delete

BST insert

• start at root

• always insert as a leaf

BST Search/Find

• start at root

• compare to see if less than or greater than root; proceed to corresponding subtree and repeat process

BST delete (leaf node)

• just delete that specific node

• does NOT affect the rest of the tree

BST delete (1 child)

• replace node with its child

  • greater or less based on which subtree it is

BST delete (2 child)

• find next higher node

what are the advantages of binary search trees?

1. speed - O(logn)