Flashcards
Binary Search Trees
Flashcards do 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
Informações
- Descrição
- Computer Science FlashCards sobre Binary Search Trees, criado por Virginie Gagné em 15-04-2022.
- Criado por
- Virginie Gagné
- Visualizações
- 1
- Avaliação