Posts

AVL Tree And B Tree

Image
AVL Tree An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. ~  Height of a node: -The height of an empty subtree is 0. -The height of a leaf is 1. -The height of an internal node is the maximum height of its children plus 1. ~ Balance factor: -The difference height of its LEFT subtree and its RIGHT subtree . The balance factor of all nodes in AVL tree should be at most 1. AVL Tree Example Right Rotation Left Rotation AVL Insertion Process If there is an imbalance in left child of right subtree, then you perform a left-right rotation. If there is an imbalance in left child of left subtree, then you perform a right rotation. If there is an imbalance in right child of right subtree, then you perform a left rotation. If there is an imbalance in right chi...
Post a Comment
Read more

Rangkuman Before UTS

Image
Linked List Linked List Definition A linked list is a dynamic data structure where a  node  is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a  head  and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front. A Simple Linked List Circular Single Linked list In Circular Single Linked List, last node contains a pointer to the first node, We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list Implementation Insertion A node can be added in three ways: Insertion in an empty list Insertion at the beginning of the li...
Post a Comment
Read more

Binary Search Tree

Binary Search Tree Definition Binary search tree (BST), also known as sorted binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.The BST data structure is the basis for a number of highly efficient sorting and searching algorithms, and it can be used to construct more abstract data structures including sets, multisets, and associative arrays. BST Rules For a node x in of a BST T, –the left subtree of x contains elements that are smaller than those stored in x, –the right subtree of x contains all elements that are greater than those stored in x, Binary Search Tree Operations Search() : find key in the BST  Whenever an element is to be searched, start searching from the root node. Then if th...
Post a Comment
Read more

Stack And Queue

Image
Stack And Queue Stack Stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.  The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations. There are basically three operations that can be performed on stacks. They are inserting an item into a stack (push), deleting an item from the stack, and displaying the contents of the stack. Array Representation •Stack has two variables: -TOP which is used to store the address of the topmost element of the stack. -MAX which is used to store the maximum number of elements that the stack can hold. -If TOP = NULL, then indicates that the stack is empty. -If TOP = MAX – 1, then the stack is full. Linked List Representati...
Post a Comment
Read more