Binary tree

Binary Tree
Published on 10 March, 2014
A binary tree is a recursive data structure where data is stored in a node that has a value, and
two pointers going left and right which go to another node. They have a similar visual
representation of a tree, starting from the root node, then either branching left or right until
the desired node is found.
Definitions:
 Root node – The top most node; the starting point of the binary tree.
 Internal node – A node that has a two or one branching nodes, and is not the root
node.
 Subtree – Similar characteristics to the internal node.
 Leaf – A node that doesn’t have any further branching nodes.
 Height – Total of the longest chain of branching nodes from the root.
Operations:
 Create – Create a node.
 Remove – Remove a tree.
 Display – Display all values in a tree.
 Find – Find a node that contains a certain value.
 Insert – Insert a value into the tree.
 Change – Change a value stored in a node.
 Count – Count the number of nodes in a tree.
Complexity:
Average Worst case
Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

Binary Search Tree:

A binary search tree is a binary tree where the nodes are in order by value. For each node, all
the elements on the left subtree are less than or equal to the base subtree node, and all the
elements on the right are higher than the base subtree node. Each following subtree follows
this same constraint. The benefit of this is that it is fast for lookup and insertion; good for
dictionary style problems.
The shape of a binary search tree is a key role to its performance. If values where added to a
binary search tree in increasing order, then the tree nodes would grow to the right side. The
opposite would occur if the values were added in decreasing order. This is a problem as the
binary search tree would not be balanced, increasing search times. Rebalancing the binary
search tree would improve the efficiency, however can be an expensive operation.
Filed in Computer Science Revision | No replies