Search Tree: Fundamentals and Applications
By Fouad Sabry
()
About this ebook
What Is Search Tree
A search tree is a tree data structure that is used in the field of computer science for the purpose of locating specific keys from within a collection. The key for each node in a tree needs to be greater than any keys in subtrees on the left, and it needs to be less than any keys in subtrees on the right for the tree to be able to function as a search tree.
How You Will Benefit
(I) Insights, and validations about the following topics:
Chapter 1: Search Tree
Chapter 2: Binary Search Tree
Chapter 3: Self-Balancing Binary Search Tree
Chapter 4: Red-Black Tree
Chapter 5: B-Tree
Chapter 6: Splay Tree
Chapter 7: Tries
Chapter 8: AVL Tree
Chapter 9: 2-3 Tree
Chapter 10: Treap
(II) Answering the public top questions about search tree.
(III) Real world examples for the usage of search tree in many fields.
(IV) 17 appendices to explain, briefly, 266 emerging technologies in each industry to have 360-degree full understanding of search tree' technologies.
Who This Book Is For
Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of search tree.
Read more from Fouad Sabry
Emerging Technologies in Transport
Related to Search Tree
Titles in the series (100)
Long Short Term Memory: Fundamentals and Applications for Sequence Prediction Rating: 0 out of 5 stars0 ratingsEmbodied Cognition: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsAttractor Networks: Fundamentals and Applications in Computational Neuroscience Rating: 0 out of 5 stars0 ratingsConvolutional Neural Networks: Fundamentals and Applications for Analyzing Visual Imagery Rating: 0 out of 5 stars0 ratingsHybrid Neural Networks: Fundamentals and Applications for Interacting Biological Neural Networks with Artificial Neuronal Models Rating: 0 out of 5 stars0 ratingsArtificial Neural Networks: Fundamentals and Applications for Decoding the Mysteries of Neural Computation Rating: 0 out of 5 stars0 ratingsPerceptrons: Fundamentals and Applications for The Neural Building Block Rating: 0 out of 5 stars0 ratingsRadial Basis Networks: Fundamentals and Applications for The Activation Functions of Artificial Neural Networks Rating: 0 out of 5 stars0 ratingsBackpropagation: Fundamentals and Applications for Preparing Data for Training in Deep Learning Rating: 0 out of 5 stars0 ratingsRestricted Boltzmann Machine: Fundamentals and Applications for Unlocking the Hidden Layers of Artificial Intelligence Rating: 0 out of 5 stars0 ratingsRecurrent Neural Networks: Fundamentals and Applications from Simple to Gated Architectures Rating: 0 out of 5 stars0 ratingsAlternating Decision Tree: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsFeedforward Neural Networks: Fundamentals and Applications for The Architecture of Thinking Machines and Neural Webs Rating: 0 out of 5 stars0 ratingsControl System: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsSubsumption Architecture: Fundamentals and Applications for Behavior Based Robotics and Reactive Control Rating: 0 out of 5 stars0 ratingsStatistical Classification: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsNouvelle Artificial Intelligence: Fundamentals and Applications for Producing Robots With Intelligence Levels Similar to Insects Rating: 0 out of 5 stars0 ratingsMultilayer Perceptron: Fundamentals and Applications for Decoding Neural Networks Rating: 0 out of 5 stars0 ratingsSupport Vector Machine: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsCognitive Architecture: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsHebbian Learning: Fundamentals and Applications for Uniting Memory and Learning Rating: 0 out of 5 stars0 ratingsHopfield Networks: Fundamentals and Applications of The Neural Network That Stores Memories Rating: 0 out of 5 stars0 ratingsNeuroevolution: Fundamentals and Applications for Surpassing Human Intelligence with Neuroevolution Rating: 0 out of 5 stars0 ratingsNaive Bayes Classifier: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsEmbodied Cognitive Science: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsNetworked Control System: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsKernel Methods: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsBio Inspired Computing: Fundamentals and Applications for Biological Inspiration in the Digital World Rating: 0 out of 5 stars0 ratingsK Nearest Neighbor Algorithm: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsSituated Artificial Intelligence: Fundamentals and Applications for Integrating Intelligence With Action Rating: 0 out of 5 stars0 ratings
Related ebooks
Quadtree: Exploring Hierarchical Data Structures for Image Analysis Rating: 0 out of 5 stars0 ratingsBreadth First Search: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsData Structures & Algorithms Interview Questions You'll Most Likely Be Asked Rating: 1 out of 5 stars1/5Beginning Data Structures Using C Rating: 4 out of 5 stars4/5Depth First Search: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsDecision Tree Pruning: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsData Structures for Beginners: Mastering the Building Blocks of Efficient Data Management Rating: 0 out of 5 stars0 ratingsADVANCED DATA STRUCTURES FOR ALGORITHMS: Mastering Complex Data Structures for Algorithmic Problem-Solving (2024) Rating: 0 out of 5 stars0 ratingsVisualizing Data Structures Rating: 0 out of 5 stars0 ratingsMagic Data: Part 2 - Harnessing the Power of Algorithms and Structures Rating: 0 out of 5 stars0 ratingsMagic Data: Part 1 - Harnessing the Power of Algorithms and Structures Rating: 0 out of 5 stars0 ratingsAutomatic Image Annotation: Enhancing Visual Understanding through Automated Tagging Rating: 0 out of 5 stars0 ratingsData Structures I Essentials Rating: 0 out of 5 stars0 ratingsAlternating Decision Tree: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsAutomatic Image Annotation: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsMastering Data Structures and Algorithms in C and C++ Rating: 0 out of 5 stars0 ratingsSemantic Network: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsEssential Algorithms: A Practical Approach to Computer Algorithms Rating: 5 out of 5 stars5/5Scale Invariant Feature Transform: Unveiling the Power of Scale Invariant Feature Transform in Computer Vision Rating: 0 out of 5 stars0 ratingsComputer Data Rating: 0 out of 5 stars0 ratingsAlgorithms and Data Structures for Massive Datasets Rating: 0 out of 5 stars0 ratingsAdvanced Algorithms and Data Structures Rating: 0 out of 5 stars0 ratingsSpatiotemporal Data Analysis Rating: 3 out of 5 stars3/5Perceptrons: Fundamentals and Applications for The Neural Building Block Rating: 0 out of 5 stars0 ratingsMicrosoft Access: Database Creation and Management through Microsoft Access Rating: 0 out of 5 stars0 ratingsRelationship Extraction: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsVisual Word: Unlocking the Power of Image Understanding Rating: 0 out of 5 stars0 ratingsConcept Mining: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsBeam Search: Fundamentals and Applications Rating: 0 out of 5 stars0 ratingsData Mining for the Social Sciences: An Introduction Rating: 0 out of 5 stars0 ratings
Intelligence (AI) & Semantics For You
Artificial Intelligence: A Guide for Thinking Humans Rating: 4 out of 5 stars4/5Midjourney Mastery - The Ultimate Handbook of Prompts Rating: 5 out of 5 stars5/5ChatGPT For Fiction Writing: AI for Authors Rating: 5 out of 5 stars5/5Summary of Super-Intelligence From Nick Bostrom Rating: 5 out of 5 stars5/52084: Artificial Intelligence and the Future of Humanity Rating: 4 out of 5 stars4/5Mastering ChatGPT: 21 Prompts Templates for Effortless Writing Rating: 5 out of 5 stars5/5Chat-GPT Income Ideas: Pioneering Monetization Concepts Utilizing Conversational AI for Profitable Ventures Rating: 3 out of 5 stars3/5Creating Online Courses with ChatGPT | A Step-by-Step Guide with Prompt Templates Rating: 4 out of 5 stars4/5Enterprise AI For Dummies Rating: 3 out of 5 stars3/5101 Midjourney Prompt Secrets Rating: 3 out of 5 stars3/5ChatGPT For Dummies Rating: 4 out of 5 stars4/5Killer ChatGPT Prompts: Harness the Power of AI for Success and Profit Rating: 2 out of 5 stars2/5Dark Aeon: Transhumanism and the War Against Humanity Rating: 5 out of 5 stars5/5The Secrets of ChatGPT Prompt Engineering for Non-Developers Rating: 5 out of 5 stars5/5AI for Educators: AI for Educators Rating: 5 out of 5 stars5/5Artificial Intelligence For Dummies Rating: 3 out of 5 stars3/5The Algorithm of the Universe (A New Perspective to Cognitive AI) Rating: 5 out of 5 stars5/5ChatGPT Ultimate User Guide - How to Make Money Online Faster and More Precise Using AI Technology Rating: 1 out of 5 stars1/5Dancing with Qubits: How quantum computing works and how it can change the world Rating: 5 out of 5 stars5/5ChatGPT: The Future of Intelligent Conversation Rating: 4 out of 5 stars4/5
Reviews for Search Tree
0 ratings0 reviews
Book preview
Search Tree - Fouad Sabry
Chapter 1: Search tree
A search tree is a kind of tree data structure that is used in the field of computer science for the purpose of identifying certain keys included within a collection. In order for a tree to serve its purpose as a search tree, the key for each node has to be higher than any of the keys in the subtrees on the left, but lower than any of the keys in the subtrees on the right.
The benefit of using search trees is that they reduce the amount of time spent searching, provided that the tree is adequately balanced, which means that the leaves at either end have depths that are equivalent to one another. There are many different search-tree data structures, some of which additionally allow for the effective insertion and deletion of members; these operations, which then have to preserve tree balance,.
The implementation of an associative array often makes use of search trees. The key from the key–value pair is used by the search tree method to select a location, and after it has found the site, the application saves the full key–value pair at that specific position.
A Binary Search Tree is a data structure that is built on nodes, and each node in the tree holds a key in addition to two subtrees called the left and the right. For each and every node, the key for the left subtree must be less than the key for the node, and the key for the right subtree must be larger than the key for the node. All of these subtrees have to meet the criteria for binary search trees.
The worst-case time complexity for searching a binary search tree is the height of the tree, which may be as low as O(log n) for a tree with n elements. This is because the height of the tree is proportional to the number of elements in the tree.
Binary search trees may be generalized into B-trees, which differ from binary search trees in that each node in a B-tree can contain any number of subtrees. B-trees have the potential to waste some space since, despite the fact that child-nodes have a pre-defined range, this range is not guaranteed to be filled with data in every instance. The benefit of this is that B-trees do not need rebalancing nearly as often as other types of self-balancing trees do.
B-trees are advantageous for usage in systems that read enormous blocks of data because of the flexible range of their node lengths; in addition, B-trees are often used in database systems.
The complexity of searching a B-tree in terms of time is O. (log n).
A search tree is referred to be a (a,b)-tree when all of its leaves have the same level of depth. Each node in the tree has a minimum of a children and a maximum of b children, with the root having a minimum of 2 children and a maximum of b children.
The values of a and b may be determined using the following equation::
2\leq a\leq {\frac {(b+1)}{2}}O is the complexity measure for the amount of time needed to search a (a,b)-tree (log n).
A low child, an equal child, and a high child are the three possible nodes that might be present in a tree of the kind known as a ternary search tree. Every node in the tree is responsible for storing a single character, and the tree as a whole is organized in the same manner as a binary search tree is, with the optional addition of a third node.
When doing a search using a ternary search tree, you must first submit a string before determining which paths include it.
The temporal complexity of exploring a balanced ternary search tree is represented by the letter O. (log n).
Assuming that the tree is in some kind of order, we may use a key to look for anything specific inside the tree. The algorithms that are going to be discussed here are generalizations for binary search trees; however, the basic concept may be used for trees in other formats as well.
search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return node
searchIterative(key, node)
currentNode := node
while currentNode is not NULL
if currentNode.key = key
return currentNode
else if currentNode.key > key
currentNode := currentNode.left
else
currentNode := currentNode.right
The value that is the lowest in a sorted tree may be found at the node that is the farthest to the left, while the value that is the highest can be found at the node that is the furthest to the right.
findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key
findMaximum(node)
if node is NULL
return EMPTY_TREE
max := node
while max.right is not NULL
max := max.right
return max.key
{End Chapter 1}
Chapter 2: Binary search tree
In the field of computer science, a binary search tree (BST), which is also known as an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. Other names for this type of tree include an ordered binary tree and a sorted binary tree. The height of the binary search tree has a direct bearing on the amount of time that is needed to complete various operations on the tree.
Binary search trees make it possible to do binary search, which enables a quick searching as well as the insertion and removal of data items. The lookup efficiency in a BST is proportionate to that of a binary logarithm. This is due to the fact that the nodes in a BST are put out in such a way that each comparison skips about half of the remaining tree. Conway Berners-Lee and David Wheeler are credited with developing BSTs in the 1960s as a solution to the difficulty of efficiently storing labeled data. BSTs were created to solve the problem.
Because random node insertions may result in degeneracy, the performance of a binary search tree is contingent on the order in which the nodes are added to the tree; nevertheless, several variants of the binary search tree can be constructed with assured worst-case performance. The following are examples of fundamental operations: search, traversal, insert, and delete. Better performance may be expected from BSTs with assured worst-case complexity than from an unsorted array, which would need linear search time.
An examination of the BST's level of complexity reveals that, on average, the insert, delete and search takes O(\log n) for n nodes.
In the worst possible scenario, they degrade to that of a singly linked list: O(n) .
In order to combat the uncontrollable growth of the tree's height caused by arbitrary additions and removals, In order to reduce the worst lookup complexity to the level of the binary logarithm, self-balancing variations of BSTs have been developed.
The earliest self-balancing binary search trees were actually called AVL trees, Georgy Adelson-Velsky and Evgenii Landis are credited with having created it in the year 1962.
The implementation of abstract data types like dynamic sets, lookup tables, and priority queues, as well as the usage of binary search trees in sorting algorithms like tree sort, are all possible with the help of binary search trees.
Multiple scholars, including P.F. Windley, Andrew Donald Booth, Andrew Colin, and Thomas N. Hibbard, came to the same conclusion separately and developed what is now known as the binary search tree method.
If the nodes are added to the tree in any random sequence, the amount of time required to complete a binary search tree will climb exponentially along with the tree's height, therefore self-balancing binary search trees were introduced to bound the height of the tree to O(\log n) .
A binary search tree is a rooted binary tree in which the nodes are arranged in strict total order in which the nodes with keys greater than any particular node is stored on the right sub-trees and the ones with equal to or less than are stored on the left sub-tree satisfying the binary search property.: 299-302
A basic data structure that is utilized in the building of abstract data structures such as sets, multisets, and associative arrays are called a binary search tree.
It is possible to either recursively or iteratively program the process of searching a binary search tree for a certain key.
The first step in the search is to investigate the root node.
If there is no tree at all, The key that is being looked for is not present anywhere in the tree.
Otherwise, if the key's value is the same as the root's, then, the node is located and returned when the search was successful.
In the event that the key's value is lower than that of the root, The next step in the search is to investigate the left subtree.
Similarly, in the event that the value of the key exceeds that of the root, The next step of the search involves looking through the appropriate subtree.
This process is repeated until the key is found or the remaining subtree is {\displaystyle {\text{nil}}} .
If the searched key is not found after a {\displaystyle {\text{nil}}} subtree is reached, then the key is not present in the tree.: 290–291
The following pseudocode implements the BST search procedure through recursion.: 290
The recursive procedure continues until a {\displaystyle {\text{nil}}} or the {\displaystyle {\text{key}}} being searched for are encountered.
A while loop may be created from the recursive form of the search by unrolling
it.
On the majority of machines, the iterative version is found to be more efficient.: 291
Given that the search might continue till reaching a leaf node, the running time complexity of BST search is O(h) where h is the height of the tree.
However, the worst case for BST search is O(n) where n is the total number of nodes in the BST, due to the possibility that an imbalanced BST would degenerate into a linked list.
However, if the BST is height-balanced the height is O(\log n) .: 290
Regarding certain procedures, given a node {\displaystyle {\text{x}}} , finding the successor or predecessor of {\displaystyle {\text{x}}} is crucial.
Assuming that each of the keys on the BST has its own identity, the successor of a node {\displaystyle {\text{x}}} in BST is the node with the smallest key greater than {\displaystyle {\text{x}}} 's key.
To put things another way, the predecessor of a node {\displaystyle {\text{x}}} in BST is the node with the largest key smaller than {\displaystyle {\text{x}}} 's key.
Following is pseudocode for finding the successor and predecessor of a