Application of binary tree in data structure?

Answer 1

1) the complexity of insertion,deletion and searching operation is depend on the height of the tree.

i.e. if height is n(for skew binary tree) then complexity is O(n) .

2) difficult to get the sorted list from the binary tree.which is easy for BST.

Answer 2

1. One application is to find duplicates in a list of numbers. Let a given list be" 12 34 56 89 33 11 89 the first number in the list is placed in a node that is established as the root of a binary tree. Each number is compared with the node in the root, if the number is larger, we search the right sub-tree else we search the left sub-tree. If the sub-tree is empty, the number is not a duplicate and this will be added as a new node. 2. Binary trees can be used for sorting a given list such that, if we take the first number as root, the numbers less than that number will be transfered to left sub-tree and the greater numbers to right sub-tree. 3. Binary trees are also used for developing the huffman codes.

Answer 3

A binary search tree is a binary tree. Definitions differ, but one alternative says that a binary tree can be either:

• empty
• Or be a root node N with two sons L and R, each of which is a binary tree.

On top of being a binary tree, each node of the binary search tree stores a key. Say the key is an integer. The binary search tree has the property that every key which is to the left of a node M or in its left child is smaller or equal to the node's key. Also, every key which is to the right of a node M or in its right child is greater or equal to its key.
This enables us to use the binary search tree for search (now there's a surprise!):
Looking for a value we start scanning the tree at the root, and go left or right according to the respective node keys, until we either find an identical key or reach a leaf that has another key value, meaning that the search has failed.
We can store a payload with the key, and thus use the binary search tree as a dictionary.
In order for search to be efficient, we need the binary tree to be balanced - No node can have too great a difference between the sizes of its left and right children.
The advantage of binary search trees over hash maps is that we can go over keys in order without needing to sort them. Usually, binary search tree operations take O(log N) when N is the number of nodes while hash map operations take O(1), so the speed of hash maps often makes us choose them over binary search trees.

Answer 4

Binary trees are used to store comparable items that need to be searched often. While adding and removing items to a binary tree are costly compared to a typical list, searching an element takes logarithmic time versus the linear time of a list or array.

Answer 5

• Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries.

• Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.

• Binary Tries - Used in almost every high-bandwidth router for storing router-tables.

• Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.

• Heaps - Used in heap-sort; fast implementations of Dijkstra's algorithm; and in implementing efficient priority-queues, which are used in scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including video games).

• Huffman Coding Tree (Chip Uni) - used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.

• GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers.

• Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.

• Treap - Randomized data structure used in wireless networking and memory allocation.

• T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

Answer 6

A binary tree can be used as a simple decision tree with two options. In this case, each leaf will be a final decision arrived by traversing one branch of the tree. Another use of a binary tree is to sort numerical data in a very simple yet effective way.

Answer 7

A threaded binary tree is structured in an order that, all right child pointers would normally be null and points to the 'in-order successor' of the node. Similarly, all the left child pointers would normally be null and points to the 'in-order predecessor' of the node.Uses of Threaded binary tree:

1.Traversal is faster than unthreaded binary trees

2.More subtle, by enabling the determination of predecessor and successor nodes that starts from any node, in an efficient manner.

3.No stack overload can be carried out with the threads.

4.Accessibility of any node from any other node

5.It is easy to implement to insertion and deletion from a threaded tree.

Answer 8

A binary tree is a tree data structure in which each node has at most two child nodes. There are several common orders in which nodes can be visited. Each of these nodes has useful properties that are exploited in algorithms.

Answer 9

Binary trees are commonly used to implement binary search tree and binary heaps.