Intro To Trees
What is a tree?
In programming, a tree is a data structure. Trees are used to represent hierarchical data, rather linear data.
Here is an image of what a tree might look like:
Where would we use a tree data structure?
One of the places where a tree is used where you might not realize is in HTML. The DOM is actually a tree data structure.
Another place where a tree is used is your file system.
Why use trees over arrays or other data structures?
Given a tree of keys, there are some types of trees that allow us to access a given key faster than a linked list, but slower than an array.
We can insert/delete keys faster than arrays but slower than unordered linked lists.
Common uses of trees include helping us search for information easier and manipulating sorted lists of data.
Tree Terminology
There are terms that you would need to know when talking about trees.
Root Node: The root is the first node in the tree.
Parent Node: A node with other nodes connected below it
Child Node: A node that is connected to a node above it
External Node: An external node(leaf node)is any node that does not have child nodes
Internal Node: An internal node is any node that has a child node
Depth: The depth of a node is the number of edges from the root to the node
Height: The height of a tree is the max number of edges or paths from the root node to a leaf node. The height of a node is longest path from the node to a leaf node.
On top of new terminology for trees, there are also various types of trees that can be implemented.
Binary Search Trees
A binary search tree has the following properties:
-Each node can have at most 2 children
-A key in any node is greater than any keys in that node’s left subtree
-A key in any node is less than any keys in that node’s right subtree
Binary trees are used for efficient sorting and searching
AVL Trees
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
Red-Black Trees
A red-black tree is also a self-balancing binary tree. In a red-black tree, the nodes have an extra bit that represents the color of the node. The bit is used to balance out the tree during insertions/deletions. A red-black tree has these properties:
-Every node is either red or black.
-Every leaf (NULL) is black.
-If a node is red, then both its children are black.
-Every simple path from a node to a descendant leaf contains the same number of black nodes.
Here is a link that shows how red-black trees work:
In summary, trees are an important data structure in programming. Like any data structure, there are tradeoffs for using a certain data structure over another. Hopefully, I helped you learn about a new data structure or reinforced your knowledge of trees.
