Karteikarten
Binary Search Trees
Karten in diesem Stapel (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
Informationen
- Beschreibung
- Computer Science Karteikarten am Binary Search Trees, erstellt von Virginie Gagné am 15/04/2022.
- Erstellt von
- Virginie Gagné
- Aufrufe
- 1
- Bewertung