Search Tree: Fundamentals and Applications

By Fouad Sabry

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.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jun 28, 2023

Book preview

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