Flashcards
Binary Search Trees
Cards in this deck (7)
- 1define binary search treea binary tree s.t.
1. each node contains an element, called a key, such that the keys are comparable, namely there is a strict ordering relation < between keys of different nodes
2. any two nodes have different keys
3.for any node,
— all keys in the left subtree are less than the node's key
— all keys in the right subtree are greater than the node's key.
4. in-order traversal gives the elements in order - 2find(key) finMin() algorithms
- 3findMax() alg
- 4add(key) alg
- 5remove(root, key) alg
- 6—
- 7Computational complexitybest case: when the keys are arranged such that the tree is balanced (all leaves are at the same depth)
worst case: height n-1
Information
- Description
- Computer Science Flashcards on Binary Search Trees, created by Virginie Gagné on 15/04/2022.
- Created by
- Virginie Gagné
- Views
- 1
- Rating