AVL Trees

-

AVL Trees
===============
- Also called height balanced tree
-Height of children present at same level may not have same height. There height can differ at most by 1.
-The height of an AVL tree T storing n keys is O(log n)

Structure of AVL Tree
========================
- Consoder an AVL tree of n nodes
-Cosider a leaf which is closest to the root
- Suppose this leaf is at level k.
-Then height of a tree is at most 2k - 1.




Summary of AVL Tree
==========================
- If height is h , then leaf closest to root is at level  at least (h+1)/2
-On the first (h-1)/2 levels the AVL tree is a complete binary tree
- After (h-1)/2 level the AVL tree may start "thinning out"
-Number of nodes in AVL tree is at least 2 to raise (h-1)/2 and at most 2 raise to h

Insertion in AVL Tree
==========================
Insertion of node make tree changes height and hence height balance property voilated.

If Insertion causes T to become unbalanced , we travel up the tree from the newly created node until we find first node x such that its grandparent z is unbalanced node.(IMP)

-Rotation if performed to make balanced
even after rotation height of tree remains same
-Middle node becomes root after rotation



Deletion
=============================
-Let w be a node to be deleted
-Let z be the firt unbalanced node encountered while travelling up the  tree from w . Also let x be the child of y with a larger height .
-We perform rotation to restore balance at subtree rooted at z
-As this restructring may upset the balance of another node heigher in the tree , we must continue checking for balance until the root of T is reached.



Comments

Post a Comment

Popular posts from this blog

JDBC Hive Connection fails : Unable to read HiveServer2 uri from ZooKeeper

-
Image
I have been struggling from couple of days to get my jdbc hive connection working using Zookeeper URI and after putting lot of effort finally I realised problem. In this post I will sharing my experience  and steps I took to rectify problem. Notes : I am having a HDP 2.6 sandbox along with my JDBC program . Use case : Many companies does not provide HiveServer2 url for configuring your JDBC string and its important because if your hiveserver goes down  , your whole job will abort (You will be missing Hive HA capabilities). So How do I dynamically determine second Hive Server URI ? Solution is to use Zookeeper Service Discovery feature. Zookeepers keeps all HiveServer 2 URI into its namespace. When client tries to make a connection to Hive , Zookeeper will look for available hive server and return URL to client program. You can quickly verify HiveServer namespace in zk Path with below command on HDP.  /usr/hdp/current/zookeeper-client/bin/zookeeper-client...
Read more

Access Kubernetes ConfigMap in Spring Boot Application

-
Image
 Hello There, Welcome back to our new post on Kubernetes tutorials. In this example we will see how can we configure and access ConfigMap in Spring boot application. ConfigMaps are helpful where you have multiple environment (Dev,Test Prod etc) and you want to promote your container with different environment configuration. There are three ways Pods can access ConfigMap in containers. For todays Demo , we will use Environment Variable approach. Pre-requisite : MiniKube Cluster   For Demo Purpose I have created Spring Boot application which will expose below end point.  curl localhost:8080/configMap Docker Image : shashivish123/springboot  Below is how Controller class looks like and value is being autowired from application.properties. Remember CONFIG_KEY value will be coming from Kubernetes ConfigMap Environment Configuration. Now Let's Begin , We will start by Creating firs ConfigMap in Kubernetes. Step 1: Create a namespace where we will ...
Read more

Developing Custom Processor in Apache Nifi

-
Image
Apache Nifi was developed to automate the flow of data between different systems. Apache NiFi is based on technology previously called “Niagara Files” that was in development and used at scale within the NSA for the last 8 years and was made available to the Apache Software Foundation through the NSA Technology Transfer Program. Nifi is based on FlowFiles which are heart of it. A FlowFile is a data record, which consists of a pointer to its content (payload) and attributes to support the content, that is associated with one or more provenance events. The attributes are key/value pairs that act as the metadata for the FlowFile, such as the FlowFile filename. The content is the actual data or the payload of the file. Provenance is a record of what’s happened to the FlowFile. Each one of these parts has its own repository (repo) for storage. Each flowfile is processed by FlowFile processor . Processors have access to attributes of a given FlowFile and its content stream. Processo...
Read more