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) { }}; |
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 = valueclass 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 usageconst 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.
Python
class FingerTree: def __init__(self, root, finger = None): self.root = root self.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.
Python
def size(tree): if isinstance(tree, 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.
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), rightdef insert(tree, index, value): left, right = split(tree.root, index) return FingerTree(TreeNode(left.root, TreeNode(Leaf(value), right.root)), finger = 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.
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 |
Here is an example usage of the finger tree and the search function:
Python
t = FingerTree(TreeNode(TreeNode(Leaf(1), Leaf(2)), TreeNode(Leaf(3), Leaf(4))))print(search(t, 1)) # 0print(search(t, 2)) # 1print(search(t, 3)) # 2print(search(t, 4)) # 3print(search(t, 5)) # Nonet = insert(t, 2, 5)print(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 = fingerclass Leaf: def __init__(self, value): self.value = valueclass Node: def __init__(self, left, right, size): self.left = left self.right = right self.size = sizedef 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.sizedef 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 }} |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
