No video of the event yet, sorry!

RED-BLACK Tree and AVL Tree have been applied in skb structure in Linux kernel or in searching the IP routing information based table(RIB) for a long time. If more insertions or deletions are needed, then RB-Tree is used. On the other hand, when searching is the key point, then AVL-Tree is suggested. This is because, after running a long time, RB-Tree tends to become a skew tree which means the total search path is longer than AVL-Tree.

In this paper, a new algorithm is proposed to improve this skew issue of RB-Tree.

Currently, the structure of Red-Black Tree is only equivalent to the B-Tree of order 4, not for B-Tree of any order. When order increases, we cannot make use any insertion algorithm of Red-Black Tree any more, and thus the sequential search loading will be heavier when searching a key located in a long link list inside B-Tree.

In this paper, we provide a homogeneous Red-Black Tree like insertion algorithm which can be applied to any order of B-Tree, including a B-Tree of order 4 of course. This algorithm will combine 3 concepts, AVL tree, B-Tree and RB-Tree, together, so called ABR-Tree. So that we can make use of all advantages of self-balancing of AVL Tree, shorter depth path of B-Tree and an amortized rotation of RB-Tree simultaneously.