Materi Pertemuan 6 Data Structure TREE & BINARY TREE

MATERI PERTEMUAN 6

Tree & Binary Tree

Binary tree

A binary tree is a tree in which no node can have more than two children.

Each node has an element, a reference to a left child and a reference to a right child.

Type of Binary Tree

·       PERFECT binary tree is a binary tree in which every level are at the same depth.

·       COMPLETE binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.

·       SKEWED binary tree is a binary tree in which each node has at most one child.

·       BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Notes: materi lebih lengkap dapat di lihat di upload sebelumnya J

Binary Search tree

           A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

·      The left sub-tree of a node has a key less than or equal to its parent node's key.

·      The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

Basic Operations

Following are the basic operations of a tree −

·      Search − Searches an element in a tree.

·      Insert − Inserts an element in a tree.

·      Pre-order Traversal − Traverses a tree in a pre-order manner.

·      In-order Traversal − Traverses a tree in an in-order manner.

·      Post-order Traversal − Traverses a tree in a post-order manner.

Contoh : Terdapat data yaitu (27,14,10,19,35,31,42) dan 27 didefinisikan sebagai akar maka tree akan menjadi seperti gambar dibawah ini :

  

Untuk penjelasan insert dan delete pada binary search tree lanjut dapat dilihat dilink berikut ini:

https://www.youtube.com/watch?v=wcIRPqTR3Kc

notes : jika yang didelete adalah leaf maka node tersebut langsung hilang, jika bukan maka node tersebut akan digantikan

·       Jika node tersebut disebelah kiri maka akan digantikkan oleh anaknya yang paling besar.

·       Jika node tersebut disebelah kanan maka akan digantikkan oleh anaknya yang paling kecil.