Treap is a data structure that is a combination of binary search tree and heap. e.g. Each node has key and value. Key belongs to BST rule and value belongs to heap rule.
k-d tree is a binary search tree that represents the node value as k-dimensional coordinates, and how the left and right branches go depends on the layer of tree (e.g. 1: x, 2: y, 3: z, 4: x, ...). This data structure is typically used for nearest neighbor algorithm.
red-black tree is a binary search tree that is balanced by coloring nodes red or black by some rules. (insertion and deletion video links are in the description below the video.)
splay tree is a binary search tree that lets the root always be a target of the search so it enables O(1) for accessing the data. this is often used for cache algorithm. shape of the tree is kept by rotation depending on zig-zag, zig-zig, and zig pattern.
concept of balanced binary search tree and how to rotate for balancing the tree. balanced binary search tree is a binary search tree that lets the search cost always O(log n) by making it balanced (not skewed).
van Emde Boas Trees is a data structure that divides a binary search tree into multiple sub trees for making the times of seek less. (You don't have to visit every node from root like binary search tree. You can just seek root of the sub trees first.)
1
Advanced Data Structures: Treaps
K-d Tree in Python #3 — Finale
23-Tree Intuition and Definition
Red-Black Trees - Data Structures
Splay Tree Introduction
AVL tree removals
Balanced binary search tree rotations
Cache Oblivious Search
