Draft:Zip Tree

• Comment: Invented 2018 but only one source after 2018 KylieTastic (talk) 19:23, 5 March 2024 (UTC)

---

AVL tree
Type	Tree
Invented	2018
Invented by	Robert E. Tarjan, Caleb C. Levy and Stephen Timmel
Complexities in big O notation
Space complexity Space ${\text{Θ}}(n)$ Time complexity Function Amortized Worst Case Search ${\text{Θ}}(\log n)$. ${\text{O}}(\log n)$ Insert ${\text{Θ}}(\log n)$ ${\text{O}}(\log n)$ Delete ${\text{Θ}}(\log n)$ ${\text{O}}(\log n)$

In computer science, zip trees are a type of randomized binary search tree which each node in a zip tree is assigned a numeric rank, with the tree maintaining a max-heap order based on these ranks.

This structure allows for efficient insertions and deletions without the need for rotations, using a process called zipping and unzipping. The rank of each node is randomly chosen from a geometric distribution, allowing for a compact representation of the tree. Zip trees require only ${\text{O}}(\log \log n)$ bits to represent the largest rank in an n-node binary search tree.

Zip trees closely resemble two well-known data structures: the treap and the skip list

Definition

Spine

The spine of a node refers to a specific path originating from that node. The left spine is defined by the sequence of nodes reached by consecutively following the left child from a given node x until reaching the node with the smallest key within x's subtree. Conversely, the right spine is established by tracing the path through right children from x, ending at the node with the largest key in x's subtree.

Property

The expected rank of the root in a zip tree is at most $\lg n+3$.

For any c > 0, the root rank is at most $(c+1)\lg n$.

Operations

Zip trees are characterized by three principal operations: insertion, deletion, and search.

Search

Searching for a specific value in a zip tree can be done the same way as that of any binary search tree. The running time complexity of a zip tree search is O(h) where h is the height of the tree.

Insert

To insert a new node x, the tree is searched to locate the node y that x will replace. This is determined by the condition that y's rank is less than or equal to x's rank, with a strict inequality if y's key is less than x's key.

Following this, the search path for x is split into two paths: P, containing nodes with keys less than x's key, and Q, containing nodes with keys greater than x's key. The process of splitting these paths is known as "unzipping".

The top node of P becomes x's left child, and the top node of Q becomes its right child. If y had a parent z before the insertion, x is made a child of z, replacing y. If y was the root, x becomes the new root​

Delete

Deletion is the inverse of insertion. To delete a node x, we first do a search for the node x to be deleted.

Let P and Q be the right spine of the left subtree of x and the left spine of the right subtree of x. Zip P and Q to form a single path R by merging them from top to bottom in non-increasing rank order, breaking a tie in favour of the smaller key. Zipping preserves the left subtrees of the nodes on P and the right subtrees of the nodes on Q.

Finally, if x had a parent z, make the top node of R(or null if R is empty) the left or right child of z, depending on whether the key of x is less than or greater than that of z, respectively (the top node of R replaces x as a child of z); if x is the root, make the top node of R the root.

Adventages

The advantages of zip trees over similar data structures like treap can be summarized in terms of operational simplicity and space efficiency:

Operational Simplicity: Zip trees employ straightforward "zip" and "unzip" operations for insertions and deletions, which are conceptually simpler than the sequences of rotations used in treaps. This simplicity potentially makes zip trees easier to understand, implement, and maintain, reducing the cognitive load associated with complex rotation sequences found in other tree structures.

Space Efficiency and Structure: Zip trees utilize random ranks for organizing keys, similar to treaps. However, the ranks in zip trees require only ${\text{Θ}}(\log \log n)$ bits each, in contrast to the ${\text{Θ}}(\log n)$ bits required for key labels in treaps. This reduced bit requirement for ranks translates into more space-efficient storage of tree nodes. Furthermore, zip trees are topologically isomorphic to skip lists, meaning they share the same overall structure but achieve this with less space, further enhancing their efficiency.