Advanced Trees

Self-balancing binary search trees

• 2-3 tree
• AA tree
• AVL tree
• Red-black tree
• splay tree
• scapegoat tree
• treap

B tree

self-balancing tree. nodes can have a variable number of child nodes within a pre-defined range. (2-3 tree)

it's a generalization of binary search tree in that a node can have more than 2 children. unlike self-balancing binary search trees, it's optimized for systems that read and write large blocks of data.

It's a good exmaple of data structure for external memory, commonly used in database and filesystems.

k-d tree

space-partitioning data strucutre for organizing pointers in K-D space.

quadtree

most often used to partition a 2-D space by recursively subdividing it into 4 quadrants or regions.