Friday, November 18, 2016

Trees

This might sound like it's an article not related to computer science,but in computer science trees refer to an advanced data structure concept that's very useful for ordered collections and the way we represent them in coding.

What's a tree ?

Wikipedia defines a tree as a widely used abstract type(ADT) can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

What are some properties of a theoretical tree?

Much similar to plants, data structures trees have some properties that specify them.Some of these properties are:
1-Height :the length of its longest path or the deepest depth 
2-Depth:the length of its root path
3-Path length:the sum of the depths of all nodes
4-Width:the size of the largest level 

How's that connected to programming ? What's a binary tree?

It's an ordered tree in which every internal node has two distinguished subtrees.
Binary trees are more important than general trees or unordered trees because they have a pattern that works with the machine language(0s and 1s),so that's what makes a binary tree one of the most widely used internal data structures in computing 



Some applications of binary trees ?

1-Binary search trees :a binary tree in which for each key in the tree, all the keys in its left subtree are less than it and all the keys in its rights subtrees are greater than it.
2-Fibonacci tress:built on the same structure of the Fibonacci numbers that we took earlier in the semester 

3-AVL trees :a binary search tree that maintains its balance by forcing the two subtrees at any node to have nearly the same height.This is done by rotating subtrees whenever an imbalance occurs through an algorithm

References:
1-https://en.wikipedia.org/wiki/Tree_(data_structure)
2-https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/220px-Binary_tree.svg.png
3-https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/binaryTree.bmp
4-https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Fibonacci_Tree_5.svg/372px-Fibonacci_Tree_5.svg.png
5-https://www.cs.auckland.ac.nz/software/AlgAnim/fig/AVL1a.gif







No comments:

Post a Comment