Red Black Tree vs AVL Tree vs B-Tree

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

B-tree when you’re managing more than thousands of items and you’re paging them from a disk or some slow storage medium. RB tree when you’re doing fairly frequent inserts, deletes and retrievals on the tree. AVL tree when your inserts and deletes are infrequent relative to your retrievals. think B+ trees are a good general-purpose ordered container data structure, even in main memory. Even when virtual memory isn’t an issue, cache-friendliness often is, and B+ trees are particularly good for sequential access - the same asymptotic performance as a linked list, but with cache-friendliness close to a simple array. [Read More]
kodeknight  red-black-tree  RBT  balanced trees  incomplete  avl 

AVL Tree Index

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

hell-o, im carloe distor, from the most beautiful … Anonymous - Mar 3, 2014hell-o, im carloe distor, from the most beautiful province in benguet, baguio city, i would like to ask if you can do me a favor, because im so tired in doing my homework , IN BINARY TREE (ARRAY REPRESENTATION), INFIXTOPOSTFIX USING STACK AND AVL , THANK YOU, Hi , I don’t think I will be able to help much. [Read More]
tree  kodeknight  balanced trees  avl 

AVL Tree : Rotations

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A tree rotation can be an imtimidating concept at first. You end up in a situation where you’re juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what’s going on with any of the subtrees which are attached to the nodes you’re fumbling with, but that can be hard. Left Rotation (LL) or Single Left rotation [Read More]
tree  kodeknight  balanced trees  avl 

AVL Trees : Inserting a new Item

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Initially, a new item is inserted just as in a binary search tree. Note that the item always goes into a new leaf. The tree is then readjusted as needed in order to maintain it as an AVL tree. There are three main cases to consider when inserting a new node. Case 1: New Node added to (BF = 0) Node A node with balance factor 0 changes to +1 or -1 when a new node is inserted below it. [Read More]
tree  kodeknight  balanced trees  avl 

Balanced Search tree

 Posted on September 10, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Definition A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height. Motivation behind Balanced Search tree Properties of sorted array Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it? Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. [Read More]
search  theory  tree  Binary Tree  BT  kodeknight  red-black-tree  RBT  balanced trees  time complexity  binary search  avl 

AVL tree : Introduction

 Posted on September 7, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Introduction AVL Tree is a kind of binary search tree. Different from binary search tree is, it is self-balanced. The heights of two child subtress of node differ by at most one. Because of this, another name of AVL Tree is height-balanced. These are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has Theta(lg n) height and hence Theta(lg n) worst case lookup and insertion times. [Read More]
tree  kodeknight  balanced trees  avl