How to draw binary search tree
Binary Search Tree (BST) with Example
What is a Binary Search Tree?
The binary search tree is an advanced algorithm used for analyzing the node, its left and right branches, which are modeled in a tree structure and returning the value. The BST is devised on the architecture of a basic binary search algorithm; hence it enables faster lookups, insertions, and removals of nodes. This makes the program really fast and accurate.
In this Data Structure tutorial, you will learn:
- What is a Binary Search Tree?
- Attributes of Binary Search Tree
- Why do we need a Binary Search Tree?
- Types of Binary Trees
- How Binary Search Tree Works?
- Important Terms
Attributes of Binary Search Tree
A BST is made of multiple nodes and consists of the following attributes:
- Nodes of the tree are represented in a parent-child relationship
- Each parent node can have zero child nodes or a maximum of two subnodes or subtrees on the left and right sides.
- Every sub-tree, also known as a binary search tree, has sub-branches on the right and left of themselves.
- All the nodes are linked with key-value pairs.
- The keys of the nodes present on the left subtree are smaller than the keys of their parent node
- Similarly, The left subtree nodes’ keys have lesser values than their parent node’s keys.
- There is the main node or parent level 11. Under it, there are left and right nodes/branches with their own key values
- The right sub-tree has key values greater than the parent node
- The left sub-tree has values than the parent node
Why do we need a Binary Search Tree?
- The two major factors that make binary search tree an optimum solution to any real-world problems are Speed and Accuracy.
- Due to the fact that the binary search is in a branch-like format with parent-child relations, the algorithm knows in which location of the tree the elements need to be searched. This decreases the number of key-value comparisons the program has to make to locate the desired element.
- Additionally, in case the element to be searched greater or less than the parent node, the node knows which tree side to search for. The reason is, the left sub-tree is always lesser than the parent node, and the right sub-tree has values always equal to or greater than the parent node.
- BST is commonly utilized to implement complex searches, robust game logics, auto-complete activities, and graphics.
- The algorithm efficiently supports operations like search, insert, and delete.
Types of Binary Trees
Three kinds of binary trees are:
- Complete binary tree: All the levels in the trees are full of last level’s possible exceptions. Similarly, all the nodes are full, directing the far left.
- Full binary tree: All the nodes have 2 child nodes except the leaf.
- Balanced or Perfect binary tree: In the tree, all the nodes have two children. Besides, there is the same level of each subnode.
Learn more about Binary Tree in Data Structure if you are interested.
How Binary Search Tree Works?
The tree always has a root node and further child nodes, whether on the left or right. The algorithm performs all the operations by comparing values with the root and its further child nodes in the left or right sub-tree accordingly.
Depends upon the element to be inserted, search, or deleted, after the comparison, the algorithm can easily drop the left or right subtree of the root node.
BST primarily offers the following three types of operations for your usage:
- Search: searches the element from the binary tree
- Insert: adds an element to the binary tree
- Delete: delete the element from a binary tree
Each operation has its own structure and method of execution/analysis, but the most complex of all is the Delete operation.
Always initiate analyzing tree at the root node and then move further to either the right or left subtree of the root node depending upon the element to be located is either less or greater than the root.
- The element to be searched is 10
- Compare the element with the root node 12, 10 < 12, hence you move to the left subtree. No need to analyze the right-subtree
- Now compare 10 with node 7, 10 > 7, so move to the right-subtree
- Then compare 10 with the next node, which is 9, 10 > 9, look in the right subtree child
- 10 matches with the value in the node, 10 = 10, return the value to the user.
Pseudo Code for Searching in BST:
search(element, root) if !root return -1 if root.value == element return 1 if root.value < element search(element, root.right) else search(element, root.left)
This is a very straight forward operation. First, the root node is inserted, then the next value is compared with the root node. If the value is greater than root, it is added to the right subtree, and if it is lesser than the root, it is added to the left subtree.
- There is a list of 6 elements that need to be inserted in a BST in order from left to right
- Insert 12 as the root node and compare next values 7 and 9 for inserting accordingly into the right and left subtree
- Compare the remaining values 19, 5, and 10 with the root node 12 and place them accordingly. 19 > 12 place it as the right child of 12, 5 < 12 & 5 < 7, hence place it as left child of 7. Now compare 10, 10 is < 12 & 10 is > 7 & 10 is > 9, place 10 as right subtree of 9.
Pseudocode for Inserting a Node in BST:
insert (element, root) Node x = root Node y = NULL while x: y = x if x.value < element.value x = x.right else x = x.left if y.value < element y.right = element else y.left = element
For deleting a node from a BST, there are some cases, i.e. deleting a root or deleting a leaf node. Also, after deleting a root, we need to think about the root node.
Say we want to delete a leaf node, we can just delete it, but if we want to delete a root, we need to replace the root’s value with another node. Let’s take the following example:
- Case 1- Node with zero children: this is the easiest situation, you just need to delete the node which has no further children on the right or left.
- Case 2 – Node with one child: once you delete the node, simply connect its child node with the parent node of the deleted value.
- Case 3 Node with two children: this is the most difficult situation, and it works on the following two rules
- 3a – In Order Predecessor: you need to delete the node with two children and replace it with the largest value on the left-subtree of the deleted node
- 3b – In Order Successor: you need to delete the node with two children and replace it with the largest value on the right-subtree of the deleted node
- This is the first case of deletion in which you delete a node that has no children. As you can see in the diagram that 19, 10 and 5 have no children. But we will delete 19.
- Delete the value 19 and remove the link from the node.
- View the new structure of the BST without 19
- This is the second case of deletion in which you delete a node that has 1 child, as you can see in the diagram that 9 has one child.
- Delete the node 9 and replace it with its child 10 and add a link from 7 to 10
- View the new structure of the BST without 9
- Here you will be deleting the node 12 that has two children
- The deletion of the node will occur based upon the in order predecessor rule, which means that the largest element on the left subtree of 12 will replace it.
- Delete the node 12 and replace it with 10 as it is the largest value on the left subtree
- View the new structure of the BST after deleting 12
- 1 Delete a node 12 that has two children
- 2 The deletion of the node will occur based upon the In Order Successor rule, which means that the largest element on the right subtree of 12 will replace it
- 3 Delete the node 12 and replace it with 19 as it is the largest value on the right subtree
- 4 View the new structure of the BST after deleting 12
Pseudo Code for Deleting a Node:
delete (value, root): Node x = root Node y = NULL # searching the node while x: y = x if x. value < value x = x.right else if x.value > value x = x.left else if value == x break # if the node is not null, then replace it with successor if y.left or y.right: newNode = GetInOrderSuccessor(y) root.value = newNode.value # After copying the value of successor to the root #we're deleting the successor free(newNode) else free(y)
- Insert: Inserts an element in a tree/create a tree.
- Search: Searches an element in a tree.
- Preorder Traversal: Traverses a tree in a pre-order manner.
- Inorder Traversal: Traverses a tree in an in-order manner.
- Postorder Traversal: Traverses a tree in a post-order manner.
- BST is an advanced level algorithm that performs various operations based on the comparison of node values with the root node.
- Any of the points in a parent-child hierarchy represents the node. At least one parent or root node remains present all the time.
- There are a left subtree and right subtree. The left subtree contains values that are less than the root node. However, the right subtree contains a value that is greater than the root node.
- Each node can have either zero, one, or two children.
- A binary search tree facilitates primary operations like search, insert, and delete.
- Delete being the most complex have multiple cases, for instance, a node with no child, node with one child, and node with two children.
- The algorithm is utilized in real-world solutions like games, autocomplete data, and graphics.
Binary Search Tree | Example | ConstructionBinary Tree-
Before you go through this article, make sure that you gone through the previous article on Binary Trees.
We have discussed-
- Binary tree is a special tree data structure.
- In a binary tree, each node can have at most 2 children.
- In a binary tree, nodes may be arranged in any random order.
In this article, we will discuss about Binary Search Trees.
Binary Search Tree-
|Binary Search Tree is a special kind of binary tree in which nodes are arranged in a specific order.|
In a binary search tree (BST), each node contains-
- Only smaller values in its left sub tree
- Only larger values in its right sub tree
Number of Binary Search Trees-
Number of distinct binary search trees possible with 3 distinct keys
= 2×3C3 / 3+1
= 6C3 / 4
If three distinct keys are A, B and C, then 5 distinct binary search trees are-
Binary Search Tree Construction-
Let us understand the construction of a binary search tree using the following example-
Construct a Binary Search Tree (BST) for the following sequence of numbers-
50, 70, 60, 20, 90, 10, 40, 100
When elements are given in a sequence,
- Always consider the first element as the root node.
- Consider the given elements and insert them in the BST one by one.
The binary search tree will be constructed as explained below-
- As 70 > 50, so insert 70 to the right of 50.
- As 60 > 50, so insert 60 to the right of 50.
- As 60 < 70, so insert 60 to the left of 70.
- As 20 < 50, so insert 20 to the left of 50.
- As 90 > 50, so insert 90 to the right of 50.
- As 90 > 70, so insert 90 to the right of 70.
- As 10 < 50, so insert 10 to the left of 50.
- As 10 < 20, so insert 10 to the left of 20.
- As 40 < 50, so insert 40 to the left of 50.
- As 40 > 20, so insert 40 to the right of 20.
- As 100 > 50, so insert 100 to the right of 50.
- As 100 > 70, so insert 100 to the right of 70.
- As 100 > 90, so insert 100 to the right of 90.
This is the required Binary Search Tree.
To gain better understanding about Binary Search Trees,
Watch this Video Lecture
PRACTICE PROBLEMS BASED ON BINARY SEARCH TREES-
A binary search tree is generated by inserting in order of the following integers-
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left subtree and right subtree of the root respectively is _____.
- (4, 7)
- (7, 4)
- (8, 3)
- (3, 8)
Using the above discussed steps, we will construct the binary search tree.
The resultant binary search tree will be-
- Number of nodes in the left subtree of the root = 7
- Number of nodes in the right subtree of the root = 4
Thus, Option (B) is correct.
How many distinct binary search trees can be constructed out of 4 distinct keys?
Number of distinct binary search trees possible with 4 distinct keys
= 2nCn / n+1
= 2×4C4 / 4+1
= 8C4 / 5
Thus, Option (B) is correct.
The numbers 1, 2, …, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be-
Let n = 4 and p = 3.
Then, given options reduce to-
Our binary search tree will be as shown-
Clearly, first inserted number = 1.
Thus, Option (C) is correct.
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with given set so that it becomes a binary search tree?
- C(2n, n) / n+1
Option (B) is correct.
To watch video solutions and practice more problems,
Watch this Video Lecture
Download Handwritten Notes Here-
Next Article- Binary Search Tree Traversal
Get more notes and other study material of Data Structures.
Watch video lectures by visiting our YouTube channel LearnVidFun.
Binary search tree - frwiki.wiki
For articles of the same name, see ABR, Arbre (disambiguation) and BST.
An example of a binary search tree containing 9 keys.
In computer science, the binary search tree or ABR (in English, binary search tree or BST ) is a data structure that is a set or associative array whose keys belong to a fully ordered set. The binary search tree allows you to quickly find a key, insert or delete a key.
- 1 Definition
- 1.1 General definition
- 1.2 Specific definitions
- 2 Operations
- 2.1 Research
- 2.2 Insert
- 2.3 Uninstall
- 3 Applications
- 3.1 Ordered course
- 3.2 Sorting
- 3.3 Priority queues
- 4 Balancing
- 5 extensions
- 6 External links
A binary search tree is a binary tree in which each node has a key such that each node of the left subtree has a key less than or equal to the key of the node in question, and each node of the right subtree has a key greater than or equal to this - Depending on the ABR implementation, keys with the same value may or may not be disallowed. The nodes we added become the leaves of the tree.
- A binary search tree is considered complete if all levels of the tree are filled, except possibly the last one, where the nodes are on the left.
- An ideal binary tree is a complete tree with all leaves at the same height (the last level is completely occupied).
- A binary tree is called degenerate if each of its nodes has at most one child.
- A binary tree is said to be balanced if all paths from the root to the leaves are of the same length.
Rotation is the balancing operation of the shafts.
Finding a node with a specific key in a binary tree is a recursive process. Let's start by learning the root. If its key is the desired one, the algorithm terminates and returns the root. If it is strictly less then it is in the left subtree, which we then recursively search for. Similarly, if the found key is strictly greater than the root key, the search continues in the right subtree. If we reach a leaf whose key is not the one we are looking for, then we know that the key we are looking for does not belong to any node, so it does not appear in the search tree. We can compare the exploration of a binary search tree with a dichotomous search, which works in much the same way, except that it goes directly to each element of the array, rather than following links. The difference between these two algorithms is that in dichotomous search we assume that there is a criterion for dividing the space into two parts, which is not present in tree search.
font Recherche(A,e) Si A = . Faux retourner Sinon A = (x,FilsGauche,FilsDroit) Si x = e retourner vrai Sinon si e < x retourner Recherche(FilsGauche,e) Sinon retourner Recherche(FilsDroit,e)
This operation takes O(log(n)) in the average case, but O(n) in the critical case where the tree is completely unbalanced and looks like a linked list. This problem is avoided if the shaft is balanced by rotation during insertions, which can lead to too long lists.
Insertion of a node begins with a search: we are looking for the key of the node to be inserted; when we reach a leaf, we add a node as a child of that leaf, comparing its key with the leaf's key: if it's lower, the new node will be on the left; otherwise it will be correct.
font Insertion(A,e) Si A = . retourner (e,.,.) Sinon A = (x,FilsGauche,FilsDroit) Si e < x retourner (x,Insertion(FilsGauche,e),FilsDroit) Sinon retourner (x,FilsGauche,Insertion(FilsDroit,e))
The complexity is the same as for the search: O (log n) in the average case and O (n) in the critical case.
You can also write a procedure to add an element to the root of a binary tree. This operation requires the same complexity, but is better in terms of element access.
We start by looking up the key of the node to be deleted in the tree. Once the node to be deleted has been found by its key, there are several cases to consider:
- Leaf Removal : You just need to remove it from the tree as it has no threads.
- Removing a node with a child element : it must be removed from the tree, replaced by its child.
- Deleting a node with two child nodes: Suppose the node to be deleted is called N (the node with value 7 in the figure below). We swap node N with its nearest successor (leftmost node of the right subtree, below, node of value 9) or its nearest predecessor (the rightmost node of the subtree on the left, below, the node with value 6). This allows the binary search tree structure to be preserved at the end of the operation. We then apply the delete procedure again to N , which is now a leaf or node with only one child.
font Suppression(A,e) si A = . returner. sinon A = (x,FilsGauche,FilsDroit) si e > x retourner (x,FilsGauche,Suppression(FilsDroit,e)) si e < x retourner (x,Suppression(FilsGauche,e),FilsDroit) sinon x = e si FilsGauche = . et FilsDroit = . returner. si FilsGauche = . retourner FilsDroit si FilsDroit = . retourner FilsGauche sinon y = Max(FilsGauche) retourner (y,Suppression(FilsGauche,y),FilsDroit)
This choice of implementation can lead to tree imbalance. Indeed, since the leaves of the left subtree are always removed, frequent use of this function will result in a heavier tree on the right than on the left. This can be fixed by successively alternating the removal of the minimum of the right son with the removal of the maximum of the left son, instead of always choosing the latter. For example, a random factor can be used: the program will have one in two chances to select the correct child and one in two chances to select the left child.
In all cases, this operation requires traversing the tree from root to leaf: so the execution time is proportional to the depth of the tree, which is n in the worst case , hence the maximum complexity is O(n) .
We can get the keys of the binary search tree in ascending order by doing an infix scan. You want to concatenate in this order a sorted list obtained recursively by traversing the left child at the root, and then to a list obtained recursively by traversing the right child. This can be done in reverse order, starting from the right subtree. The path of the tree runs in linear time because it only has to go through each node once.
font ParcoursInfixe(A): si A = . retourner sinon A = (x,FilsGauche,FilsDroit) retourner ParcoursInfixe(FilsGauche) + [x] + ParcoursInfixe(FilsDroit)
So we can create a simple but inefficient sorting algorithm by inserting all the keys we want to sort into a new binary search tree and then iterating through that tree in an ordered manner as above.
A = . pour e dans L faire A = Insertion(A,e) ListeTriee = ParcoursInfixe(A)
The worst execution time is O(n²), where n is the number of keys in the tree, obtained when the keys are already ordered: then we have a linked list. For example, if we give the keys 1, 2, 3, 4, 5 in that order, we get the tree (Void, 1, (Void, 2, (Void, 3, (Void, 4, (Void, 5, Empty)) )))) . There are many ways to avoid this problem, the most common being a balanced tree. Then we can come to the worst case in O(n*ln(n)).
Binary search trees can be used to implement an abstract type in a priority queue. in fact, the key insertion and vacuum test operations are performed with advantageous complexity (respectively in O(log(n)) and in O(1), where n is the number of keys represented in the tree). For the operation of deleting the largest key, it is enough to walk the tree from its root, selecting the right child of each node, and remove the leaf leaf. this requires a number of operations equal to the height of the tree, hence the logarithmic complexity of the number of keys. The infamous advantage of this priority queue representation is that with a similar process, there is also a logarithmic time deletion of the smallest key.
Insertion and deletion are performed in O (h), where h is the height of the tree. This turns out to be especially costly when the tree is very unbalanced (for example, a comb tree whose height depends linearly on the number of keys), and therefore we get more efficient balancing of trees during their use. There are methods for obtaining balanced trees, i.e. to guarantee the logarithmic height of the number of elements:
- AVL tree
- these trees are red-black
- trees 2-3
- in 2-3-4 trees
- in B-trees
The split tree is a binary search tree that automatically brings frequently used items closer to the root. In treap , each node also has a higher priority than each of its children.
- (fr) Introduction to Binary Search Trees
|Binary tree||Binary search tree Excavation tree Cartesian tree MVP tree (en) Vertex tree (en) T-tree (en)|
|Balanced tree||AA Tree (c) AVL Tree LLRB Tree (c) Bicolor Tree Drop Tree Splay Tree Cartesian Tree|
|Wood B||B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a, b) -tree (en) Dancing tree Htree (en)|
|Sort||Suffix tree Radix tree Ternary search tree X-fast tree Y-fast tree|
|Binary decomposition of space trees||Quadtree Octree kd tree (relaxed) Implicit kd-tree (in) vp-tree (en)|
|Non-binary trees||Tree exponent Merge tree ( inches ) Shaft intervals Shaft PQ Scope tree ( tree range ) SPQR tree Van Emde Boas tree|
|Spatial database tree||R-tree R + tree (en) R * tree (en) X-tree (en) M-tree (en) Segment tree Hilbert R-tree (en) Priority R-tree (en)|
|Other trees||Merkle tree · Minimum weight spanning tree · Syntax tree · Abstract syntax tree · Finger tree (c) · Order of statistics tree (c) · Metric tree · Cover tree (c) · BK-tree (c) · Doubly chained tree · iDistance ( en) Linked tree (en) Fenwick tree (en) Heap Binomial structure Heap Fibonacci tas Stitched tree|
|Abstract type|| |
|Schedule||Binary solution diagram|
Binary search tree, property definition, Structure operations. ..
Hello, today we will talk about the binary search tree definition of the property of the operation, I promise to tell you everything I know. In order to better understand what is binary search tree operation property definition, highly recommend reading everything from the Data Structures category.
|Binary search tree|
| Time complexity |
Binary search tree definition and properties, operations
1 Basic operations in the binary search tree
1. 1 Finding an element (FIND)
1.2 Adding an element (INSERT)
1.3 Removing a node (REMOVE)
1.4 Tree traversal (TRAVERSE)
1.5 Splitting a tree by key
1.6 Combining two trees into one
2 Wood balancing
3 Binary search tree problems
Binary search tree (eng. binary search tree , BST) is a binary tree for which the following additional conditions are satisfied ( search tree properties ):
- Both left and right subtrees are binary trees search.
- All nodes of the left subtree of an arbitrary node X have data key values is less than than the data key value of node X itself.
- While the values of the data keys of all nodes of the right subtree (of the same node X) are greater than than the value of the data key of node X.
Obviously, the data in each node must have keys on which the comparison operation is defined less than .
Typically, the information representing each node is a record, not a single data field. However, this is about the implementation, not the nature of the binary search tree.
An example of a binary search tree
For implementation purposes, a binary search tree can be defined as follows:
- node, left and right are links to nodes that are children of this node - the left and right sons, respectively. To optimize the algorithms, specific implementations also assume the definition of the parent field in each node (except the root) - a link to the parent element.
- Data (data) has a key (key) on which the comparison operation "less than" is defined. In specific implementations, this can be a pair (key, value) - (key and value), or a reference to such a pair, or a simple definition of a comparison operation on the required data structure or a reference to it.
- For any node X, the properties of the search tree are fulfilled: key[left[X]] < key[X] ≤ key[right[X]], i.e. the data keys of the parent node are greater than the data keys of the left child and are not strictly less than the data keys of the right one.
A binary search tree should not be confused with a binary heap built according to other rules.
The main advantage of a binary search tree over other data structures is the possible high efficiency of implementing search and sorting algorithms based on it.
The binary search tree is used to build more abstract structures such as sets, multisets, associative arrays.
Basic operations in the binary search tree
The basic interface of the binary search tree consists of three operations:
- FIND(K) - finds the node that stores the pair (key, value) with key = K.
- INSERT(K,V) — adding a pair (key, value) = (K, V) to the tree.
- REMOVE(K) - deleting a node that stores a pair (key, value) with key = K.
This abstract interface is a general case, for example, of such interfaces taken from applied tasks: records.
In fact, a binary search tree is a data structure that can store a table of pairs (key, value) and supports three operations: FIND, INSERT, REMOVE.
In addition, the binary tree interface includes three additional tree node traversals: INFIX_TRAVERSE, PREFIX_TRAVERSE, and POSTFIX_TRAVERSE. The first of them allows you to traverse the nodes of the tree in non-decreasing order of keys.
Given : tree T and key K.
Task : check if there is a node with key K in tree T, and if so, return a link to that node.
- If the tree is empty, report that the node was not found and stop.
- Else compare K with the key value of the root node X.
- If K=X, issue a link to this node and stop.
- If K>X, search recursively for the key K in the right subtree of T.
- If K
Element search (example)
Element search 4
To search for an element in a binary search tree, you can use the following function, which takes the root of the tree and the search key as parameters. For each node, the function compares the value of its key with the desired key. If the keys are the same, then the function returns the current node, otherwise the function is called recursively for the left or right subtree. The nodes that the function visits form a downward path from the root, so its running time is O ( h )O(h), where h h is the height of the tree.
Node search(x : Node , k : T ): if x == null or k == x. key return x if k < x.key return search(x.left, k) else return search(x.right, k)
Finding minimum and maximum
To find the minimum element in the search binary tree, you just need to follow the indicators L E F T LEFT from the root of the tree, until the value of N 9050 N 9050 L L 9050 L 9050 L 9050 L Nulll. If a node has a left subtree, then by the property of a binary search tree, it stores all elements with a smaller key. If it does not exist, then this vertex is the minimum. The maximum element is searched in the same way. To do this, follow the right signs.
Node minimum(x : Node ): if x.left == null return x return minimum(x. left)
Node maximum(x : Node ): if x.right == null return x return maximum(x.right)
These functions take the root of a subtree, and return the minimum (maximum) element in the subtree. Both procedures are completed in O ( h )O(h).
Finding the next and previous element
Implementation using parent information
If a node has a right subtree, then the element following it will be the minimum element in that subtree. If it does not have a right subtree, then we must proceed upward until we encounter a node that is the left child of its parent. The search for the previous one will be performed in the same way. If a node has a left subtree, then the element following it will be the maximum element in that subtree. If it does not have a left subtree, then we must proceed upward until we encounter a node that is the right child of its parent.
Node next(x : Node ): if x.right != null return minimum(x.right) y = x.parent while y != null and x == y.right x=y y = y.parent return y
Node prev(x : Node ): if x.left != null return maximum(x.left) y = x.parent while y != null and x == y.left x=y y = y.parent return y
Both operations are performed in time O ( h )O(h).
Implementation without using parent information
Consider searching for the next element for some key x x . This is indicated by the site https://intellect.icu. We will start the search from the root of the tree, keeping the current node C U R R E N T Current and node S U 9050 C 9050 C E 9050 S S S S S S S S S S S S S S S S 905AT successor, the last visited node whose key is greater than x x.
We go down the tree, as in the node search algorithm. Consider the key of the current node c u r r e n t current. If c u r r e n t . K E Y ⩽ x Current.key⩽x, so the next for x x is located in the right support (in the left support all keys less than C 9050 U R R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R 9050 R e n t . If x < c u r r e n t K E Y XX < N E x T ( X ) ⩽ C 9050 U 9050 R 9050 R 9050 R 9050 E E E E E E E E E E E E E E E . k e y xc u r r e n t 905 01 current 9 can be0500 x x, or the next node is in the left subtree c u r r e n t current. Let's go to the desired subtree and repeat the same steps.
The operation of searching for the previous element is implemented similarly.
Node next(x : T ): Node current = root, successor = null // root is the root of the tree while current != null if current key > x successor = current current = current left else current = current right return successor
Adding (inserting) an element (INSERT)
Given : tree T and pair (K, V).
Problem : insert a pair (K, V) into the tree T (if K matches, replace V).
- If the tree is empty, replace it with a tree with one root node ((K,V), null, null) and stop.
- Else compare K with the key of the root node X.
- If K>X, cyclically add (K,V) to the right subtree of T.
- If K
- If K=X, replace V of the current node with the new value. (although you can organize a list of V values, but that's another topic)
The second example
The insertion operation works similarly to the search for an element, only if the element does not have a child, you need to hang the element being inserted on it.
Implementation using parent information
func insert(x : Node , z : Node ): // x is the root of the subtree, z is the element to be inserted while x != null if z. key > x.key if x.right != null x = x.right else z.parent = x x.right = z break else if z.key < x.key if x.left != null x = x.left else z.parent = x x.left = z break
Implementation without parent information
Node insert(x : Node , z : T ): // x is the root of the subtree, z is the key to be inserted if x == null return Node(z) // hang Node with key = z else if z < x.key x.left = insert(x.left, z) else if z > x.key x.right = insert(x.right, z) return x
The running time of the algorithm for both implementations is O ( h )O(h).
Removing a node (REMOVE)
Given : tree T with root n and key K.
Problem : remove a node with key K (if any) from tree T.
- If tree T is empty, stop;
- Otherwise, compare K with the key X of the root node n.
- If K>X, cyclically remove K from the right subtree of T;
- If K
- If K=X, then three cases need to be considered.
- If there are no both children, then delete the current node and reset the reference to it from the parent node;
- If one of the children does not exist, then we put the values of the fields of the child m instead of the corresponding values of the root node, overwriting its old values, and free the memory occupied by the node m;
- If both children are present, then
- If there is no left node m of the right subtree (n->right->left)
- Copy from (8) to (4) fields K, V and a link to the right node.
- take the leftmost node m, of the right subtree n->right;
- copy data (except for references to child elements) from m to n;
- recursively delete node m.
- If there is no left node m of the right subtree (n->right->left)
Deletion (second example)
Non-recursive implementation of deleting a node from a binary search tree
To remove a node from a binary search tree, three possible situations need to be considered. If the node has no child nodes, then its parent should simply replace the pointer with n u l l null. If a node has only one child node, then a new relationship must be created between the parent of the node being deleted and its child node. Finally, if the node has two child nodes, then you need to find the element following it (this element will not have a left child), hang its right child in the place of the found element, and replace the removed node with the found node. Thus, the property of the binary search tree will not be violated. This removal implementation does not increase the height of the tree. The running time of the algorithm is O ( h )O(h).
|Removing a node with one child node|
|Removing a node with two children|
func delete(t : Node , v : Node ): // t t is the tree, v v is the element to be removed p = v.parent // parent of the element to be removed if v.left == null and v.right == null // first case: element to be removed is a leaf if p. left == v p.left = null if p.right == v p.right = null else if v.left == null or v.right == null // second case: element to be removed has one child if v.left == null if p.left == v p.left = v.right else p.right = v.right v.right.parent = p else if p.left == v p.left = v.left else p.right = v.left v.left.parent = p else // third case: element to be removed has two children successor = next(v, t) v.key = successor.key if successor.parent.left == successor successor.parent.left = successor.right if successor. right != null successor.right.parent = successor.parent else successor.parent.right = successor.left if successor.left != null successor.right.parent = successor.parent
Recursive implementation of deleting a node from a binary search tree
When deleting a node recursively from a binary tree, three cases need to be considered: the element being removed is in the left subtree of the current subtree, the element being removed is in the right subtree, or the element being removed is in the root. In the first two cases, you need to recursively remove an element from the desired subtree. If the element to be removed is at the root of the current subtree and has two child nodes, then you need to replace it with the minimum element from the right subtree and remove it recursively is the minimum element from the right subtree. Otherwise, if the element to be removed has one child node, replace it with a descendant. The running time of the algorithm is O ( h )O(h). Recursive function returning tree with element removed z z:
Node delete(root : Node , z : T ): // subtree root, key to be deleted if root == null return root if z < root.key root.left = delete(root.left, z) else if z > root.key root.right = delete(root.right, z) else if root.left != null and root.right != null root.key = minimum(root.right).key root.right = delete(root.right, root.key) else if root.left != null root = root.left else root=root.right return root
Tree traversal (TRAVERSE)
There are three tree node traversal operations that differ in the order in which the nodes are traversed.
The first operation, INFIX_TRAVERSE, allows you to traverse all nodes of the tree in ascending order of keys and apply a user-defined callback function f to each node, the operand of which is the address of the node. This function usually only works on the pair (K,V) stored in the node. The INFIX_TRAVERSE operation can be implemented recursively: first it runs itself on the left subtree, then it runs the given function on the root, then it runs itself on the right subtree.
- INFIX_TRAVERSE (tr) Traverse the entire tree following the order (left subtree, top , right subtree). Elements ascending
- PREFIX_TRAVERSE (tr) - traverse the entire tree following the order ( top , left subtree, right subtree). Elements as in tree
- POSTFIX_TRAVERSE (tr) Traverse the entire tree following the order (left subtree, right subtree', top ). Elements in reverse order as in tree
In other sources these functions are called inorder, preorder, postorder respectively
Given : tree T and function f
Objective: apply f to all nodes of the tree T in ascending order 9002 Algorithm :
- If the tree is empty, stop.
- Recursively traverse the left subtree of T.
- Apply the function f to the root node.
- Recursively traverse the right subtree T.
In the simplest case, the function f can output the value of the pair (K,V). When using the INFIX_TRAVERSE operation, all pairs will be displayed in ascending order of keys. If you use PREFIX_TRAVERSE, then the pairs will be displayed in the order corresponding to the description of the tree given at the beginning of the article.
Search Tree Traversal Example
To represent a binary search tree in memory, we will use the following structure:
struct Node: T key // node key Node left // pointer to the left child Node right // pointer to the right child Node parent // pointer to an ancestor
There are three tree node traversal operations that differ in the node traversal order:
- inorderTraversalinorderTraversal - traversal of nodes in sorted order,
- preorderTraversalpreorderTraversal - traversal of nodes in order: vertex, left subtree, right subtree,
- postorderTraversalpostorderTraversal - traversal of nodes in order: left subtree, right subtree, top.
func inorderTraversal(x : Node ): if x != null inorderTraversal(x.left) print x.key inorderTraversal(x.right)
This traversal will output the vertices in the following order: 1 3 4 6 7 8 10 13 14 .
func preorderTraversal(x : Node ) if x != null print x.key preorderTraversal(x.left) preorderTraversal(x.right)
This traversal will output the vertices in the following order: 8 3 1 6 4 7 10 14 13 .
func postorderTraversal(x : Node ) if x != null postorderTraversal(x.left) postorderTraversal(x.right) print x.key
This traversal will output the vertices in the following order: 1 4 7 6 3 13 14 10 8 .
These algorithms complete the traversal in time O ( n )O(n), since the procedure is called exactly twice for each tree node.
Tree splitting by key
The “tree splitting by key” operation allows splitting one search tree into two: with keys < K 0 and ≥ K 0.
Combining two trees into one 9005 Reverse operation: there are two search trees, one has keys < K 0, the other has keys ≥ K 0. Merge them into one tree.
We have two trees: T 1 (smaller) and T 2 (larger). First you need to decide where to take the root: from T 1 or T 2. No standard method, options:
- Take at random (see Cartesian tree).
- If the size of the entire branch is maintained at each node in the tree (see tree with an implicit key), it is easy to estimate the imbalance for both options.
algTree Union(T1, T2) if T1 is empty, return T2 if T2 is empty, return T1 if you decide to make T1 the root, then T = UnionTrees(T1. right, T2) T1.right = T return T1 otherwise T = UnionTrees(T1, T2.left) T2.left = T return T2
It is always desirable that all paths in a tree from the root to the leaves have approximately the same length, that is, that the depth of both the left and right subtrees be approximately the same at any node. Otherwise, performance is lost.
In the degenerate case, it may turn out that the entire left tree is empty at each level, there are only right trees, in which case the tree degenerates into a list (going to the right). Searching (and therefore deleting and adding) in such a tree is equal in speed to searching in a list and much slower than searching in a balanced tree.
The tree rotation operation is used to balance the tree. Turning left looks like this:
- was Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R
- rotation swaps A and B, getting Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R
- also changes in node Parent(A) the link that previously pointed to A, after the rotation it points to B.
Turning to the right looks the same, it is enough to replace all Left with Right in the above example and vice versa.
Quite obviously, the rotation does not break the order of the tree, and has a predictable (+1 or -1) effect on the depths of all affected subtrees.
Algorithms such as red-black tree and AVL are used to decide which turns to make after an addition or deletion.
Both of them require additional information in the nodes - 1 bit for red-black or a signed number for AVL.
Red-black tree requires <= 2 turns after addition and <= 3 after removal, but the worst imbalance can be up to 2 times (the longest path is 2 times longer than the shortest).
AVL tree requires <= 2 rotations after addition and up to tree depth after deletion, but still perfectly balanced (no more than 1 imbalance).
Binary search tree problems
Task: An example of a tree for which it is not enough to check only its neighboring vertices Problems to find the maximum BST in a given binary tree Tree restoration based on the result of preorderTraversa Task: As we remember, the preorderTraversal procedure outputs the values in the nodes of the subtree as follows: first it goes all the way to the left, then at some point it takes a step to the right and again moves to the left. This continues until all vertices have been drawn. The resulting sequence will allow us to uniquely determine the location of all nodes of the subtree. The first vertex will always be at the root. Then, until all the values are used, we will sequentially hang the left children to the last added vertex until we find a number that violates the descending sequence, and for each such number we will look for a vertex without a right child that stores the largest value that does not exceed the one we want put, and we hang the element with the same number as the right son. When we, wanting to find such a vertex, meet some other one that already has a right son, we pass along the branch to the right. We have the right to do this, since if such a vertex is standing, then the bypass procedure has already visited it and turned to the right, so it makes no sense to go down in the other direction. The vertex with the maximum key, from which we will start the search, will be remembered. It will be updated every time a new maximum appears. The procedure for restoring the tree takes O(n). Let us analyze the algorithm using the example of the sequence 8 2 1 4 3 5 adding the right child to them (when a vertex that violates the descending sequence is considered).
Checking that a given tree is a search tree
Determine if the given binary tree is a search tree.
Find a vertex in the given tree such that it will be the root of the search subtree with the largest number of vertices.
Restore the tree according to the sequence output after executing the preorderTraversal procedure.
An example of a tree for which it is not enough to check only its neighboring vertices
Problems to find the maximum BST in a given binary tree
Tree restoration based on the result of preorderTraversa
As we remember, the preorderTraversal procedure outputs the values in the nodes of the subtree as follows: first it goes all the way to the left, then at some point it takes a step to the right and again moves to the left. This continues until all vertices have been drawn. The resulting sequence will allow us to uniquely determine the location of all nodes of the subtree. The first vertex will always be at the root. Then, until all the values are used, we will sequentially hang the left children to the last added vertex until we find a number that violates the descending sequence, and for each such number we will look for a vertex without a right child that stores the largest value that does not exceed the one we want put, and we hang the element with the same number as the right son. When we, wanting to find such a vertex, meet some other one that already has a right son, we pass along the branch to the right. We have the right to do this, since if such a vertex is standing, then the bypass procedure has already visited it and turned to the right, so it makes no sense to go down in the other direction. The vertex with the maximum key, from which we will start the search, will be remembered. It will be updated every time a new maximum appears.
The procedure for restoring the tree takes O(n).
Let us analyze the algorithm using the example of the sequence 8 2 1 4 3 5
adding the right child to them (when a vertex that violates the descending sequence is considered).