Open In App

Introduction to Finger search tree Data Structure

Last Updated : 14 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

A finger search tree is a data structure that is designed to allow for efficient search and access of data in a set or a sequence. It is a type of binary search tree that uses a “finger” or a reference to a particular element in the tree to quickly find and retrieve other elements. In this article, we will explore the types, advantages, disadvantages, and implementation codewise of a finger search tree data structure.

Below is an example structure of a Finger Search Tree:

Finger Tree Search Example

Finger Tree Search Example

Types of Finger Search Tree:

There are several types of finger search trees, including the binary search tree (BST), the red-black tree (RBT), and the AVL tree. Each type of finger search tree has its own set of rules for inserting and deleting elements, balancing the tree, and maintaining the finger reference.

  • The BST is the simplest type of finger search tree, where each node has at most two children – a left child and a right child. The finger reference in a BST is a pointer to a node in the tree.
  • The RBT is a more complex type of finger search tree that uses color-coded nodes to balance the tree. The finger reference in an RBT is a pointer to a node in the tree, and the color of the node is used to determine how the tree is balanced.
  • The AVL tree is a self-balancing type of finger search tree that uses a height balance factor to maintain balance. The finger reference in an AVL tree is a pointer to a node in the tree, and the height balance factor is used to determine how the tree is balanced.

Implementation of Finger Search Tree:

Here are the implementation steps for a finger tree data structure along with sample code for performing search operations:

Step 1: Define the basic building blocks of the finger tree, i.e., the nodes and the annotations. A node can either be a leaf node or a tree node. A leaf node contains a single element, whereas a tree node contains two subtrees and an annotation that summarizes the information about the elements in those subtrees.

C++
#include <bits/stdc++.h>
using namespace std;

class Leaf {
public:
    int value;
    Leaf(int v)
        : value(v)
    {
    }
};

class TreeNode {
public:
    Leaf* left;
    Leaf* right;
    string annotation;
    TreeNode(Leaf* l, Leaf* r)
        : left(l)
        , right(r)
    {
    }
};
Java
class Leaf {
    public int value;
    public Leaf(int v) {
        value = v;
    }
}

class TreeNode {
    public Leaf left;
    public Leaf right;
    public String annotation;
    public TreeNode(Leaf l, Leaf r) {
        left = l;
        right = r;
    }
}
Python
class Leaf:
    def __init__(self, value):
        self.value = value


class TreeNode:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        self.annotation = None
C#
using System;

public class Leaf
{
    public int Value { get; set; }

    public Leaf(int v)
    {
        Value = v;
    }
}

public class TreeNode
{
    public Leaf Left { get; set; }
    public Leaf Right { get; set; }
    public string Annotation { get; set; }

    public TreeNode(Leaf l, Leaf r)
    {
        Left = l;
        Right = r;
    }
}
Javascript
class Leaf {
    constructor(v) {
        this.value = v;
    }
}

class TreeNode {
    constructor(l, r) {
        this.left = l;
        this.right = r;
        this.annotation = '';
    }
}

// Example usage
const leaf1 = new Leaf(10);
const leaf2 = new Leaf(20);
const treeNode = new TreeNode(leaf1, leaf2);
treeNode.annotation = 'Example Annotation';

console.log(`TreeNode annotation: ${treeNode.annotation}`);
console.log(`Left leaf value: ${treeNode.left.value}`);
console.log(`Right leaf value: ${treeNode.right.value}`);

Step 2: Define the finger tree data structure, which consists of a finger (i.e., a pointer to the currently focused element) and the root node of the tree.

C++
#include <iostream>

template <typename T>
class FingerTree {
private:
    T root;
    T* finger;

public:
    FingerTree(T rootNode, T* fingerNode = nullptr) : root(rootNode), finger(fingerNode) {}

    // Other member functions can be added as needed

    // Getter for the root
    T getRoot() const {
        return root;
    }

    // Getter for the finger
    T* getFinger() const {
        return finger;
    }

    // Setter for the finger
    void setFinger(T* newFinger) {
        finger = newFinger;
    }
};

int main() {
    // Example usage
    int rootNode = 42;
    int fingerNode = 24;

    FingerTree<int> myFingerTree(rootNode, &fingerNode);

    std::cout << "Root: " << myFingerTree.getRoot() << std::endl;
    std::cout << "Finger: " << *(myFingerTree.getFinger()) << std::endl;

    // Update finger
    int newFingerNode = 100;
    myFingerTree.setFinger(&newFingerNode);

    std::cout << "Updated Finger: " << *(myFingerTree.getFinger()) << std::endl;

    return 0;
}
Java
public class FingerTree<T> {
    private T root;
    private T finger;

    public FingerTree(T rootNode, T fingerNode) {
        this.root = rootNode;
        this.finger = fingerNode;
    }

    // Other member functions can be added as needed

    // Getter for the root
    public T getRoot() {
        return root;
    }

    // Getter for the finger
    public T getFinger() {
        return finger;
    }

    // Setter for the finger
    public void setFinger(T newFinger) {
        finger = newFinger;
    }

    public static void main(String[] args) {
        // Example usage
        int rootNode = 42;
        int fingerNode = 24;

        FingerTree<Integer> myFingerTree = new FingerTree<>(rootNode, fingerNode);

        System.out.println("Root: " + myFingerTree.getRoot());
        System.out.println("Finger: " + myFingerTree.getFinger());

        // Update finger
        int newFingerNode = 100;
        myFingerTree.setFinger(newFingerNode);

        System.out.println("Updated Finger: " + myFingerTree.getFinger());
    }
}
Python
class FingerTree:
    def __init__(self, root, finger = None):
        self.root = root
        self.finger = finger
C#
using System;

public class FingerTree<T>
{
    private T root;
    private T finger;

    public FingerTree(T rootNode, T fingerNode = default(T))
    {
        root = rootNode;
        finger = fingerNode;
    }

    // Other member functions can be added as needed

    // Getter for the root
    public T GetRoot()
    {
        return root;
    }

    // Getter for the finger
    public T GetFinger()
    {
        return finger;
    }

    // Setter for the finger
    public void SetFinger(T newFinger)
    {
        finger = newFinger;
    }
}

class Program
{
    static void Main()
    {
        // Example usage
        int rootNode = 42;
        int fingerNode = 24;

        FingerTree<int> myFingerTree = new FingerTree<int>(rootNode, fingerNode);

        Console.WriteLine("Root: " + myFingerTree.GetRoot());
        Console.WriteLine("Finger: " + myFingerTree.GetFinger());

        // Update finger
        int newFingerNode = 100;
        myFingerTree.SetFinger(newFingerNode);

        Console.WriteLine("Updated Finger: " + myFingerTree.GetFinger());
    }
}
//this code is  contributed by monu .
Javascript
class FingerTree {
    constructor(root, finger = null) {
        this.root = root;
        this.finger = finger;
    }
}

Step 3: Define the annotation functions that summarize the information about the elements in a subtree. In this example, we will use the size of the subtree as the annotation.

C++
int size(Tree* tree) {
    if (dynamic_cast<Leaf*>(tree) != nullptr) {
        return 1;
    } else {
        return tree->annotation;
    }
}
Java
public class TreeUtils {
    public static int size(Tree tree) {
        if (tree instanceof Leaf) {
            return 1;
        } else {
            return tree.annotation;
        }
    }
}
Python
def size(tree):
    if isinstance(tree, Leaf):
        return 1
    else:
        return tree.annotation
Javascript
function size(tree) {
    if (tree instanceof Leaf) {
        return 1;
    } else {
        return tree.annotation;
    }
}

Step 4: Define the split and insert functions for the finger tree. The split function splits the tree at a given index and returns two new finger trees. The insert function inserts a new element at a given index in the tree.

C++
#include <iostream>
#include <utility>

// Define an interface for Tree
class Tree {
public:
    virtual ~Tree() {}
};

// Define a class for Leaf nodes
class Leaf : public Tree {
public:
    int value;

    Leaf(int value) : value(value) {}
};

// Define a class for TreeNodes
class TreeNode : public Tree {
public:
    Tree* left;
    Tree* right;

    TreeNode(Tree* left, Tree* right) : left(left), right(right) {}
};

// Define a class for FingerTree
class FingerTree {
public:
    Tree* root;
    int finger;

    FingerTree(Tree* root, int finger) : root(root), finger(finger) {}
};

// Define a class to represent a pair of objects
template<typename F, typename S>
class Pair {
public:
    F first;
    S second;

    Pair(F first, S second) : first(first), second(second) {}
};

// Function to get the size of a tree
int size(Tree* tree) {
    // Define logic to get the size of the tree
    // You need to implement this function based on your tree structure
    return 0; // Placeholder return value
}

// Function to split the tree
Pair<FingerTree*, FingerTree*> split(Tree* tree, int index) {
    if (dynamic_cast<Leaf*>(tree) != nullptr) {
        return {new FingerTree(tree, 0), new FingerTree(tree, 0)};
    } else if (index <= size(static_cast<TreeNode*>(tree)->left)) {
        auto leftRight = split(static_cast<TreeNode*>(tree)->left, index);
        return {leftRight.first, new FingerTree(new TreeNode(leftRight.second->root, static_cast<TreeNode*>(tree)->right), 0)};
    } else {
        auto leftRight = split(static_cast<TreeNode*>(tree)->right, index - size(static_cast<TreeNode*>(tree)->left));
        return {new FingerTree(new TreeNode(static_cast<TreeNode*>(tree)->left, leftRight.first->root), 0), leftRight.second};
    }
}

// Function to insert a value into the tree at a specific index
FingerTree* insert(Tree* tree, int index, int value) {
    auto leftRight = split(tree, index);
    return new FingerTree(new TreeNode(leftRight.first->root, new TreeNode(new Leaf(value), leftRight.second->root)), 0);
}

int main() {
    // Example usage
    Tree* tree = new TreeNode(new Leaf(1), new TreeNode(new Leaf(2), new Leaf(3)));
    FingerTree* result = insert(tree, 1, 4);
    std::cout << result->root << std::endl; // Note: This will print the memory address of the root
    return 0;
}
Java
// Define an interface for Tree
interface Tree {
}

// Define a class for Leaf nodes
class Leaf implements Tree {
    int value;

    public Leaf(int value) {
        this.value = value;
    }
}

// Define a class for TreeNodes
class TreeNode implements Tree {
    Tree left;
    Tree right;

    public TreeNode(Tree left, Tree right) {
        this.left = left;
        this.right = right;
    }
}

// Define a class for FingerTree
class FingerTree {
    Tree root;
    int finger;

    public FingerTree(Tree root, int finger) {
        this.root = root;
        this.finger = finger;
    }
}

// Define a class to represent a pair of objects
class Pair<F, S> {
    F first;
    S second;

    public Pair(F first, S second) {
        this.first = first;
        this.second = second;
    }
}

public class Main {

    // Function to get the size of a tree
    static int size(Tree tree) {
        // Define logic to get the size of the tree
        // You need to implement this function based on your tree structure
        return 0; // Placeholder return value
    }

    // Function to split the tree
    static Pair<FingerTree, FingerTree> split(Tree tree, int index) {
        if (tree instanceof Leaf) {
            return new Pair<>(new FingerTree(tree, 0), new FingerTree(tree, 0));
        } else if (index <= size(((TreeNode) tree).left)) {
            Pair<FingerTree, FingerTree> leftRight = split(((TreeNode) tree).left, index);
            return new Pair<>(leftRight.first, new FingerTree(new TreeNode(leftRight.second.root, ((TreeNode) tree).right), 0));
        } else {
            Pair<FingerTree, FingerTree> leftRight = split(((TreeNode) tree).right, index - size(((TreeNode) tree).left));
            return new Pair<>(new FingerTree(new TreeNode(((TreeNode) tree).left, leftRight.first.root), 0), leftRight.second);
        }
    }

    // Function to insert a value into the tree at a specific index
    static FingerTree insert(Tree tree, int index, int value) {
        Pair<FingerTree, FingerTree> leftRight = split(tree, index);
        return new FingerTree(new TreeNode(leftRight.first.root, new TreeNode(new Leaf(value), leftRight.second.root)), 0);
    }

    public static void main(String[] args) {
        // Example usage
        Tree tree = new TreeNode(new Leaf(1), new TreeNode(new Leaf(2), new Leaf(3)));
        FingerTree result = insert(tree, 1, 4);
        System.out.println(result.root);
    }
}
Python
def split(tree, index):
    if isinstance(tree, Leaf):
        return FingerTree(Leaf(tree.value)), FingerTree(Leaf(tree.value))
    elif index <= size(tree.left):
        left, right = split(tree.left, index)
        return left, FingerTree(TreeNode(right.root, tree.right), finger = tree.finger)
    else:
        left, right = split(tree.right, index - size(tree.left))
        return FingerTree(TreeNode(tree.left.root, left.root), finger = tree.finger), right


def insert(tree, index, value):
    left, right = split(tree.root, index)
    return FingerTree(TreeNode(left.root, TreeNode(Leaf(value), right.root)), finger = value)
Javascript
// Define a class for Leaf nodes
class Leaf {
  constructor(value) {
    this.value = value;
  }
}

// Define a class for TreeNodes
class TreeNode {
  constructor(left, right) {
    this.left = left;
    this.right = right;
  }
}

// Define a class for FingerTree
class FingerTree {
  constructor(root, finger = null) {
    this.root = root;
    this.finger = finger;
  }
}

// Function to get the size of a tree
function size(tree) {
  // Define logic to get the size of the tree
  // You need to implement this function based on your tree structure
}

// Function to split the tree
function split(tree, index) {
  if (tree instanceof Leaf) {
    return new FingerTree(new Leaf(tree.value)), new FingerTree(new Leaf(tree.value));
  } else if (index <= size(tree.left)) {
    let [left, right] = split(tree.left, index);
    return left, new FingerTree(new TreeNode(right.root, tree.right), tree.finger);
  } else {
    let [left, right] = split(tree.right, index - size(tree.left));
    return new FingerTree(new TreeNode(tree.left.root, left.root), tree.finger), right;
  }
}

// Function to insert a value into the tree at a specific index
function insert(tree, index, value) {
  let [left, right] = split(tree.root, index);
  return new FingerTree(new TreeNode(left.root, new TreeNode(new Leaf(value), right.root)), value);
}

Step 5: Define the search function for the finger tree. The search function searches for an element in the tree and returns its index if found, or None if not found.

C++
#include <iostream>
using namespace std;

// Define the TreeNode class representing nodes in the binary tree
class TreeNode {
public:
    int value;
    int annotation; // Annotation representing the sum of all values in the left subtree
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize TreeNode with value and annotation
    TreeNode(int value, int annotation) {
        this->value = value;
        this->annotation = annotation;
        this->left = nullptr;
        this->right = nullptr;
    }
};

// Define the search function for the binary tree
int* search(TreeNode* tree, int value) {
    // Check if the current node is a leaf
    if (tree->left == nullptr && tree->right == nullptr) {
        // Return 0 if the leaf value matches the target value, otherwise, return nullptr
        return tree->value == value ? new int(0) : nullptr;
    } else if (value <= tree->left->annotation) {
        // If the target value is less than or equal to the left subtree's annotation,
        // recursively search the left subtree
        int* index = search(tree->left, value);
        // Return the index if found, otherwise, return nullptr
        return index != nullptr ? index : nullptr;
    } else {
        // If the target value is greater than the left subtree's annotation,
        // adjust the target value and recursively search the right subtree
        int* index = search(tree->right, value - tree->left->annotation);
        // Return nullptr if not found in the right subtree, otherwise, add the left subtree's annotation
        // to the found index and return the result
        return index != nullptr ? new int(*index + tree->left->annotation) : nullptr;
    }
}

// Example usage
int main() {
    // Example tree construction
    TreeNode* leaf1 = new TreeNode(3, 3);
    TreeNode* leaf2 = new TreeNode(7, 7);
    TreeNode* leaf3 = new TreeNode(10, 10);
    TreeNode* internalNode = new TreeNode(8, 10);
    internalNode->left = leaf1;
    internalNode->right = leaf2;
    TreeNode* root = new TreeNode(5, 10);
    root->left = internalNode;
    root->right = leaf3;

    // Example search
    int valueToFind = 7;
    int* result = search(root, valueToFind);
    if (result != nullptr) {
        cout << "Index of value " << valueToFind << " is: " << *result << endl;
        delete result;
    } else {
        cout << "Value " << valueToFind << " not found in the tree." << endl;
    }

    // Don't forget to delete the nodes of the tree to avoid memory leaks
    delete leaf1;
    delete leaf2;
    delete leaf3;
    delete internalNode;
    delete root;

    return 0;
}
Java
// Define the search function for a binary tree
public class BinaryTreeSearch {
    // Define the TreeNode class representing nodes in the binary tree
    static class TreeNode {
        int value;
        int annotation; // Annotation representing the sum of all values in the left subtree

        TreeNode left;
        TreeNode right;

        // Constructor to initialize TreeNode with value and annotation
        TreeNode(int value, int annotation) {
            this.value = value;
            this.annotation = annotation;
            this.left = null;
            this.right = null;
        }
    }

    // Define the search function for the binary tree
    public static Integer search(TreeNode tree, int value) {
        // Check if the current node is a leaf
        if (tree.left == null && tree.right == null) {
            // Return 0 if the leaf value matches the target value, otherwise, return null
            return tree.value == value ? 0 : null;
        } else if (value <= tree.left.annotation) {
            // If the target value is less than or equal to the left subtree's annotation,
            // recursively search the left subtree
            Integer index = search(tree.left, value);
            // Return the index if found, otherwise, return null
            return index != null ? index : null;
        } else {
            // If the target value is greater than the left subtree's annotation,
            // adjust the target value and recursively search the right subtree
            Integer index = search(tree.right, value - tree.left.annotation);
            // Return null if not found in the right subtree, otherwise, add the left subtree's annotation
            // to the found index and return the result
            return index != null ? index + tree.left.annotation : null;
        }
    }

    // Example usage
    public static void main(String[] args) {
        // Example tree construction
        TreeNode leaf1 = new TreeNode(3, 3);
        TreeNode leaf2 = new TreeNode(7, 7);
        TreeNode leaf3 = new TreeNode(10, 10);
        TreeNode internalNode = new TreeNode(8, 10);
        internalNode.left = leaf1;
        internalNode.right = leaf2;
        TreeNode root = new TreeNode(5, 10);
        root.left = internalNode;
        root.right = leaf3;

        // Example search
        int valueToFind = 7;
        Integer result = search(root, valueToFind);
        System.out.println("Index of value " + valueToFind + " is: " + result);
    }
}
Python
def search(tree, value):
    if isinstance(tree, Leaf):
        return 0 if tree.value == value else None
    elif value <= tree.left.annotation:
        index = search(tree.left, value)
        return index if index is None else index
    else:
        index = search(tree.right, value - tree.left.annotation)
        return None if index is None else index + tree.left.annotation
Javascript
// Define the search function for a binary tree
function search(tree, value) {
    // Check if the current node is a leaf
    if (tree instanceof Leaf) {
        // Return 0 if the leaf value matches the target value, otherwise, return null
        return tree.value === value ? 0 : null;
    } else if (value <= tree.left.annotation) {
        // If the target value is less than or equal to the left subtree's annotation,
        // recursively search the left subtree
        let index = search(tree.left, value);
        // Return the index if found, otherwise, return null
        return index !== null ? index : null;
    } else {
        // If the target value is greater than the left subtree's annotation,
        // adjust the target value and recursively search the right subtree
        let index = search(tree.right, value - tree.left.annotation);
        // Return null if not found in the right subtree, otherwise, add the left subtree's annotation
        // to the found index and return the result
        return index !== null ? index + tree.left.annotation : null;
    }
}

Here is an example usage of the finger tree and the search function:

C++
#include <iostream>
#include <memory>

// Define a Leaf node for the Finger Tree
class Leaf {
public:
    int value;

    Leaf(int value)
        : value(value)
    {
    }
};

// Define a TreeNode for the Finger Tree
class TreeNode {
public:
    std::shared_ptr<void>
        left; // Can be either Leaf or TreeNode
    std::shared_ptr<void>
        right; // Can be either Leaf or TreeNode

    TreeNode(std::shared_ptr<void> left,
             std::shared_ptr<void> right)
        : left(left)
        , right(right)
    {
    }
};

// Define the Finger Tree structure
class FingerTree {
public:
    std::shared_ptr<TreeNode> root;

    FingerTree(std::shared_ptr<TreeNode> root)
        : root(root)
    {
    }
};

// Function to search for a value in the Finger Tree
class FingerTreeSearch {
public:
    static int search(FingerTree tree, int value)
    {
        // Your search logic here
        // Return the index if found, or -1 if not found
        return -1;
    }
};

// Function to insert a value at a specific index in the
// Finger Tree
class FingerTreeInsert {
public:
    static FingerTree insert(FingerTree tree, int index,
                             int value)
    {
        // Your insertion logic here
        // Return the modified Finger Tree
        return tree;
    }
};

int main()
{
    FingerTree t(std::make_shared<TreeNode>(
        std::make_shared<TreeNode>(
            std::make_shared<Leaf>(1),
            std::make_shared<Leaf>(2)),
        std::make_shared<TreeNode>(
            std::make_shared<Leaf>(3),
            std::make_shared<Leaf>(4))));
    std::cout << FingerTreeSearch::search(t, 1)
              << std::endl;
    std::cout << FingerTreeSearch::search(t, 2)
              << std::endl;
    std::cout << FingerTreeSearch::search(t, 3)
              << std::endl;
    std::cout << FingerTreeSearch::search(t, 4)
              << std::endl;
    std::cout << FingerTreeSearch::search(t, 5)
              << std::endl;

    t = FingerTreeInsert::insert(t, 2, 5);
    std::cout << FingerTreeSearch::search(t, 5)
              << std::endl;

    return 0;
}
Java
// Define a Leaf node for the Finger Tree
class Leaf {
    int value;

    public Leaf(int value) { this.value = value; }
}

// Define a TreeNode for the Finger Tree
class TreeNode {
    Object left; // Can be either Leaf or TreeNode
    Object right; // Can be either Leaf or TreeNode

    public TreeNode(Object left, Object right)
    {
        this.left = left;
        this.right = right;
    }
}

// Define the Finger Tree structure
class FingerTree {
    TreeNode root;

    public FingerTree(TreeNode root) { this.root = root; }
}

// Function to search for a value in the Finger Tree
class FingerTreeSearch {
    public static Integer search(FingerTree tree, int value)
    {
        // Your search logic here
        // Return the index if found, or null if not found
        return null;
    }
}

// Function to insert a value at a specific index in the
// Finger Tree
class FingerTreeInsert {
    public static FingerTree insert(FingerTree tree,
                                    int index, int value)
    {
        // Your insertion logic here
        // Return the modified Finger Tree
        return null;
    }
}

// Example usage
public class Main {
    public static void main(String[] args)
    {
        FingerTree t = new FingerTree(new TreeNode(
            new TreeNode(new Leaf(1), new Leaf(2)),
            new TreeNode(new Leaf(3), new Leaf(4))));
        System.out.println(
            FingerTreeSearch.search(t, 1)); // 0
        System.out.println(
            FingerTreeSearch.search(t, 2)); // 1
        System.out.println(
            FingerTreeSearch.search(t, 3)); // 2
        System.out.println(
            FingerTreeSearch.search(t, 4)); // 3
        System.out.println(
            FingerTreeSearch.search(t, 5)); // null

        t = FingerTreeInsert.insert(t, 2, 5);
        System.out.println(
            FingerTreeSearch.search(t, 5)); // 2
    }
}
Python
t = FingerTree(TreeNode(TreeNode(Leaf(1), Leaf(2)),
                        TreeNode(Leaf(3), Leaf(4))))
print(search(t, 1))  # 0
print(search(t, 2))  # 1
print(search(t, 3))  # 2
print(search(t, 4))  # 3
print(search(t, 5))  # None

t = insert(t, 2, 5)
print(search(t, 5))  # 2
C#
using System;

// Define a Leaf node for the Finger Tree
public class Leaf {
    public int Value { get; }

    public Leaf(int value) { Value = value; }
}

// Define a TreeNode for the Finger Tree
public class TreeNode {
    public object Left { get; }
    public object Right { get; }

    public TreeNode(object left, object right)
    {
        Left = left;
        Right = right;
    }
}

// Define the Finger Tree structure
public class FingerTree {
    public TreeNode Root { get; }

    public FingerTree(TreeNode root) { Root = root; }
}

// Class containing search and insert functions for
// FingerTree
public class FingerTreeOperations {
    // Function to search for a value in the Finger Tree
    public static int ? Search(FingerTree tree, int value)
    {
        // Your search logic here
        // Return the index if found, or null if not found
        return null;
    }

    // Function to insert a value at a specific index in the
    // Finger Tree
    public static FingerTree Insert(FingerTree tree,
                                    int index, int value)
    {
        // Your insertion logic here
        // Return the modified Finger Tree
        return null;
    }
}

// Example usage
class Program {
    static void Main(string[] args)
    {
        FingerTree t = new FingerTree(new TreeNode(
            new TreeNode(new Leaf(1), new Leaf(2)),
            new TreeNode(new Leaf(3), new Leaf(4))));

        Console.WriteLine(
            FingerTreeOperations.Search(t, 1)); // 0
        Console.WriteLine(
            FingerTreeOperations.Search(t, 2)); // 1
        Console.WriteLine(
            FingerTreeOperations.Search(t, 3)); // 2
        Console.WriteLine(
            FingerTreeOperations.Search(t, 4)); // 3
        Console.WriteLine(
            FingerTreeOperations.Search(t, 5)); // null

        t = FingerTreeOperations.Insert(t, 2, 5);
        Console.WriteLine(
            FingerTreeOperations.Search(t, 5)); // 2
    }
}
Javascript
// Define a Leaf node for the Finger Tree
class Leaf {
    constructor(value) {
        this.value = value;
    }
}

// Define a TreeNode for the Finger Tree
class TreeNode {
    constructor(left, right) {
        this.left = left;
        this.right = right;
    }
}

// Define the Finger Tree structure
class FingerTree {
    constructor(root) {
        this.root = root;
    }
}

// Function to search for a value in the Finger Tree
function search(tree, value) {
    // Your search logic here
    // Return the index if found, or null if not found
}

// Function to insert a value at a specific index in the Finger Tree
function insert(tree, index, value) {
    // Your insertion logic here
    // Return the modified Finger Tree
}

// Example usage
let t = new FingerTree(new TreeNode(new TreeNode(new Leaf(1), new Leaf(2)), new TreeNode(new Leaf(3), new Leaf(4))));
console.log(search(t, 1));  // 0
console.log(search(t, 2));  // 1
console.log(search(t, 3));  // 2
console.log(search(t, 4));  // 3
console.log(search(t, 5));  // null

t = insert(t, 2, 5);
console.log(search(t, 5));  // 2

Note that this is a very basic implementation of a finger tree that only supports the search and insert operations. A complete implementation of a finger tree data structure would need to include additional operations such as delete, concatenation, split, etc.

Below is the complete code to implement the finger search tree:

C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;


class Leaf {
public:
    int value;
    Leaf(int val) : value(val) {}
};

class Node {
public:
    Node* left;
    Node* right;
    int size;
    Node(Node* l, Node* r, int s) : left(l), right(r), size(s) {}
};

class FingerTree {
public:
    Node* root;
    int finger;

    FingerTree(Node* r = nullptr, int f = -1) : root(r), finger(f) {}
};

int search(FingerTree* tree, int value) {
    if (tree == nullptr) {
        return -1;
    }
    if (dynamic_cast<Leaf*>(tree->root) != nullptr) {
        return (tree->root->value == value) ? 0 : -1;
    } else if (value <= tree->root->left->size) {
        int index = search(new FingerTree(tree->root->left), value);
        return (index != -1) ? index : -1;
    } else {
        int index = search(new FingerTree(tree->root->right), value - tree->root->left->size);
        return (index != -1) ? (index + tree->root->left->size) : -1;
    }
}

FingerTree* insert(FingerTree* tree, int index, int value) {
    if (tree == nullptr) {
        return new FingerTree(new Leaf(value), value);
    }
    if (tree->root == nullptr) {
        return new FingerTree(new Leaf(value), value);
    }
    if (dynamic_cast<Leaf*>(tree->root) != nullptr) {
        if (index == 0) {
            return new FingerTree(new Node(new Leaf(value), tree->root, 2), value);
        } else if (index == 1) {
            return new FingerTree(new Node(tree->root, new Leaf(value), 2), value);
        } else {
            throw std::out_of_range("Index out of bounds");
        }
    } else if (index <= tree->root->left->size) {
        FingerTree* left = insert(new FingerTree(tree->root->left), index, value);
        int size = tree->root->size + 1;
        if (size % 2 == 0) {
            return new FingerTree(new Node(left->root, tree->root->right, size), value);
        } else {
            return new FingerTree(new Node(left->root, tree->root, size), value);
        }
    } else {
        FingerTree* right = insert(new FingerTree(tree->root->right), index - tree->root->left->size, value);
        int size = tree->root->size + 1;
        if (size % 2 == 0) {
            return new FingerTree(new Node(tree->root->left, right->root, size), value);
        } else {
            return new FingerTree(new Node(tree->root, right->root, size), value);
        }
    }
}
Java
public interface FingerTree<T> {
    FingerTree<T> insert(int index, T value);
    int search(T value);
}

public class Leaf<T> implements FingerTree<T> {
    private final T value;

    public Leaf(T value) { this.value = value; }

    public FingerTree<T> insert(int index, T value)
    {
        if (index == 0) {
            return new Node<>(new Leaf<>(value), this);
        }
        else if (index == 1) {
            return new Node<>(this, new Leaf<>(value));
        }
        else {
            throw new IndexOutOfBoundsException();
        }
    }

    public int search(T value)
    {
        return this.value.equals(value) ? 0 : -1;
    }
}

public class Node<T> implements FingerTree<T> {
    private final FingerTree<T> left;
    private final FingerTree<T> right;
    private final int size;

    public Node(FingerTree<T> left, FingerTree<T> right)
    {
        this.left = left;
        this.right = right;
        this.size = left.size() + right.size();
    }

    public FingerTree<T> insert(int index, T value)
    {
        if (index <= left.size()) {
            FingerTree<T> newLeft
                = left.insert(index, value);
            if
Python
class FingerTree:
    def __init__(self, root = None, finger = None):
        self.root = root
        self.finger = finger


class Leaf:
    def __init__(self, value):
        self.value = value


class Node:
    def __init__(self, left, right, size):
        self.left = left
        self.right = right
        self.size = size


def search(tree, value):
    if tree is None:
        return None
    if isinstance(tree.root, Leaf):
        return 0 if tree.root.value == value else None
    elif value <= tree.root.left.size:
        index = search(tree.root.left, value)
        return index if index is not None else None
    else:
        index = search(tree.root.right, value - tree.root.left.size)
        return None if index is None else index + tree.root.left.size


def insert(tree, index, value):
    if tree is None:
        return FingerTree(Leaf(value), finger = value)
    if tree.root is None:
        return FingerTree(Leaf(value), finger = value)
    if isinstance(tree.root, Leaf):
        if index == 0:
            return FingerTree(Node(Leaf(value), tree.root, 2), finger = value)
        elif index == 1:
            return FingerTree(Node(tree.root, Leaf(value), 2), finger = value)
        else:
            raise IndexError("Index out of bounds")
    elif index <= tree.root.left.size:
        left = insert(tree.root.left, index, value)
        size = tree.root.size + 1
        if size % 2 == 0:
            return FingerTree(Node(left.root, tree.root.right, size), finger = value)
        else:
            return FingerTree(Node(left.root, tree.root, size), finger = value)
    else:
        right = insert(tree.root.right, index - tree.root.left.size, value)
        size = tree.root.size + 1
        if size % 2 == 0:
            return FingerTree(Node(tree.root.left, right.root, size), finger = value)
        else:
            return FingerTree(Node(tree.root, right.root, size), finger = value)
C#
using System;

class Leaf
{
    public int value;

    public Leaf(int val)
    {
        value = val;
    }
}

class Node
{
    public Node left;
    public Node right;
    public int size;

    public Node(Node l, Node r, int s)
    {
        left = l;
        right = r;
        size = s;
    }
}

class FingerTree
{
    public Node root;
    public int finger;

    public FingerTree(Node r = null, int f = -1)
    {
        root = r;
        finger = f;
    }
}

class Program
{
    static int Search(FingerTree tree, int value)
    {
        if (tree == null)
        {
            return -1;
        }
        if (tree.root is Leaf leaf && leaf.value == value)
        {
            return 0;
        }
        else if (value <= tree.root.left.size)
        {
            int index = Search(new FingerTree(tree.root.left), value);
            return (index != -1) ? index : -1;
        }
        else
        {
            int index = Search(new FingerTree(tree.root.right), value - tree.root.left.size);
            return (index != -1) ? (index + tree.root.left.size) : -1;
        }
    }

    static FingerTree Insert(FingerTree tree, int index, int value)
    {
        if (tree == null)
        {
            return new FingerTree(new Leaf(value), value);
        }
        if (tree.root == null)
        {
            return new FingerTree(new Leaf(value), value);
        }
        if (tree.root is Leaf)
        {
            if (index == 0)
            {
                return new FingerTree(new Node(new Leaf(value), tree.root, 2), value);
            }
            else if (index == 1)
            {
                return new FingerTree(new Node(tree.root, new Leaf(value), 2), value);
            }
            else
            {
                throw new ArgumentOutOfRangeException("Index out of bounds");
            }
        }
        else if (index <= tree.root.left.size)
        {
            FingerTree left = Insert(new FingerTree(tree.root.left), index, value);
            int size = tree.root.size + 1;
            if (size % 2 == 0)
            {
                return new FingerTree(new Node(left.root, tree.root.right, size), value);
            }
            else
            {
                return new FingerTree(new Node(left.root, tree.root, size), value);
            }
        }
        else
        {
            FingerTree right = Insert(new FingerTree(tree.root.right), index - tree.root.left.size, value);
            int size = tree.root.size + 1;
            if (size % 2 == 0)
            {
                return new FingerTree(new Node(tree.root.left, right.root, size), value);
            }
            else
            {
                return new FingerTree(new Node(tree.root, right.root, size), value);
            }
        }
    }

    static void Main()
    {
        // Your main logic here
    }
}
Javascript
class Leaf {
    constructor(val) {
        this.value = val;
    }
}

class Node {
    constructor(l, r, s) {
        this.left = l;
        this.right = r;
        this.size = s;
    }
}

class FingerTree {
    constructor(r = null, f = -1) {
        this.root = r;
        this.finger = f;
    }
}

function search(tree, value) {
    if (tree === null) {
        return -1;
    }
    if (tree.root instanceof Leaf) {
        return (tree.root.value === value) ? 0 : -1;
    } else if (value <= tree.root.left.size) {
        const index = search(new FingerTree(tree.root.left), value);
        return (index !== -1) ? index : -1;
    } else {
        const index = search(new FingerTree(tree.root.right), value - tree.root.left.size);
        return (index !== -1) ? (index + tree.root.left.size) : -1;
    }
}

function insert(tree, index, value) {
    if (tree === null) {
        return new FingerTree(new Leaf(value), value);
    }
    if (tree.root === null) {
        return new FingerTree(new Leaf(value), value);
    }
    if (tree.root instanceof Leaf) {
        if (index === 0) {
            return new FingerTree(new Node(new Leaf(value), tree.root, 2), value);
        } else if (index === 1) {
            return new FingerTree(new Node(tree.root, new Leaf(value), 2), value);
        } else {
            throw new Error("Index out of bounds");
        }
    } else if (index <= tree.root.left.size) {
        const left = insert(new FingerTree(tree.root.left), index, value);
        const size = tree.root.size + 1;
        if (size % 2 === 0) {
            return new FingerTree(new Node(left.root, tree.root.right, size), value);
        } else {
            return new FingerTree(new Node(left.root, tree.root, size), value);
        }
    } else {
        const right = insert(new FingerTree(tree.root.right), index - tree.root.left.size, value);
        const size = tree.root.size + 1;
        if (size % 2 === 0) {
            return new FingerTree(new Node(tree.root.left, right.root, size), value);
        } else {
            return new FingerTree(new Node(tree.root, right.root, size), value);
        }
    }
}

Advantages of Finger Search Tree:

  • Efficient searching: Finger trees support fast search operations with a worst-case time complexity of O(log n), making them suitable for applications that require frequent searching.
  • Flexible: Finger trees can be used to implement a wide range of data structures, including priority queues, ordered sets, and sequences.
  • Persistent: Finger trees support efficient persistent data structures, which allow multiple versions of a data structure to be maintained without affecting the original structure.
  • Easy to implement: Finger trees have a simple and elegant recursive structure that makes them easy to implement and understand.

Disadvantages of Finger Search Tree:

  • Overhead: Finger trees have a higher memory overhead than other search tree data structures because they require additional information to be stored at each node, including the size of the subtree.
  • Complex operations: Some operations, such as concatenation and splitting, can be more complex and less efficient in finger trees than in other search tree data structures.
  • Lack of popularity: Finger trees are not as widely used as other search tree data structures, so there may be less community support and fewer third-party libraries available.

Conclusion:

Overall, finger search trees can be a good choice for applications that require efficient searching and flexible data structures, but may not be the best choice for all situations. It is important to consider the specific requirements of your application and evaluate the performance and tradeoffs of different data structures before making a decision. Therefore, finger search trees are a powerful data structure that can provide fast searching, insertion, and deletion operations. While they can be complex to implement, they are well worth the effort for applications where searching is a critical operation.



Similar Reads

Binary Search Tree vs Ternary Search Tree
For effective searching, insertion, and deletion of items, two types of search trees are used: the binary search tree (BST) and the ternary search tree (TST). Although the two trees share a similar structure, they differ in some significant ways. FeatureBinary Search Tree (BST)Ternary Search Tree (TST)NodeHere, each node has at most two children. H
3 min read
Static Data Structure vs Dynamic Data Structure
Data structure is a way of storing and organizing data efficiently such that the required operations on them can be performed be efficient with respect to time as well as memory. Simply, Data Structure are used to reduce complexity (mostly the time complexity) of the code. Data structures can be two types : 1. Static Data Structure 2. Dynamic Data
4 min read
Introduction to Splay tree data structure
Splay tree is a self-adjusting binary search tree data structure, which means that the tree structure is adjusted dynamically based on the accessed or inserted elements. In other words, the tree automatically reorganizes itself so that frequently accessed or inserted elements become closer to the root node. The splay tree was first introduced by Da
15+ min read
Introduction to Tree Data Structure
Tree data structure is a specialized data structure to store data in hierarchical manner. It is used to organize and store data in the computer to be used more effectively. It consists of a central node, structural nodes, and sub-nodes, which are connected via edges. We can also say that tree data structure has roots, branches, and leaves connected
15+ min read
Complexity of different operations in Binary tree, Binary Search Tree and AVL tree
In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t
4 min read
Search N elements in an unbalanced Binary Search Tree in O(N * logM) time
Given an Unbalanced binary search tree (BST) of M nodes. The task is to find the N elements in the Unbalanced Binary Search Tree in O(N*logM) time. Examples: Input: search[] = {6, 2, 7, 5, 4, 1, 3}. Consider the below tree Output:FoundNot FoundFoundFoundFoundFoundNot Found Naive Approach: For each element, we will try to search for that element in
8 min read
Design a data structure that supports insert, delete, search and getRandom in constant time
Design a data structure that supports the following operations in O(1) time. insert(x): Inserts an item x to the data structure if not already present.remove(x): Removes item x from the data structure if present. search(x): Searches an item x in the data structure.getRandom(): Returns a random element from the current set of elements We can use has
5 min read
Trie Data Structure | Insert and Search
The Trie data structure is a tree-like data structure used for storing a dynamic set of strings. It is commonly used for efficient retrieval and storage of keys in a large dataset. The structure supports operations such as insertion, search, and deletion of keys, making it a valuable tool in fields like computer science and information retrieval. I
14 min read
Add and Search Word - Data Structure Design
Design a data structure GFGDictionary that enables to support the feature of adding new words and searching for words. The GFGDictionary class should have the following implementation: GFGDictionary(): constructor to initialize the objectvoid insertWord(word): function to insert word into the data structure.bool findWord(word): function to return t
4 min read
Introduction to the Probabilistic Data Structure
Introduction: Probabilistic Data Structures are data structures that provide approximate answers to queries about a large dataset, rather than exact answers. These data structures are designed to handle large amounts of data in real-time, by making trade-offs between accuracy and time and space efficiency. Some common examples of Probabilistic Data
5 min read