Binary Search Tree

Binary Search Tree is a binary tree based on nodes that has a certain attribute such as


  • that the left node is smaller than its parents' node
  • that the right node will always be bigger than its parents' node
  • that both nodes must also be binary search tree and therefore cannot contains duplicates

Above is an example of a Binary Search Tree

Binary search tree can perform several operations such as:
  • Searching, By comparing its roots to its nodes a program can climb through the node of a Binary search tree and find a specific node. by checking each root, comparing it to what it searched for climbing down to find the right node.
    • sample code for searching in BST
  • insertion, an operation to input certain data unto the Binary search tree on a specific node in the tree. by creating a space pushing the node and creating a new node either in the middle, the end or the beginning. 
    • sample code of insertion in BST
  • Deletion, an Operation that removes a node from the binary search tree and refills that certain location with a corresponding node
    • sample code of deletion in BST
  • Traversal, an operation to display the nodes of the binary search tree in several ways such as inorder, postorder and pre-order
    • sample code of traversal in BST









Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree & B-Tree

Gambar
AVL Tree  AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where {\displaystyle n}n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. AVL tree was made to simplify BST to make data gathering of one(AVL) easier than the other(BST) due to AVL nature to always having itself balanced. The AVL Tree is considered balanced if the total height of the right child subtracted by the total height of the right child is either 1,0, or -1 . AVL Rotation To balance itself, an AVL tree may perform the following four kinds of rotations − Left rotation Right rotation Left-Right rotation Right-Left rotation The first two rotations are single rotations and the next two rotations
Baca selengkapnya

Summary

SUMMARY Linked-list single Linked List is a data structure consisting of nodes. which together form a sequence. In its most basic form, each node contains data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to the pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists. Stack: In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the
Baca selengkapnya