AVL
AVL represents a self balancing binary tree where the heights of the two child subtrees of any node differ by at most one. Instantiate an empty Avl tree below
Usage
Avl(comparator: Callable = lambda x, y: x >= y)
Parameters:
comparator : Callable
A lambda function to relatively order the items in the Avl tree
Comparators should be defined in the following format: (x, y) => x >= y
Methods
| Method | Description |
|---|---|
| search | Search for an item in the tree |
| insert | Insert an element into the tree |
| delete | Delete an element from the tree |
| min | Find the smallest element in the tree |
| max | Find the largest element in the tree |
| successor | Finds the next biggest element after "item" |
| predecessor | Finds the next smallest element after "item" |
| rank | Finds the rank of a particular item |
| select | Given the rank, find the associated item |
| in_order | Conduct an in order traversal of the tree and output the result in a list |
| pre_order | Conduct a pre order traversal of the tree and output the result in a list |
| post_order | Conduct a post order traversal of the tree and output the result in a list |
| Prints the type of traversal |
Example
from jellybeans.structures import Avltree = Avl(lambda x,y: len(x) >= len(y))