A weighting based ABR Tree
A algorithm used to improve Red-Black Tree
I'm a software engineer who is a member of Joey Lee's team. My major job in this team is shim module maintenance.
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.
- 2022 October 1 - 05:45
- 15 min
- Main Track
- openSUSE.Asia Summit 2022