Probabilistic AVL Trees (p-AVL): Relaxing Deterministic Balancing
arXiv:2604.02223v1 Announce Type: new Abstract: This paper studies the empirical behaviour of the p-AVL tree, a probabilistic variant of the AVL tree in which each imbalance is repaired with probability $p$. This gives an exact continuous interpolation from $p = 0$, which recovers the BST endpoint, to $p = 1$, which recovers the standard AVL tree. Across random-order insertion experiments, we track rotations per node, total imbalance events, average depth, average height, and a global imbalance statistic $\sigma$. The main empirical result is that even small nonzero p already causes a strong structural change. The goal here is empirical rather than fully theoretical: to document the behaviour of the p-AVL family clearly and identify the main patterns.
View PDF HTML (experimental)
Abstract:This paper studies the empirical behaviour of the p-AVL tree, a probabilistic variant of the AVL tree in which each imbalance is repaired with probability $p$. This gives an exact continuous interpolation from $p = 0$, which recovers the BST endpoint, to $p = 1$, which recovers the standard AVL tree. Across random-order insertion experiments, we track rotations per node, total imbalance events, average depth, average height, and a global imbalance statistic $\sigma$. The main empirical result is that even small nonzero p already causes a strong structural change. The goal here is empirical rather than fully theoretical: to document the behaviour of the p-AVL family clearly and identify the main patterns.
Comments: 22 pages,15 figures
Subjects:
Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2604.02223 [cs.DS]
(or arXiv:2604.02223v1 [cs.DS] for this version)
https://doi.org/10.48550/arXiv.2604.02223
arXiv-issued DOI via DataCite (pending registration)
Submission history
From: Hayagriv Desikan [view email] [v1] Thu, 2 Apr 2026 16:14:03 UTC (2,992 KB)
Sign in to highlight and annotate this article
Conversation starters
Daily AI Digest
Get the top 5 AI stories delivered to your inbox every morning.
More about
announceglobalpaper
The bar is lower than you think
TL;DR: The efficient market hypothesis is a lie, there are no adults, you don't have to be as cool as the Very Cool People to contribute something, your comparative advantage tends to feel like just doing the obvious thing, and low hanging fruit is everywhere if you pay attention. The Very Cool People are anyways not so impossible to become; and perhaps most coolness is gated behind a self belief of having nothing to add. So put more out into the world, worry less about whether people already know or find it boring. At worst you'll be slightly annoying. How can you know, if you haven't even tried? Recently I've been commenting more on LessWrong [1] . This place is somehow the best [2] forum for sane reasoned discussion on the internet besides small academic-gated communities. A lot of post
Knowledge Map
Connected Articles — Knowledge Graph
This article is connected to other articles through shared AI topics and tags.
More in Research Papers
Development and multi-center evaluation of domain-adapted speech recognition for human-AI teaming in real-world gastrointestinal endoscopy
Automatic speech recognition (ASR) is a critical interface for human-AI interaction in gastrointestinal endoscopy, yet its reliability in real-world clinical settings is limited by domain-specific terminology and complex acoustic conditions. Here, we present EndoASR, a domain-adapted ASR system designed for real-time deployment in endoscopic workflows. We develop a two-stage adaptation strategy based on synthetic endoscopy reports, targeting domain-specific language modeling and noise robustness. In retrospective evaluation across six endoscopists, EndoASR substantially improves both transcrip — Ruijie Yang, Yan Zhu, Peiyao Fu
Memory in the LLM Era: Modular Architectures and Strategies in a Unified Framework
Memory emerges as the core module in the large language model (LLM)-based agents for long-horizon complex tasks (e.g., multi-turn dialogue, game playing, scientific discovery), where memory can enable knowledge accumulation, iterative reasoning and self-evolution. A number of memory methods have been proposed in the literature. However, these methods have not been systematically and comprehensively compared under the same experimental settings. In this paper, we first summarize a unified framework that incorporates all the existing agent memory methods from a high-level perspective. We then ex — Yanchen Wu, Tenghui Lin, Yingli Zhou
Human-Guided Reasoning with Large Language Models for Vietnamese Speech Emotion Recognition
Vietnamese Speech Emotion Recognition (SER) remains challenging due to ambiguous acoustic patterns and the lack of reliable annotated data, especially in real-world conditions where emotional boundaries are not clearly separable. To address this problem, this paper proposes a human-machine collaborative framework that integrates human knowledge into the learning process rather than relying solely on data-driven models. The proposed framework is centered around LLM-based reasoning, where acoustic feature-based models are used to provide auxiliary signals such as confidence and feature-level evi — Truc Nguyen, Then Tran, Binh Truong
Discussion
Sign in to join the discussion
No comments yet — be the first to share your thoughts!