Fichas
Binary Search Trees
Fichas del conjunto (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
Información
- Descripción
- Computer Science Fichas sobre Binary Search Trees, creado por Virginie Gagné el 15/04/2022.
- Creado por
- Virginie Gagné
- Visitas
- 1
- Valoración