avl

AVL Binary search trees (without duplicates) + Unordered lists with log time insertion/removal, implementation in Python 3.

API:

Node class:
- elt: stored data
- n: tuple of left/right nodes
- h: tuple of left/right heights
- s: tuple of left/right subtree sizes
- fix(node,b): sets the left or right node of the original node, and rebalances the tree
- traverse(check,ret,use,x): inorder traversal of the subtree of given node (with x set to the index of the node)
  - check(node,x): boolean function that terminates traversal when True
  - ret(node,x): function called on each traversed node, returning desired information
  - use(al,a,ar): function that combines information from node and both subtrees, and passes upwards
    
    Note that the default values of al and ar (for an empty subtree) are always (None,0).
  As an example, the following call returns the maximum of a non-empty Ulist u:
```
check = lambda n, x: 0
ret = lambda n, x: n.elt
z = lambda a, b: max(a, b) if b else a
use = lambda al, a, ar: z(z(a, al[0]), ar[0])
return u.h.traverse(check, ret, use, u.h.s[0])[0]
```
AVL class:
- h: root Node of tree (None if empty)
- find(elt): binary searches the position where elt should be inserted in the tree
- get(i): get the value stored at index i
- add(elt): add elt to the tree
- delt(elt): remove elt from the tree if present
- dpos(i): remove elt stored at index i
- disp(): returns string containing the contents of the tree
Ulist class (extends AVL):
- add(elt,i): inserts elt before index i (or appends to end if i is unassigned)
- find(elt): returns the first index of an element equal to elt, or -1 if none exist

abertell/avl

avl