Vincec's Dimension

# Tree Review

Word count: 1,028 / Reading time: 6 min
2019/06/08 Share

A ‘tree’ is a widely used abstract data type (ADT)

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees. A tree has following general properties:

• One node is distinguished as a root;
• Every node (exclude a root) is connected by a directed edge from exactly one other node; A direction is: parent -> children

Each node can have arbitrary number of children. Nodes with no children are called leaves, or external nodes. Nodes, which are not leaves, are called internal nodes. Internal nodes have at least one child.

Nodes with the same parent are called siblings.
The depth of a node is the number of edges from the root to the node.
The height of a node is the number of edges from the node to the deepest leaf. The height of a tree is a height of a root.

# A General Tree

A tree where each node may have zero or more children.

# Binary Trees

A binary tree is a specialized case of a general tree. A tree where each node can have no more than two children

## Full binary tree.

Each node has exactly zero or two children

Complete filled

## Binary Search Trees

Given a binary tree, have an ordered sequence for recursively visit each node. A “balanced” binary search tree can be searched in O(log n) time. Using In-Order traversal will get a sorted sequence.

A BST is a binary tree of nodes ordered in the following way:

• Each node contains one key (also unique)
• The keys in the left subtree are < (less) than the key in its parent node
• The keys in the right subtree > (greater) than the key in its parent node
• Duplicate node keys are not allowed.

A binary search tree(BST) with this worst-case structure(inserting an ordered) is no more efficient than a regular linked list. Need to be as balanced as possible.

### BST OPERATIONS

#### Searching for a node

Similar with Insert

#### Deleting a node

• _Operations on Binary Search Tree’s_
• Case 1 : The node to delete is a leaf node, just delete

• Case 2 : The node to delete is a node with one child.
• If node be deleted is a left child of the parent. Connect the leaf with left pointer with the parent
• If node be deleted is a right child of the parent. Connect the leaf with right pointer with the parent
• (node.left != null, make a parent node point to a left child;) and vice versa
• Case 3: The node to delete is a node with two children
• we find the largest node in the left sub tree (15) or smallest node in the right sub tree (45) and replace the root with that node
• Do Case 1 or Case 2 with replaced node.

## (BST)Traversing Trees

### Depth First Traversals:

• In-Order, 中序遍历 (Left, Root, Right) : 4 2 5 1 3, Inorder traversal is always symmetrical, 对称的.
• Pre-Order, 前序遍历 (Root, Left, Right) : 1 2 4 5 3
• Post-Order, 后序遍历 (Left, Right, Root) : 4 5 2 3 1

### Breadth First or Level Order Traversal

Level Order Traversal : 1 2 3 4 5

We can implement the level-order traversal using the API’s LinkedList class.

### Iterator API for Traversing Trees

• boolean `hasNext()` - Returns true if the iteration has more elements.
• Object `next()` - Returns the next element in the iteration.
• void `remove()` - (optional operation) Removes from the underlying collection the last element returned by next().

## (BST) AVL(Adelson-Velskii and Landis) Tree

AVL Tree | Set 1 (Insertion)

Differences between heights of any left and right subtrees for every node is less than or equal to 1.

For remains O(Logn) and keep the BST be as balanced as possible. Make sure the height of the tree remains O(Logn) after every insertion and deletion. So keep rotate until reach AVL tree or maintain an “almost” balanced tree.

No longer used in practice

## (BST) Red-black Tree

### Rules

• Red or Black
• When Tree is modified, new tree is subsequently rearranged and repainted.
• It requires 1 bit of color information for each node in tree.

Maintained by Red Black Tree:

• Root is always black.
• All 树尾端(NIL) NULL leaves are black, both children of red node are black.
• Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点.
• Path form root to farthest leaf is no more than twice as long as path from root to nearest leaf.

Author: VINCEC