Trees#
To download the demo code for this lecture, run:
$ dmget wb-trees --demo
Introduction#
Goals#
Introduce terminology
Create a tree class and methods
Learn uses for trees
What Is a Tree?#
A computer science tree is similar to an upside-down version of trees that exist in nature.
Terminology#
node: basic unit
children: nodes directly below a node
descendants: nodes directly below a node
parent: node directly above a node
ancestor: node that is above a node
root node: node at the top of tree
leaf node: node without any children
An Org Chart Is A Tree#
A Filesystem Is A Tree#
HTML DOM Is A Tree#
A Taxonomy Is A Tree#
Trees in JavaScript#
The Node Class#
class Node {
constructor(data, children=[]) {
this.data = data;
this.children = children;
}
}
const rachna = new Node("Rachna");
const morgan = new Node("Morgan", [rachna]);
console.log(morgan.children);
// Node {data: 'Rachna'}
morgan.children.push(new Node("Taylor"));
console.log(morgan.children);
// [Node {data: 'Rachna'}, Node {data: 'Taylor'}]
Finding a Node#
Starting at Morgan, find Riley:
Depth First Search#
class Node {
find(data) {
let toVisit = [this];
while (toVisit.length > 0) {
let current = toVisit.pop();
if (current.data === data) {
return current;
}
toVisit = toVisit.concat(current.children);
}
}
current toVisit ------ [+morgan] morgan [+taylor, +zuza, +rachna] rachna [taylor, zuza, +mien] mien [taylor, zuza, +isi] isi [taylor, zuza] zuza [taylor, +dawa, +riley] riley
List starts off as
[morgan]Not Riley, so add Morgan’s children:
[taylor, zuza, rachna]Pop Rachna, not Riley, so add Rachna’s child:
[taylor, zuza, mien]Pop Mien, not Riley, add Mien’s children:
[taylor, zuza, isi]Pop Isi, not Riley, no children, so down to:
[taylor, zuza]Pop Zuza, not Riley, add Zuza’s children:
[taylor, dawa, riley]Pop Riley. We found Riley!
This type of search is called a “depth-first search” (DFS) –– we search the children of the current node before the next sibling of the current node (and the children of those children first, etc). We get this feature of being a DFS by using a stack for toVisit –– do you see why it’s a stack?
Runtime: Depth First Search#
Depth First Search uses a stack.
In the worst case, we have to visit every node
So the runtime of Depth First Search is O(n).
Highest-Ranking Riley#
Say there was another Riley in the organization.
Find the highest ranking Riley in the org chart:
Breadth First Search#
class Node {
find(data) {
let toVisit = [this];
while (toVisit.length > 0) {
let current = toVisit.shift(); // removes 1st item
if (current.data === data) {
return current;
}
toVisit = toVisit.concat(current.children);
}
}
current toVisit ------ [+morgan] morgan [+taylor, +zuza, +rachna] taylor [zuza, rachna, +kyo] zuza [rachna, kyo, +dawa, +riley] rachna [kyo, dawa, riley, +mien] kyo [dawa, riley, mien, +riley] zuza [riley, mien, riley, +seamus, +harlow] riley
List starts off as
[morgan]Not Riley, so add Morgan’s children:
[taylor, zuza, rachna]Pop Taylor, not Riley, so add Taylor’s child:
[zuza, rachna, kyo]Pop Zuza, not Riley, so add Zuza’s children:
[rachna, kyo, dawa, riley]Pop Rachna, not Riley, so add Rachna’s child:
[kyo, dawa, riley, mien]Pop Kyo, not Riley, so add Kyo’s child:
[dawa, riley, mien, riley]Pop Dawa, not Riley, so add Dawa’s children:
[riley, mien, riley, seamus, harlow]Pop Riley. We found Riley!
Simply by changing pop() to shift() (remove the first item from the list, rather than the last), we’ve made this into a “Breadth First Search” (BFS). This makes toVisit a queue (rather a stack, like before). Do you see why it’s a queue?
Runtime: Breadth First Search#
Breadth First Search uses a queue
We still have to visit every node in the worst case
But remember, removing from the beginning of an array is slow!
Runtime: O(n) for visiting every node × O(n) for popping from the beginning = \(O(n^2)\)
Runtime can be improved to O(n) by using a linked list instead of an array.
Tree Class#
A Tree class would just keep track of the root node:
class Tree {
constructor(root) {
this.root = root;
}
}
const tree = new Tree(new Node('Morgan'));
console.log(tree); // Tree {root: Node {data: 'Morgan'} }
To implement find in a Tree class, just call the find method on the root node:
class Tree {
findInTree(data) {
return this.root.find(data);
}
}
Linked Lists and Trees#
Every linked list is a tree.
But not every tree is a linked list.
Binary Search Trees#
A Binary Search Tree#
Also a tree, made of nodes
Each node has max 2 children, a left child and a right child
Nodes are ordered according to a rule
Binary Search Tree Nodes#
class BinarySearchNode {
constructor(data, left=null, right=null) {
this.data = data;
this.left = left;
this.right = right;
}
}
Binary Search Tree Find#
class BinarySearchNode {
find(dataToFind) {
let current = this;
while (current !== null) {
if (current.data === dataToFind) {
return current;
}
else if (dataToFind < current.data) {
current = current.left;
}
else {
current = current.right;
}
}
}
Find C: E → left to B → right to D → left to null
Every choice we make reduces # options by half!
What’s the runtime of searching a BST?
For n nodes in the tree, we need to search at most log2n nodes.
So the runtime is O(log n)!
We can search >1,000 nodes in only 10 steps!
We can search >1,000,000 nodes in only 20 steps!
Badly Balanced Binary Trees#
Can find A efficiently
Can find missing C efficiently
Can’t find G efficiently
Tree needs to be “balanced”
Advanced Ideas#
Can’t Move Up#
const isi = orgChart.find('isi');
isi.findParent(); // not possible!
Some Trees Point Both Ways#
class BidirectionalNode {
constructor(data, parent, children=[]) {
this.data = data;
this.parent = parent;
this.children = children;
}
}
You Can Store Trees In Databases#
Object/graph databases can store directly
Different options to model in relational databases
A good overview of options: http://www.sitepoint.com/hierarchical-data-database/
Coming Up#
Recursion!
“Each node is like a tree, itself”
Lots of whiteboard questions & challenges