AVL(3)

💖 AVL(3) 💖

okay so bestie, this is AVL(3) from the Library Functions Manual, and it's literally the whole vibe for balanced trees in memory. no cap, it's giving "data structures but make it cute." let's go ✨

---

🌸 NAME 🌸

The icons in question, fr fr:

• mkavltree
• insertavl
• lookupavl
• deleteavl
• avlwalk
• avlnext
• avlprev
• endwalk

all of them: AVL tree routines 🎀

---

✨ SYNOPSIS ✨

#include <u.h>
#include <libc.h>
#include <avl.h>
typedef struct Avl Avl;
struct Avl
{
       Avl    *p;           /* parent */
       Avl    *n[2];        /* children */
       int    bal;          /* balance bits */
};
Avl    *avlnext(Avlwalk *walk);
Avl    *avlprev(Avlwalk *walk);
Avlwalk       *avlwalk(Avltree *tree);
void   deleteavl(Avltree *tree, Avl *key, Avl **oldp);
void   endwalk(Avlwalk *walk);
void   insertavl(Avltree *tree, Avl *new, Avl **oldp);
Avl    *lookupavl(Avltree *tree, Avl *key);
Avl    *searchavl(Avltree *tree, Avl *key, int neighbor);
Avltree       *mkavltree(int(*cmp)(Avl*, Avl*));

like, look at that struct. p is the parent, n[2] is the children, bal is the balance bits. tiny little icon, honestly. 👑

---

🦋 DESCRIPTION 🦋

So an AVL tree is a self-balancing binary search tree — yes, it balances itself, main character energy, no supervision needed — and these routines let you make and maintain in-memory AVL trees. 🫶

You get an empty AVL tree by calling mkavltree with a comparison function as its argument. That function should take two pointers to Avl objects and return -1, 0 or 1 depending on whether the first is respectively less than, equal to, or greater than the second. periodt.

insertavl adds a new tree node into tree. If oldp is non-nil upon return, it points to storage for an old node with the same key that may now be freed. (so like, free it, bestie 💅)

lookupavl returns the tree node that matches key by tree's comparison function, or nil if there's none to be found. 😭

searchavl returns the tree node that matches key by tree's comparison function, if it exists. If it does not exist:

• and neighbor is positive → it returns the nearest node whose key is greater, or nil if there is none
• and neighbor is negative → it returns the nearest node whose key is less, or nil if there is none

⚠️ setting neighbor to values other than -1, 0, or +1 is an error. not a vibe. don't.

deleteavl removes the node matching key from tree; oldp is handled as per insertavl.

avlwalk returns a pointer to a newly-allocated Avlwalk object. endwalk frees such an object. avlnext and avlprev walk the tree associated with walk, returning the next (respectively, previous) tree node in the comparison order defined by the comparison function associated with the tree associated with walk. yes, that sentence nests like that, it's iconic, iykyk. 🌈

---

🎀 EXAMPLES 🎀

So the intended usage seems to be: make an anonymous Avl the first member of your application's tree-node structure, then pass these routines tree-node pointers instead of Avl*s. literally the hack, slay.

typedef struct Node {
       Avl;
       uchar  score[VtScoreSize];
       int    type;
} Node;
Avltree *tree;
Avl *res;
Node *np;
...
       res = lookupavl(tree, np);

---

💜 SOURCE 💜

/src/libavl

---

⭐ SEE ALSO ⭐

• G. M. Adelson-Velsky, E. M. Landis, ``An algorithm for the organization of information'', Soviet Mathematics, Vol. 3, pp. 1256—1263.

like they literally invented the thing, show some respect 💀👑

---

🍓 DIAGNOSTICS 🍓

Functions returning pointers return nil on error. that's it, that's the whole energy. 🙈

---

and that's the page!! 🧚 it's AVL(3) from the Library Functions Manual, the source is /src/libavl, and the footer signs off with just AVL(3) again — no date on this one, so nothing to report, bestie. 💖✨🌸