이번 포스팅은 따로 한국어없이 영어로만 작성되었습니다.

Tree

Tree is a nonlinear structure in which each node is capable of having many successor nodes, called children. Trees are useful for representing lots of varied relationships among data items.

Definitions

• Tree: A structure with a unique starting node (root), in which each node is capable of having multiple successor nodes (its children), and in which a unique path exists from the root to every other node.
• Root: The top node of a tree structure; a node with no parent.
• Parent node: The predecessor node of a node is its parent.
• Subtree: A node and all of its descendants form a subtree rooted at the node.

  

Require

A tree's subtrees must be disjoint. There is a unique path from the root of a tree to any other node of the tree. Every child has only one parent.

More Definitions

• Ancestor: A parent of a node, or a parent of an ancestor.
• Descendant: A child of a node, or a child of a descendant.
• Leaf: A node that has no children.
• Interior node: A node that is not a leaf.
• Siblings: Nodes with the same parent.
• Level: The level of a node is its distance from the root (the number of connections between itself and the root).
• Height: The maximum level of the tree.

Example

• The ancestors of P are H, X and A.
• The descendant of X are H, Q, Z and P.
• The leaf nodes are C, T, F, P, Q and Z.
• The interior nodes are A, B, and X.
• The siblings of B are F and X.

• The height of this tree is 3.

Traversal

Breadth-First Traversal

Also called "level-order traversal"
Using Queue

Depth-First Traversal

Using Stack

Binary Search Trees

• Binary Tree: A tree in which each node is capable of having two child nodes, a left child node and a right child node.

A binary tree in which the key value in any node.

• is greater than or equal to the key value in its left child and any of its descendants (the nodes in the left subtree).
• is less than the key value in its right child and any of its descendants (the nodes in the right subtree).

Feature

1. Each node contains a distinct data value.
2. The key values in the tree can be compared using "greater than" and "less than".
3. The key value of each node in the tree is less than every key value in its right subtree, and greater than every key value in its left subtree.

Traversals

Preorder traversal

1. Root
2. Left subtree
3. Right subtree
   P→F→B→H→G→S→R→Y→T→W→Z

   

Inorder traversal

1. Left subtree
2. Root
3. Right subtree
   B→F→G→H→P→R→S→T→W→Y→Z

   

Postorder traversal

1. Left subtree
2. Right subtree
3. Root
   B→G→H→F→R→W→T→Z→Y→S→P

   

Implementation

BST Node

Constructors

Observers

Transformers

Add

A new node is always inserted into its appropriate position in the tree as a leaf.
If a new node is smaller than a root node, add the new node on the left of the root node. If it is greater than the root node, add it on the right of the root node.

Remove

Must ensure when remove an element maintain the binary search tree property.

• Removing a leaf
  Removing a leaf is simply a matter of setting the appropriate link of its parent to null.

• Removing a node with only one child
  Make the reference from the parent skip over the removed node and point instead to the child of the node we intend to remove.

• Removing a node with two children
  Replaces the node's info with the info from another node in the tree so that the search property is retained - then remove this other node.

Performance

• A Binary search tree is an appropriate structure for many of the same applications discussed previously in conjunction with sorted lists.
• There is a space cost - the binary search tree, with its extra reference in each node, takes up more memory space than a singly linked list.
• Similar to a sorted array-based list, it can be searched quickly, using a binary search.
• Similar to a linked list, it allows insertions and removals without having to move large amounts of data.

Big-O

Compare BST to Linear LIsts

Binary Tree and its Array Representation

To implement the algorithms that manipulate the tree, must be able to find the left and right child of a node in the tree.

• tree.nodes[index] left child is in tree.nodes[index * 2 + 1].
• tree.nodes[index] right child is in tree.nodes[index * 2 + 2].

Also, can determine the location of its parent node

• tree.nodes[index]'s parent is in tree.nodes[(index - 1) / 2].

If the tree is complete, this representation works best, space wise.

Full Binary Tree

A binary tree in which all of the leaves are on the same level and every non-leaf node has two children.

Complete Binary Tree

A binary tree that is either full or full through the next-to-last level, with the leaves on the last level as far to the left as possible.

The complete binary tree with 'k' height has maximum 2^(k+1) - 1 nodes.
In the other words, the complete binary tree which saves 'n' nodes has log(n) height.

Reference

• CS401-Data Structure. (2021). Micheal Y. Choi, Ph.D. Illinois Institute of Technology.
• Full Binary Tree. (2019). Image. Retrieved February 15, 2022, from https://soldonii.tistory.com/75.
• Complete Binary Tree. (2018). Image. Retrieved February 15, 2022, from https://medium.com/jiwon-bae/data-structure-binary-tree-f6fe881b0554.

https://github.com/namdarine/DataStructure.git
Full code is in "BST" package in this repository.