Scribd
Upload
20 views

Group4 Binary Search Tree

The document discusses binary search trees, including their definition, operations like searching, insertion, deletion and traversal, properties, types, performance comparisons and applications. Binary search trees arrange nodes in a way that the value of each node's left subtree is less than the node's value and the value of the right subtree is greater than or equal to the node's value.

Uploaded by

Nwaigwe Spencer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
20 views

Group4 Binary Search Tree

The document discusses binary search trees, including their definition, operations like searching, insertion, deletion and traversal, properties, types, performance comparisons and applications. Binary search trees arrange nodes in a way that the value of each node's left subtree is less than the node's value and the value of the right subtree is greater than or equal to the node's value.

Uploaded by

Nwaigwe Spencer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Binary Search Tree

Definition

This is a class of binary tree in which the node are arrange in a specific order,
this is also called ordered binary tree.

Operations of Binary Search Tree.

Binary Search Tree (BST), the value of all the node in left sub tree is less than
the node in the right sub tree is greater or equal to the value of the root the
shape of the binary search dependence entirely on the order of insertion or
the value of the nodes.

Example: Draw the binary search tree when the node are added in this order
(11, 6, 8, 19, 4, 10, 5, 17)

Solution

11

6 19

43
4 8
31 49
7 10
5

Diagram of Binary Search Tree

There has been a lot of research to prevent degeneration of the tree resulting
in worst case fame complexity of 0(n) of details see section types

Operation of Binary Search Tree

Binary Search Tree support there main operations deletion of elements and
lookup checking weather a key is present

Searching
Searching in binary search tree for a specific key can be programmed
recursively or interactively

We begin by examine the root node. If the tree is null the key we are searching
for does not exist

In the tree otherwise if the key equal that of the not the search is successful
and we return the node. If the key is less than that of the root, we search the
left sub tree

There are algorithm method can be implemented iteratively searching with


dip locates is allowed

Insertion

Insertion begin as a search would begin let see how a typical binary search
tree insertion in c++

Void insert (Node & another way to explain insertion is that in order to insert
a new code in the tree its key is first compared with that of the root if its key is
less then the roots it is then compared with the key of the root’s left could if
the key is greater it as compared with the root’s right word

Deletion

When removing a node from a binary search tree it is mandatory to maintain


the in-order sequence of the nodes to following are the method to do flees:

1. Deleting a node with no children simply remove the node from the tree
2. Deleting a node with no child
3. Deleting a node with two children

Traversal

Once binary search tree has been created its elements can be retrieved in-
order by recursively traversing the left sub tree of the root node, accessing the
node itself then recursively traversing the right sub tree of the node,
continuing the pattern with each node in the tree as if recursively accessed

Verification
Sometimes we already have a binary tree and we need to determine whether
it is BST this problem has a simple recursive solution

BST Properties

1. Every node on the right sub tree has to be larger than the current node
2. Every node on the left subs tree has to be smaller the current node

These are the key to figure out whether a tree is a BST or root

Example of Applications

1. SORT: A binary search tree can be used to implement a simple sorting


algorithm similar to heap sort, we insert all the values we wish to sort
into a new ordered data structure.
2. PRIORITY QUEUE OPERATIONS: BST can serve as priority queues
structures that allow insertion of arbitrary key as well as lookup and
deletion of minimum (or max) key.

Types of BST

There are main type of BST

1. AVL tree and red-black trees are both forms of self-balancing binary
search trees a splay tree is a binary search that automatically moves
frequently accessed demands nearer to the root. In a treap (tree heap),
each node also holds a (randomly chosen) priority and the parent node
has higher priority than its children tango trees are trees optimized for
fast searches
2. T-trees are binary search trees optimized to reduce storage space
overhead, widely used for in-memory databases

Performance Comparisons

D.A. Heger(2004) presented a performance comparison of binary search trees.

Optimal Binary Search Trees

Tree rotations are very common internal oprations in birnary trees to keep
perfect, or near to perfect, internal balance in the tree.
Basic operation of BST

1. Search
2. Insert
3. Pre-ordered transversal
4. Transversal – post order
5. In-order – transversal

Properties of BST

1. The tree has a root node date is used as the starting point for any
operation
2. Each node in the tree has one or two nodes attached to it one is to the
night of the node, and the other is to the left
3. Everything to the right of the node is larger in value compared to it
everything to the left of a node is smaller in value compared to CTL
The main valuable property of BST is that they store data in a way that
is easy for search when data is in a BST we can use the property of left
and right nodes to determine where a node we are searching for is likely
to be it takes less time to search BST compared to searching through a
list of value one by one

References

^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein,


Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and
McGraw-Hill. ISBN 0-262-03384-4.^ a b Mehlhorn, Kurt; Sanders,
Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF).
Springer.^ Trubetskoy, Gregory. "Linus on understanding pointers".
Retrieved 21 February 2019.^ Robert Sedgewick, Kevin Wayne: Algorithms
Fourth Edition. Pearson Education, 2011, ISBN 978-0-321-57351-3, p.
410.^ Heger, Dominique A. (2004), "A Disquisition on The Performance
Behavior of Binary Search Tree Data Structures" (PDF), European Journal for
the Informatics Professional, 5 (5): 67–75, archived from the original (PDF) on
2014-03-27, retrieved 2010-10-16^ Gonnet, Gaston. "Optimal Binary Search
Trees". Scientific Computation. ETH Zü rich. Archived from the original on 12
October 2014. Retrieved 1 December 2013.

You might also like