Introduction to Finger search tree Data Structure
Last Updated :
14 May, 2024
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
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)
{
}
};
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;
}
}
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
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;
}
}
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;
}
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());
}
}
class FingerTree:
def __init__(self, root, finger = None):
self.root = root
self.finger = finger
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 .
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;
}
}
public class TreeUtils {
public static int size(Tree tree) {
if (tree instanceof Leaf) {
return 1;
} else {
return tree.annotation;
}
}
}
def size(tree):
if isinstance(tree, Leaf):
return 1
else:
return tree.annotation
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;
}
// 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);
}
}
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)
// 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;
}
// 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);
}
}
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
// 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;
}
// 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
}
}
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
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
}
}
// 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);
}
}
}
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
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)
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
}
}
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.
Please Login to comment...