BINARY TREES
With my on-going study of algorithms and data structures, I’m continuing to the next data structure, Binary Trees.
This is what I’ve learned so far about Binary Trees.
Finding data within a binary search tree is typically pretty quick, as well as insertion and deletion.
— — — — — — — — — — — — — — — — — —
A binary search tree is a tree data structure which is composed of nodes.
These nodes contain data as well as references to their children nodes
— — — — — — — — — — — — — — — — — — -
What is a Tree?
· A data structure made up of linked nodes.
· One node can link to any number of children.
· We will mainly be using binary trees and binary search trees.
— — — — — — — — — — — — — — — — — — -
What is a Binary Tree?
· A binary tree is a specific category of trees.
· A binary tree node can point to 2 child nodes at most.
· Properties:
o Non-linear
o Hierarchical
o Acyclic
o Recursive
· A tree with n nodes will always have n-1 edges.
· A binary search tree (BST) is a type of binary tree.
· A valid BST is defined as follows:
o The left subtree of a node contains only nodes with values less than the node’s values.
o The right subtree of a node contains only nodes with values greater than the node’s values.
o Both the left and right subtrees must also be binary search trees.
— — — — — — — — — — — — — — — — — — -
BINARY SEARCH TREES PROPERTIES
1. Each node within a tree can have, at most, two children.
a. you can have:
i. a left and right child
ii. only a left child
iii. only a right child
iv. no children at all
2. Left child must always be less than its parent.
a. By having the left child less than the parent, the guarantees that the left sub-tree will only contain data that is less than the parent.
3. Right child must always be greater than its parent.
a. By having the right child greater than the parent, the guarantees that the right sub-tree will only contain data that is greater than the parent.
4. Every Sub-tree within a Binary Search Tree, is itself, its own binary search tree.
a. This implies that since every child must be either less than or greater than its parent so that there can be no duplicates within the tree.
5. No duplicates.
— — — — — — — — — — — — — — — — — — -
a valid example of a binary search tree
_______50_______
/ \
__25__ __75__
/ \ / \
15 35 65 85
/ \ / \ / \ / \
none none|none none|none none|none none
— — — — — — — — — — — — — — — — — — -
a valid example of a binary search tree
_______50_______
/ \
__10__ __75_
/ \ / \
5 none 65 85
\
70
— — — — — — — — — — — — — — — — — — -
a valid example of a binary search tree
50
\
75
\
85
— — — — — — — — — — — — — — — — — — -
an invalid example of a binary search tree
_______50_______
/ \
__25__ __75_
/ \ / \
75 35 65 85
/ \ / \ / \ / \
none none|none none|none none|none none
this tree is an invalid example of a binary search tree because the left child of 25, which is 75, is greater than its parent, which is 25.
— — — — — — — — — — — — — — — — — — -
_______50_______
/ | \
25 65 75
this is an invalid example of a binary search tree because parent node 50 has three children of 25, 65, 75.
A parent node in a binary search tree can only have two children.
— — — — — — — — — — — — — — — — — — -
BINARY SEARCH TRES: DOWNFALLS
A balanced binary search tree is a tree where the sibling sub-trees do not differ in height by more than one level.
The following is considered a balanced tree:
_______50_______
/ \
__25__ __75_
/ \ / \
15 35 65 85
/ \ / \ / \ / \
10 18 27 40 60 70 83 98
The following is considered a unbalanced tree:
An unbalanced tree like this can be considered a linked list.
Look up times can be comparable to linked lists, if the tree is skewed.
50
/ \
none _75_
/ \
none 85
\
95
Typically, this is not an issue when inserting random data but if you want to insert data that is sorted, then you would end up with an unbalanced tree.
It might be a better idea to use a linear data structure, like an array or a linked list.
— — — — — — — — — — — — — — — — — — -
BINARY SEARCH TREES: CONSTRUCTORS
Need to define two classes:
1. node
2. BST
class Node {
constructor(data){
this.left = null;
this.right = null;
this.data = data;
// this.data is set to the data that is being passed in.
}
}
class BST{
constructor(){
this.root = null;
// this.root is set to null because the tree is initially empty.
}
}
I will continue learning about Binary Trees for the next couple of posts.
