  Binary AIFV codes are lossless codes that generalize the class of
instantaneous FV codes. The code uses two code trees and assigns source symbols
to incomplete internal nodes as well as to leaves. AIFV codes are empirically
shown to attain better compression ratio than Huffman codes. Nevertheless, an
upper bound on the redundancy of optimal binary AIFV codes is only known to be
1, which is the same as the bound of Huffman codes. In this paper, the upper
bound is improved to 1/2, which is shown to coincide with the worst-case
redundancy of the codes. Along with this, the worst-case redundancy is derived
in terms of $p_{\max}\geq$1/2, where $p_{\max}$ is the probability of the most
likely source symbol. Additionally, we propose an extension of binary AIFV
codes, which use $m$ code trees and allow at most $m$-bit decoding delay. We
show that the worst-case redundancy of the extended binary AIFV codes is $1/m$
for $m \leq 4.$
