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)

_Tree Data Structure_

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.

1
2
3
4
5
6
public class TNode {
private Object data;
private MyLinkedList siblings;
private TNode myLeftChild;
public TNode(Object n){data=n; siblings=NULL;myLeftChild=NULL;}
}

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 binary tree

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.

_Operations on Binary Search Tree’s_

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

Inserting a node

1
2
3
Insert(N, T) = N   if T is empty
= insert(N, T.left) if N < T
= insert(N, T.right) if N > T

Searching for a node

Similar with Insert

1
2
3
4
Search(N, T) =  false   if T is empty
= true if T = N
= search(N, T.left) if N < T
= search(N, T.right) if N > T

Deleting a node

  • _Operations on Binary Search Tree’s_
  • _Advanced BST Operations_

  • 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

_Advanced BST Operations_

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

In-Order example

1
2
3
4
5
6
7
private void inorder(Node root){
if (root != null) {
inorder(root.leftChild);
// visit root;
inorder(root.rightChild);
}
}

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.

(BST)Splay Trees

Reference

Author: VINCEC

Permalink: https://vince-amazing/blog/2019/06/08/tree-review/

Date: June 8th 2019, 10:27:24

Copyright license: The article usingCC licensing 4.0

CATALOG
  1. 1. A General Tree
  2. 2. Binary Trees
    1. 2.1. Full binary tree.
    2. 2.2. Complete binary tree
    3. 2.3. Binary Search Trees
      1. 2.3.1. BST OPERATIONS
        1. 2.3.1.1. Inserting a node
        2. 2.3.1.2. Searching for a node
        3. 2.3.1.3. Deleting a node
    4. 2.4. (BST)Traversing Trees
      1. 2.4.1. Depth First Traversals:
        1. 2.4.1.1. In-Order example
      2. 2.4.2. Breadth First or Level Order Traversal
      3. 2.4.3. Iterator API for Traversing Trees
    5. 2.5. (BST) AVL(Adelson-Velskii and Landis) Tree
    6. 2.6. (BST) Red-black Tree
      1. 2.6.1. Rules
    7. 2.7. (BST)Splay Trees
  3. 3. Reference