Flattened Balanced Binary Search Tree, a Hybrid of Balanced Binary Search Tree and B-Tree Supporting Fast Search, Insertion, and Deletion

This article describes the data structure Flattened Balanced Binary Search Tree (FBBST), a container of ordered data supporting fast query, insertion, and deletion. The FBBST combines features from balanced binary search tree (BBST) and B-tree. Different from classical BBSTs, where each node stores a single piece of data, and similar to B-tree, each node of FBBST stores an array of data, and the array must maintain minimum occupancy. Insertion and deletion may cause node splitting and node merging. The advantage of FBBST tree include 1) using fewer pointers as overhead such that more space efficient; 2) data are stored in arrays such that more cache efficient. The FBBST achieves O(log N) complexity in search, insertion, and deletion.

The primary motivation is to transform the leaf layer of a B+ tree, which forms a sorted doubly linked list, into a BBST. The upper levels of B+ trees, which contain only indexes but no data, can be discarded. This BST can then be balanced with techniques like AVL tree and Red-Black tree. As a result, a data structure for an ordered container is obtained with less overhead while achieving high performance. The source code of an implementation using C# is available at

https://github.com/usernamenotavailablenot/Flattened-Balanced-Binary-Search-Tree

with Left Leaning Red-Black (LLRB) tree as the balancing strategy.

1. Data Structure Definition

1.1 Node Structure

Each FBBST node contains:

· An ordered array of keys, where the keys must be comparable

· An array of values at the same length as keys

· A pointer to left child

· A pointer to right child

· A Boolean for color bit (for LLRB balancing)

· An integer indicating the current occupancy.

Formally, a node may be represented as:

private class FBBSTreeNode
{
    private short _len; // one bit for color, other 15 bits for length
    public K[] Keys;
    public V[] Values;
    public FBBSTreeNode? Left;
    public FBBSTreeNode? Right;
    public bool IsRed
    {
        get => _len < 0;
        set
        {
            if (value)
            {
                // red
                _len = (short)(_len | 0b1000000000000000);
            }
            else
            {
                // black
                _len = (short)(_len & 0b0111111111111111);
            }
        }
    }
    public int Len
    {
        get => _len & 0b0111111111111111;
        set
        {
            if (IsRed)
            {
                _len = (short)(value | 0b1000000000000000);
            }
            else
            {
                _len = (short)value;
            }
        }
    }
    public FBBSTreeNode(int capacity)
    {
        Keys = new K[capacity];
        Values = new V[capacity];
        _len = -32768; // 1000000000000000, Red and Len = 0
    }
    public void Shrink(int newLen)
    {
        for (int i = newLen; i < this.Len; ++i)
        {
            this.Keys[i] = default!;
            this.Values[i] = default!;
        }
        this.Len = newLen;
    }
}

1.2 Tree Structure

A FBBST contains:

· A pointer to the root node.

· An immutable integer for array capacity.

· An immutable integer for the lower bound of occupancy

· A Boolean _handleLeaf for element deletion at the leaf node. Its usage is explained in “Deletion” section.

· The constructor creates an empty black node and sets the capacity and lower bound of occupancy.

Formally, a node may be represented as:

public class FBBSTree<K, V> where K : IComparable
{
    private class FBBSTreeNode
    {
        ...
    }

    private readonly int MAX; // capacity
    private readonly int MIN; // quarter of capacity
    private readonly int HALF; // half of capacity
    private FBBSTreeNode _root;
    private bool _isDB = false; // label for double black
    private bool _handleLeaf = false; // predecessor/successor of a leaf node is its parent
    public V? Deleted = default!;
    public FBBSTree(int min)
    {
        MIN = min < 1 ? 1 : (min > 4096 ? 4096 : min);
        HALF = 2 * MIN;
        MAX = 4 * MIN;
        _root = new FBBSTreeNode(MAX);
        _root.IsRed = false;
    }
    ...
}

1.3 Ordering Invariant

Data stored in FBBST follow the order below, which facilitates quick query as described later.

· All keys in the left subtree are strictly less than the minimum of the node keys.

· All keys in the right subtree are strictly greater than the maximum of the node keys.

· Keys within a node are internally sorted.

Figure 1 illustrates an example of a FBBST.

Figure 1. An example of FBBST with LLRB as the balancing strategy. The MIN is set to 1, and the capacity is 4. All the nodes are ordered the same way as BST, and the keys within each node are sorted internally.

1.4 Occupancy Constraints

Upon construction, a FBBST sets up a minimum occupancy MIN and a maximum occupancy MAX, with MAX being the length of the array.

Each FBBST node maintains an occupancy Len, such that

MIN <= node.Len <= MAX

except that the tree contains only one node, which is the root. Current implementation requires the MIN to be at least 1 and sets MAX to be 4 times of MIN, which will be discussed later.

2. Search Algorithm

2.1 Overview

Search proceeds similarly to BST to locate the node. Then, within the node, the search proceeds with binary search in an ordered array. But different from BST, search in FBBST will never hit a null, which behaves the same as B-tree.

2.2 Algorithm

1. If left child is not null and the target key is less than the smallest key, then search the left sub tree recursively.

2. If right child is not null and the target key is greater than greatest key, then search the right sub tree recursively.

3. If the above two conditions are not met, then perform binary search inside the current node.

2.3 Code Snippet for Search

Code implementation is like below.

private static V GetValueRecur(K key, FBBSTreeNode node)
{
    if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
    {
        return GetValueRecur(key, node.Left);
    }
    if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
    {
        return GetValueRecur(key, node.Right);
    }
    bool found = false;
    int idx = FindIndex(node, key, out found); // regular binary search
    if (found)
    {
        return node.Values[idx];
    }
    else
    {
        throw new IndexOutOfRangeException();
    }
}

3. Insertion Algorithm

3.1 Overview

Insertion starts from finding the node and index to insert as described in “Search”. If there is room in the node, then insert at the correct position. Otherwise, this node is split to create a new node, and the new node is added to the BST. Then, BST is balanced by the selected strategy.

When the target node is not full, insertion does not change FBBST structure, which is similar to B-tree, and the target node is not necessarily the leaf. When the target node is full, insertion of the new node behaves similar to BST insertion, in that new node is attached at leaf level.

3.2 Algorithm

1. Find the node and index as described in “Search”.

2. If the key exists, update the value and return.

3. If occupancy is less than the MAX, insert at the correct index in the node and return.

4. Otherwise create a new red node and move right half of the elements from current node to the new node.

5. Insert the new data to the correct node (current node or the new node).

6. Insert the new node as the minimum of the right subtree of current node. Figure 2 illustrates an example of node splitting and node insertion.

7. Balance the BST. Balancing action may propagate to the root level.

The procedures above incorporate features from both BBST and B-tree.

Figure 2. Node splitting. A new node is created to contain right half of the original node. The new node is then inserted to the right subtree as the smallest node.

3.3 Code Snippet for Insertion

The core function for insertion implementation is like below. Insertion may cause node splitting and imbalance of BBST structure. This implementation adopts LLRB tree to restore the balance.

private FBBSTreeNode AddRecur(K key, V value, FBBSTreeNode node)
{
    if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
    {
        node.Left = AddRecur(key, value, node.Left);
        node = ResolveDoubleRed(node); // May cause Double Red violation.
        return node;
    }
    if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
    {
        node.Right = AddRecur(key, value, node.Right);
        node = ResolveRightRed(node); // May cause Right Red violation.
        return node;
    }
    int len = node.Len;
    bool found = false;
    int idx = FindIndex(node, key, out found); // Binary search in an array
    if (found)
    {
        // update
        node.Values[idx] = value;
        return node;
    }
    if (len < MAX)
    {
        // insert
        for (int i = len; i > idx; --i)
        {
            node.Keys[i] = node.Keys[i - 1];
            node.Values[i] = node.Values[i - 1];
        }
        node.Keys[idx] = key;
        node.Values[idx] = value;
        node.Len += 1;
        return node;
    }
    // split
    FBBSTreeNode newNode = SplitNode(node, idx, key, value); // Create a new node to store half of elements
    node.Right = Prepend(newNode, node.Right); // Recursively add the new node to the right subtree
    node = ResolveRightRed(node); // May cause Right Red violation
    return node;
}

4. Deletion Algorithm

4.1 Overview

Deletion starts from finding the node and index as described in “Search”. Then, deletion proceeds as deletion in an array. If the occupancy is below the minimum after deletion, then the occupancy needs to be restored from borrowing from or merging with a neighboring node. The neighboring node is its predecessor or successor if sorted by the keys. Whether to borrow or merge is determined by the occupancy of its neighbor. When two nodes are merged, one node will be deleted from the BST, which will trigger tree balancing actions.

After deletion, if occupancy of the target node is greater than or equal to the minimum, deletion is similar to B-tree. Otherwise, deletion will trigger node borrowing or merging, which is also similar to B-tree. However, node merging will remove a node, and tree balancing follows the procedure of BBST. As shown below, node deletion always starts from the leaf level.

4.2 Algorithm

1. Find the node and index as described in “Search”.

2. If the key does not exist, do nothing and return.

3. Remove at the correct index. If the occupancy is not less than the minimum, do nothing and return.

4. Otherwise, resolve the occupancy by borrowing from or merging with predecessor or successor. Borrowing move some data from one node to another, which does not change tree structure and requires no further action. In contrast, node merging moves all the data in a node to another, and the source node is removed, which may trigger tree balancing actions. There are three scenarios to consider as described below.

i. Current node is leaf. Set the Boolean flag _handleLeaf to true. Return this node and let its parent to decide whether to borrow or merge. A leaf node does not know its predecessor or successor. This Boolean flag notifies its parent, which is either the predecessor or the successor, to handle the situation of occupancy being too low.

ii. Current node has one child. Due to the rules of LLRB tree, the child node is a red leaf at left and the predecessor. If traditional Red-Black tree or AVL tree is adopted, the child node may be the right leaf and the successor.

iii. Current node has two children. The successor is the minimum of the right subtree. Upon merging, the successor is merged into the current node and the successor is deleted from the right sub tree. Figure 3 illustrates an example of node merging and deletion.

Figure 3. Node merging. The elements in the minimum of right subtree are copied to the node. Then, the minimum is deleted from the right subtree.

4.3 Code Snippet for Deletion

The core function for deletion implementation is like below. Deletion may cause “Double Black” and imbalance of BBST structure. This implementation adopts LLRB tree to restore the balance.

private FBBSTreeNode RemoveRecur(K key, FBBSTreeNode node)
{
    if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
    {
        node.Left = RemoveRecur(key, node.Left);
        if (_handleLeaf) // in case the left child is leaf and low occupancy
        {
            HandleLeftLeafOnDelete(node);
            _handleLeaf = false;
        }
        node = ResolveDB(node, node.Left); // Left sub tree may be double black
        return node;
    }
    if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
    {
        node.Right = RemoveRecur(key, node.Right);
        if (_handleLeaf) // in case the right child is leaf and low occupancy
        {
            HandleRightLeafOnDelete(node);
            _handleLeaf = false;
        }
        node = ResolveDB(node, node.Right); // Right sub tree may be double black
        return node;
    }
    bool found = false;
    int idx = FindIndex(node, key, out found);
    if (!found)
    {
        // search miss, do nothing
        return node;
    }
    this.Deleted = node.Values[idx];
    for (int i = idx; i < node.Len - 1; ++i)
    {
        node.Keys[i] = node.Keys[i + 1];
        node.Values[i] = node.Values[i + 1];
    }
    node.Shrink(node.Len - 1);
    if (node.Len >= MIN)
    {
        return node;
    }
    // Node contains too few elements.
    // Leaf
    if (node.Left == null && node.Right == null)
    {
        _handleLeaf = true; // notify the parent to handle low occupancy of child
        return node;
    }
    // One child, only possibility is Left Red for LL RB tree.
    if (node.Left != null && node.Right == null)
    {
        HandleLeftLeafOnDelete(node);
        return node;
    }
    // two children, borrow or merge with its successor, the min of the right sub tree
    node.Right = HandleWithNextOnDelete(node, node.Right!); // recursively find the smallest of right sub tree
    node = ResolveDB(node, node.Right); // Right sub tree may be Double Black due to deletion
    return node;
}

5. Discussion

5.1 Overhead Reduction

Traditional BBSTs require two pointers per piece of data. For FBBST, if a node stores K elements, pointer overhead per element decreases approximately by a factor of K. Additionally, the number of nodes also decrease by a factor of K, which reduces memory allocation and fragmentation.

A FBBST requires an additional integer to store the occupancy, which generally needs two bytes, as the array should not be very long. If using Red-Black tree for balancing strategy, then the two bytes can spare one bit to store the node color.

Compared with a B+ tree, the FBBST eliminates the storage overhead associated with internal index nodes, at the cost of increased tree height.

Space complexity remains at O(N) with improved constant factors due to reduction of overhead.

5.2 Cache Behavior

Compared to traditional BBST, keys in FBBST are stored contiguously in arrays. As a result, spatial locality and cache utilization improve. This can reduce cache misses compared to classical BBSTs.

5.3 Strategy for Tree Balancing

The current implementation adopts the LLRB Tree. Other strategies, such as traditional Red-Black tree or AVL tree, can also be used.

Skip list is similar to BBST. It is generally layers of singly linked lists with each node having forward pointers only. The strategy of storing an array rather than a single piece of data can also be applied to skip list. Due to its structure, it is difficult to locate the predecessor of a node. Therefore, borrowing and merging in element deletion can only involve the successor. One difficult situation is that deletion happens in the last node, which does not have a successor. In this scenario, the rule of minimum occupancy may not apply to the last node.

The difficulty in skip list does not apply to the leaf node of FBBST. Although the leaf node does not know its neighbor, it is guaranteed that the parent node is the predecessor or successor and that the path to the leaf node includes the parent node.

5.4 Relationship to Doubly Linked List

As discussed in the section of “Motivation”, FBBST is equivalent to a sorted doubly linked list. The actions of FBBST in node insertion and deletion can be considered the same as those in doubly linked list. The difference is that FBBST takes O(log N) to locate the target node and its neighbor, whereas doubly linked list takes O(N) and O(1) respectively.

5.5 Load Factor

Load Factor (LF) of FBBST is defined as number of elements divided by the maximum of elements the all the tree nodes can hold, formally as below.

*LF = (Number of Elements) / (MAX (Number of Nodes))

In current implementation, the lower bound of occupancy (MIN) is set to a quarter of MAX. In theory, LF is between 0.25 and 1. Setting the MIN to be a quarter rather than half of MAX is to prevent “thrashing”, which is frequent node splitting and merging due to repeated deletion and insertion of the same key. A lower LF indicates more space has been pre-allocated for future insertion. A higher LF indicates that node splitting is more likely to happen when inserting a new piece of data.

6. Conclusion

This article introduced the FBBST, a container for ordered data by integrating features from BBST and B-tree. By combining tree balancing technique and node occupancy management, FBBST achieves logarithmic asymptotic complexity for search, insertion, and deletion. Compared to BBST and B-tree, preliminary observations suggest that FBBST is more efficient on space and cache utilization.

Complete implementation of FBBST is below. The source code is also available at GitHub

namespace FBBST
{
    public class FBBSTree<K, V> where K : IComparable
    {
        private class FBBSTreeNode
        {
            private short _len; // one bit for color, other 15 bits for length
            public K[] Keys;
            public V[] Values;
            public FBBSTreeNode? Left;
            public FBBSTreeNode? Right;
            public bool IsRed
            {
                get => _len < 0;
                set
                {
                    if (value)
                    {
                        // red
                        _len = (short)(_len | 0b1000000000000000);
                    }
                    else
                    {
                        // black
                        _len = (short)(_len & 0b0111111111111111);
                    }
                }
            }
            public int Len
            {
                get => _len & 0b0111111111111111;
                set
                {
                    if (IsRed)
                    {
                        _len = (short)(value | 0b1000000000000000);
                    }
                    else
                    {
                        _len = (short)value;
                    }
                }
            }
            public FBBSTreeNode(int capacity)
            {
                Keys = new K[capacity];
                Values = new V[capacity];
                _len = -32768; // 1000000000000000, Red and Len = 0
            }
            public void Shrink(int newLen)
            {
                for (int i = newLen; i < this.Len; ++i)
                {
                    this.Keys[i] = default!;
                    this.Values[i] = default!;
                }
                this.Len = newLen;
            }
        }

        private readonly int MAX; // capacity
        private readonly int MIN; // quarter of capacity
        private readonly int HALF; // half of capacity
        private FBBSTreeNode _root;
        private bool _isDB = false; // label for double black
        private bool _handleLeaf = false; // predecessor/successor of a leaf node is its parent
        public V? Deleted = default!;
        public FBBSTree(int min)
        {
            MIN = min < 1 ? 1 : (min > 4096 ? 4096 : min);
            HALF = 2 * MIN;
            MAX = 4 * MIN;
            _root = new FBBSTreeNode(MAX);
            _root.IsRed = false;
        }
        public V GetValue(K key)
        {
            return GetValueRecur(key, _root);
        }
        public bool HasKey(K key)
        {
            return HasValueRecur(key, _root);
        }
        public void Add(K key, V value)
        {
            _root = AddRecur(key, value, _root);
            _root.IsRed = false;
        }
        public void Remove(K key)
        {
            _handleLeaf = false;
            _isDB = false;
            Deleted = default!;
            _root = RemoveRecur(key, _root);
            _handleLeaf = false;
            _isDB = false;
            _root.IsRed = false;
        }
        private static V GetValueRecur(K key, FBBSTreeNode node)
        {
            if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
            {
                return GetValueRecur(key, node.Left);
            }
            if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
            {
                return GetValueRecur(key, node.Right);
            }
            bool found = false;
            int idx = FindIndex(node, key, out found);
            if (found)
            {
                return node.Values[idx];
            }
            else
            {
                throw new IndexOutOfRangeException();
            }
        }
        private static bool HasValueRecur(K key, FBBSTreeNode node)
        {
            if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
            {
                return HasValueRecur(key, node.Left);
            }
            if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
            {
                return HasValueRecur(key, node.Right);
            }
            bool found = false;
            _ = FindIndex(node, key, out found);
            return found;
        }
        private FBBSTreeNode AddRecur(K key, V value, FBBSTreeNode node)
        {
            if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
            {
                node.Left = AddRecur(key, value, node.Left);
                node = ResolveDoubleRed(node);
                return node;
            }
            if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
            {
                node.Right = AddRecur(key, value, node.Right);
                node = ResolveRightRed(node);
                return node;
            }
            int len = node.Len;
            bool found = false;
            int idx = FindIndex(node, key, out found);
            if (found)
            {
                // update
                node.Values[idx] = value;
                return node;
            }
            if (len < MAX)
            {
                // insert
                for (int i = len; i > idx; --i)
                {
                    node.Keys[i] = node.Keys[i - 1];
                    node.Values[i] = node.Values[i - 1];
                }
                node.Keys[idx] = key;
                node.Values[idx] = value;
                node.Len += 1;
                return node;
            }
            // split
            FBBSTreeNode newNode = SplitNode(node, idx, key, value);
            node.Right = Prepend(newNode, node.Right);
            node = ResolveRightRed(node);
            return node;
        }
        private FBBSTreeNode SplitNode(FBBSTreeNode node, int idxAt, K key, V value)
        {
            FBBSTreeNode newNode = new(MAX);
            if (idxAt <= HALF) // in old node
            {
                for (int i = HALF, j = 0; i < MAX; ++i, ++j)
                {
                    newNode.Keys[j] = node.Keys[i];
                    newNode.Values[j] = node.Values[i];
                }
                for (int i = HALF; i > idxAt; --i)
                {
                    node.Keys[i] = node.Keys[i - 1];
                    node.Values[i] = node.Values[i - 1];
                }
                node.Keys[idxAt] = key;
                node.Values[idxAt] = value;
            }
            else // in new node
            {
                int j = 0;
                for (int i = HALF + 1; i < idxAt; ++i, ++j)
                {
                    newNode.Keys[j] = node.Keys[i];
                    newNode.Values[j] = node.Values[i];
                }
                newNode.Keys[j] = key;
                newNode.Values[j] = value;
                ++j;
                for (int i = idxAt; i < MAX; ++i, ++j)
                {
                    newNode.Keys[j] = node.Keys[i];
                    newNode.Values[j] = node.Values[i];
                }
            }
            node.Shrink(HALF + 1);
            newNode.Len = HALF;
            return newNode;
        }
        private FBBSTreeNode RemoveRecur(K key, FBBSTreeNode node)
        {
            if (node.Left != null && key.CompareTo(node.Keys[0]) < 0)
            {
                node.Left = RemoveRecur(key, node.Left);
                if (_handleLeaf)
                {
                    HandleLeftLeafOnDelete(node);
                    _handleLeaf = false;
                }
                node = ResolveDB(node, node.Left);
                return node;
            }
            if (node.Right != null && key.CompareTo(node.Keys[node.Len - 1]) > 0)
            {
                node.Right = RemoveRecur(key, node.Right);
                if (_handleLeaf)
                {
                    HandleRightLeafOnDelete(node);
                    _handleLeaf = false;
                }
                node = ResolveDB(node, node.Right);
                return node;
            }
            bool found = false;
            int idx = FindIndex(node, key, out found);
            if (!found)
            {
                // search miss, do nothing
                return node;
            }
            this.Deleted = node.Values[idx];
            for (int i = idx; i < node.Len - 1; ++i)
            {
                node.Keys[i] = node.Keys[i + 1];
                node.Values[i] = node.Values[i + 1];
            }
            node.Shrink(node.Len - 1);
            if (node.Len >= MIN)
            {
                return node;
            }
            // Node contains too few elements.
            // Leaf
            if (node.Left == null && node.Right == null)
            {
                _handleLeaf = true;
                return node;
            }
            // One child, only possibility is Left Red for LL RB tree.
            if (node.Left != null && node.Right == null)
            {
                HandleLeftLeafOnDelete(node);
                return node;
            }
            // two children, borrow or merge with its successor, the min of the right sub tree
            node.Right = HandleWithNextOnDelete(node, node.Right!);
            node = ResolveDB(node, node.Right);
            return node;
        }
        // Left leaf is short or the parent is short
        private void HandleLeftLeafOnDelete(FBBSTreeNode node)
        {
            int sumLen = node.Len + node.Left!.Len;
            if (sumLen < HALF + MIN)
            {
                // merge from Left child
                MergeFromPre(node, node.Left);
                _isDB = (!node.Left.IsRed);
                node.Left = null;
            }
            else
            {
                if (node.Len < MIN)
                {
                    // node borrows from Left
                    BorrowFromPre(node, node.Left);
                }
                else
                {
                    // Left borrows from node
                    BorrowFromNext(node.Left, node);
                }
                _isDB = false;
            }
        }
        // Right leaf is short.
        private void HandleRightLeafOnDelete(FBBSTreeNode node)
        {
            if (node.Len < HALF)
            {
                // merge right child into this node by append
                MergeFromNext(node, node.Right!);
                _isDB = true; // Right leaf must be BLACK
                node.Right = null;
            }
            else
            {
                // Right leaf borrows from this node
                BorrowFromPre(node.Right!, node);
                _isDB = false;
            }
        }
        private FBBSTreeNode? HandleWithNextOnDelete(FBBSTreeNode pNode, FBBSTreeNode curNode)
        {
            if (curNode.Left == null)
            {
                if (curNode.Len < HALF)
                {
                    // merge
                    MergeFromNext(pNode, curNode);
                    _isDB = (!curNode.IsRed);
                    return null;
                }
                else
                {
                    // pNode borrow from curNode
                    BorrowFromNext(pNode, curNode);
                    _isDB = false;
                    return curNode;
                }
            }
            curNode.Left = HandleWithNextOnDelete(pNode, curNode.Left!);
            curNode = ResolveDB(curNode, curNode.Left);
            return curNode;
        }
        // Add a new node as the smallest to the root
        private static FBBSTreeNode Prepend(FBBSTreeNode newNode, FBBSTreeNode? root)
        {
            if (root == null)
            {
                return newNode;
            }
            root.Left = Prepend(newNode, root.Left);
            root = ResolveDoubleRed(root);
            return root;
        }
        private FBBSTreeNode ResolveDB(FBBSTreeNode parent, FBBSTreeNode? child)
        {
            if (!_isDB)
            {
                return parent;
            }
            if (IsRed(child))
            {
                child!.IsRed = false;
                _isDB = false;
                return parent;
            }
            // Black and DB
            if (parent.Left == child)
            {
                bool pc = parent.IsRed;
                bool px = IsRed(parent.Right!.Left);
                FBBSTreeNode nd = LeftRotation(parent);
                if (!px)
                {
                    nd.Left!.IsRed = true;
                    _isDB = (!pc);
                    return nd;
                }
                else
                {
                    nd.Left = LeftRotation(nd.Left!);
                    nd = RightRotation(nd);
                    nd.Left!.IsRed = false;
                    nd.IsRed = pc;
                    _isDB = false;
                    return nd;
                }
            }
            else // right
            {
                if (parent.IsRed)
                {
                    if (IsRed(parent.Left!.Left))
                    {
                        var nd = RightRotation(parent);
                        nd.Left!.IsRed = false;
                        nd.Right!.IsRed = false;
                        nd.IsRed = true;
                        _isDB = false;
                        return nd;
                    }
                    else
                    {
                        parent.IsRed = false;
                        parent.Left.IsRed = true;
                        _isDB = false;
                        return parent;
                    }
                }
                else // parent is black
                {
                    if (!parent.Left!.IsRed)
                    {
                        if (!IsRed(parent.Left.Left))
                        {
                            parent.Left.IsRed = true;
                            _isDB = true;
                            return parent;
                        }
                        else
                        {
                            var nd = RightRotation(parent);
                            nd.Left!.IsRed = false;
                            _isDB = false;
                            return nd;
                        }
                    }
                    else
                    {
                        var nd = RightRotation(parent);
                        nd.IsRed = false;
                        nd.Right!.Left!.IsRed = true;
                        if (IsDoubleRed(nd.Right.Left))
                        {
                            nd.Right = RightRotation(nd.Right);
                            nd.Right.Left!.IsRed = false;
                            nd = LeftRotation(nd);
                            nd.IsRed = false;
                            nd.Left!.IsRed = true;
                        }
                        _isDB = false;
                        return nd;
                    }
                }
            }
        }
        private static int FindIndex(FBBSTreeNode node, K key, out bool found)
        {
            int lo = 0;
            int hi = node.Len - 1;
            int mid = (lo + hi) / 2;
            while (true)
            {
                if (lo > hi)
                {
                    found = false;
                    return lo;
                }
                int comp = key.CompareTo(node.Keys[mid]);
                if (comp == 0)
                {
                    found = true;
                    return mid;
                }
                if (comp < 0)
                {
                    hi = mid - 1;
                }
                else
                {
                    lo = mid + 1;
                }
                mid = (lo + hi) / 2;
            }
        }
        private static FBBSTreeNode LeftRotation(FBBSTreeNode node)
        {
            var tmp = node.Right;
            node.Right = node.Right!.Left;
            tmp!.Left = node;
            return tmp;
        }
        private static FBBSTreeNode RightRotation(FBBSTreeNode node)
        {
            var tmp = node.Left;
            node.Left = node.Left!.Right;
            tmp!.Right = node;
            return tmp;
        }
        private static bool IsRed(FBBSTreeNode? node)
        {
            if (node == null)
            {
                return false;
            }
            return node.IsRed;
        }
        private static bool IsDoubleRed(FBBSTreeNode? node)
        {
            if (IsRed(node) && IsRed(node!.Left))
            {
                return true;
            }
            return false;
        }
        private static FBBSTreeNode ResolveDoubleRed(FBBSTreeNode node)
        {
            if (IsDoubleRed(node.Left))
            {
                node = RightRotation(node);
                node.Left!.IsRed = false;
            }
            return node;
        }
        private static FBBSTreeNode ResolveRightRed(FBBSTreeNode node)
        {
            if (IsRed(node.Right))
            {
                if (IsRed(node.Left)) // flip color
                {
                    node.Left!.IsRed = false;
                    node.Right!.IsRed = false;
                    node.IsRed = true;
                }
                else
                {
                    bool c = node.IsRed;
                    node = LeftRotation(node);
                    node.Left!.IsRed = true;
                    node.IsRed = c;
                }
            }
            return node;
        }
        private static void ArrayShiftLeft<T>(T[] arr, int curLen, int shiftLeft)
        {
            for (int i = 0; i < curLen - shiftLeft; ++i)
            {
                arr[i] = arr[i + shiftLeft];
            }
        }
        private static void ArrayShiftRight<T>(T[] arr, int curLen, int shiftRight)
        {
            for (int i = curLen - 1; i >= 0; --i)
            {
                arr[i + shiftRight] = arr[i];
            }
        }
        private static void BorrowFromPre(FBBSTreeNode thisNode, FBBSTreeNode pre)
        {
            int sumLen = pre.Len + thisNode.Len;
            int rightShift = sumLen / 2 - thisNode.Len;
            ArrayShiftRight(thisNode.Keys, thisNode.Len, rightShift);
            ArrayShiftRight(thisNode.Values, thisNode.Len, rightShift);
            for (int i = 0, j = pre.Len - rightShift; i < rightShift; ++i, ++j)
            {
                thisNode.Keys[i] = pre.Keys[j];
                thisNode.Values[i] = pre.Values[j];
            }
            thisNode.Len += rightShift;
            pre.Shrink(pre.Len - rightShift);
        }
        private static void BorrowFromNext(FBBSTreeNode thisNode, FBBSTreeNode next)
        {
            int sumLen = next.Len + thisNode.Len;
            int leftShift = sumLen / 2 - thisNode.Len;
            for (int i = thisNode.Len, j = 0; j < leftShift; ++i, ++j)
            {
                thisNode.Keys[i] = next.Keys[j];
                thisNode.Values[i] = next.Values[j];
            }
            ArrayShiftLeft(next.Keys, next.Len, leftShift);
            ArrayShiftLeft(next.Values, next.Len, leftShift);
            thisNode.Len += leftShift;
            next.Shrink(next.Len - leftShift);
        }
        private static void MergeFromPre(FBBSTreeNode thisNode, FBBSTreeNode pre)
        {
            int rightShift = pre.Len;
            ArrayShiftRight(thisNode.Keys, thisNode.Len, rightShift);
            ArrayShiftRight(thisNode.Values, thisNode.Len, rightShift);
            for (int i = 0; i < rightShift; ++i)
            {
                thisNode.Keys[i] = pre.Keys[i];
                thisNode.Values[i] = pre.Values[i];
            }
            thisNode.Len += rightShift;
        }
        private static void MergeFromNext(FBBSTreeNode thisNode, FBBSTreeNode next)
        {
            for (int i = thisNode.Len, j = 0; j < next.Len; ++i, ++j)
            {
                thisNode.Keys[i] = next.Keys[j];
                thisNode.Values[i] = next.Values[j];
            }
            thisNode.Len += next.Len;
        }
    }
}