Current Research in the field of data structures ( Articles under submission ) :

***** Towards a Path Reducer in Binary Search Trees

Abstract

We propose a maintenance algorithm running in O(lg(n)) to reduce the length of a path in a binary search tree of size n (lg being the base-2 logarithm). This algorithm can be applied after a search, insert or delete operation in a binary search tree.

The proposed algorithm goes back in the path and simulates restructurings (single or double rotations) on triples of consecutive nodes by calculating heights before and after the restructurings. If the heights decrease, the restructurings become real.

We will show that the algorithm applied after operations on unbalanced binary search tree reduces its depth and therefore improves its performance.

We will also show that the proposed algorithm applied to a set of inserted elements produces an AVL tree and thus provides another simpler expression for building an AVL tree.

***** M-PBBST(n1, n2) : Multiple Partially Balanced Binary Search Trees in One

Abstract

In this paper, a novel binary search tree is introduced that has the capability to generate well-known data structures like Red-Black trees, AA trees, 2-3 trees, and several other previously unknown structures. The proposed data structure achieves this by partitioning the elements of a binary search tree into unbalanced sub-trees, with heights ranging from n1 to n2-1, where n1 is between 0 and n2-2, and n2 is greater than 1.

One of the notable advantages of the proposed approach is its simplicity. The algorithms involved are straightforward and easy to understand. Additionally, the implementation of the algorithms requires only a few extra bits of storage at each tree node. This efficiency in terms of storage is highly desirable as it minimizes the memory overhead associated with the data structure.

Another significant feature of the proposed approach is the utilization of a single code to cover all generated data structures. This means that instead of writing separate code for each data structure, a unified codebase can be used to handle the construction and manipulation of various tree shapes. This simplifies the implementation process and reduces code duplication.

Furthermore, the worst-case height of the generated trees is  

where N  represents the number of elements in the tree. This is an important characteristic as it guarantees efficient search, insertion, and deletion operations in terms of time complexity. A logarithmic worst-case height ensures that the tree remains balanced and balanced trees typically exhibit better overall performance compared to highly skewed structures.

***** Relaxed AVL Trees with Extra Nodes

Abstract

A modification to the AVL tree is proposed, allowing for relaxation without requiring additional space. The original AVL tree implementation utilizes two extra bits per node to maintain tree balance, employing only three configurations to represent possible balance factors.

We take advantage of the fourth configuration to introduce extra nodes into the AVL tree. These additional nodes have no impact on the rebalancing process.

Consequently, the resulting data structure, known as the AVL-2 tree, can adjust its height, enabling faster or slower search, insert, and delete operations depending on the specific needs of the application.

The height of the AVL-2 tree is at most 2.88 lg2(N), where N represents the size of the tree and lg2 denotes the base 2 logarithm.

Unlike other data structures, an unsuccessful search can terminate at an internal node, and nearly 80% of the data can be deleted with a maximum of two pointer changes.

***** Improving the Red-Black Tree Delete Algorithm 

Abstract

Today, Red-Black trees are becoming a popular data structure typically used to implement dictionaries, associative arrays, symbol tables within some compilers (C++, Java …) and many other systems.  

In this paper, we present an improvement of the delete algorithm of this kind of binary search tree.

The suggested algorithm appears to be promising as it gives the tree a different coloring while reducing the number of color changes and maintenance operations by a factor of roughly 29% and 11%, respectively.  

The new coloring favors the presence of red nodes and therefore speeds up the deletion operation.

It also saves about 4 % on running time when insert and delete operations are used together while conserving search performance of the standard algorithm.