Jim and his LAN Party – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Jim and his LAN Party HackerRank Solution
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct UnionFind {
vector<int> data;
void init(int n) { data.assign(n, -1); }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if(x != y) {
if(data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) { return root(x) == root(y); }
int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
int size(int x) { return -data[root(x)]; }
};
int main() {
int N, M, Q;
scanf("%d%d%d", &N, &M, &Q);
vector<int> A(N), cnt(M);
rep(i, N) {
scanf("%d", &A[i]), -- A[i];
++ cnt[A[i]];
}
vector<map<int,int> > a(N);
rep(i, N)
a[i][A[i]] = 1;
vector<int> ans(M, -1);
rep(i, M) if(cnt[i] <= 1)
ans[i] = 0;
UnionFind uf;
uf.init(N);
rep(i, Q) {
int u, v;
scanf("%d%d", &u, &v), -- u, -- v;
int ur = uf.root(u);
int vr = uf.root(v);
if(ur != vr) {
uf.unionSet(ur, vr);
int zr = uf.root(ur);
if(ur != zr && vr != zr) { cerr << "error!" << endl; abort(); }
map<int,int> &za = a[zr], &wa = a[zr == ur ? vr : ur];
if(za.size() < wa.size())
za.swap(wa);
each(j, wa) {
int k = j->first;
if((za[k] += j->second) == cnt[k] && ans[k] == -1)
ans[k] = i + 1;
}
wa.clear();
}
}
rep(i, M)
printf("%d\n", ans[i]);
return 0;
}
Java Jim and his LAN Party HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), m = ni(), Q = ni();
int[] a = na(n);
int[][] gg = makeBuckets(a, m+1);
int s = (int)Math.sqrt(n);
int[][] qs = new int[Q][];
for(int i = 0;i < Q;i++){
qs[i] = new int[]{ni()-1, ni()-1};
}
int[] ret = new int[m+1];
Arrays.fill(ret, -1);
for(int i = 1;i <= m;i++){
if(gg[i].length == 1){
ret[i] = 0;
}
}
DJSet ds = new DJSet(n);
for(int i = 0;i < Q;i+=s){
DJSet xds = new DJSet(ds);
for(int j = i;j < i+s && j < Q;j++){
ds.union(qs[j][0], qs[j][1]);
}
int[] id = new int[m+1];
Arrays.fill(id, -1);
for(int j = 0;j < n;j++){
int v = a[j];
if(id[v] == -1){
id[v] = ds.root(j);
}else if(id[v] >= 0){
if(id[v] != ds.root(j)){
id[v] = -2;
}
}
}
int[] an = new int[m];
int p = 0;
for(int j = 1;j <= m;j++){
if(id[j] >= 0 && ret[j] == -1){
an[p++] = j;
}
}
for(int j = i;j < i+s && j < Q;j++){
xds.union(qs[j][0], qs[j][1]);
inner:
for(int k = 0;k < p;k++){
if(ret[an[k]] == -1){
for(int u : gg[an[k]]){
if(!xds.equiv(u, gg[an[k]][0]))continue inner;
}
ret[an[k]] = j+1;
}
}
}
}
for(int i = 1;i <= m;i++){
out.println(ret[i]);
}
}
public static int[][] makeBuckets(int[] a, int sup)
{
int n = a.length;
int[][] bucket = new int[sup+1][];
int[] bp = new int[sup+1];
for(int i = 0;i < n;i++)bp[a[i]]++;
for(int i = 0;i <= sup;i++)bucket[i] = new int[bp[i]];
for(int i = n-1;i >= 0;i--)bucket[a[i]][--bp[a[i]]] = i;
return bucket;
}
public static class DJSet {
public int[] upper;
public DJSet(int n) {
upper = new int[n];
Arrays.fill(upper, -1);
}
public DJSet(DJSet ds) {
upper = Arrays.copyOf(ds.upper, ds.upper.length);
}
public int root(int x) {
return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
}
public boolean equiv(int x, int y) {
return root(x) == root(y);
}
public boolean union(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (upper[y] < upper[x]) {
int d = x;
x = y;
y = d;
}
upper[x] += upper[y];
upper[y] = x;
}
return x == y;
}
public int count() {
int ct = 0;
for (int u : upper)
if (u < 0)
ct++;
return ct;
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Jim and his LAN Party HackerRank Solution
import sys
class Vertex(object):
def __init__(self, i, c, cc):
self.i = i
self.c = c
self.cc = cc
self.e = []
def merge_cc(cc, v, i, j, res, n, color_counts):
to_rem = j if len(cc[i][1]) > len(cc[j][1]) else i
to_leave = j if to_rem == i else i
cc[to_rem][2] = False
for i in cc[to_rem][1]:
v[i].cc = to_leave
cc[to_leave][1].append(i)
if v[i].c in cc[to_leave][0]:
cc[to_leave][0][v[i].c] += 1
else:
cc[to_leave][0][v[i].c] = 1
if cc[to_leave][0][v[i].c] == color_counts[v[i].c] and res[v[i].c] == -1:
res[v[i].c] = n
cc[to_rem][1] = []
# print("saving result for color %s: %s" % (v[i].c, n))
# print("res: ", res)
# print("colors of merged cc: ", cc[to_leave][0])
n, m, q = (int(x) for x in input().strip().split(' '))
colors = [int(x) for x in input().strip().split(' ')]
vs=[]
comps = {}
for i in range(n):
vs.append(Vertex(i, colors[i], i))
comps[i] = [{colors[i]: 1}, [i], True] # connected component: (all colors, vertextes)
color_counts = {}
for c in colors:
if c in color_counts:
color_counts[c] += 1
else:
color_counts[c] = 1
res = dict((c, -1) for c in set(colors))
for i in color_counts:
if color_counts[i] == 1:
res[i] = 0
for i in range(q):
a, b = (int(x) for x in input().strip().split(' '))
a -= 1
b -= 1
# adding edge
vs[a].e.append(b)
vs[b].e.append(a)
# merge components and update answer
#bfs(vs, color_counts, res)
if vs[a].cc != vs[b].cc:
# print("merging: ", vs[a].cc, vs[b].cc)
merge_cc(comps, vs, vs[a].cc, vs[b].cc, res, i+1, color_counts)
#for i in range(len(vs)):
# print("cc active: ", i, comps[i][2])
for i in sorted(res.keys()):
print(res[i])
Python 2 Jim and his LAN Party HackerRank Solution
import sys
def read():
l = sys.stdin.readline()
if l[-1] == '\n': l = l[:-1]
xs = filter(lambda x: len(x) > 0, l.split(' '))
return map(int, xs)
n, m, q = read()
ps = map(lambda x: x - 1, read())
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
if len(gs[ix]) < 2:
res.append(0)
else:
res.append(-1)
def find(x):
if uf[x][0] == x:
return x
r = find(uf[x][0])
uf[x][0] = r
return r
def union(u, v, ix):
ur = find(u)
vr = find(v)
ur, uh, us = uf[ur]
vr, vh, vs = uf[vr]
if uh > vh:
uf[vr][0] = ur
uf[ur][2] |= vs
for g in vs:
gs[g].discard(vr)
gs[g].add(ur)
if res[g] < 0 and len(gs[g]) == 1:
res[g] = ix + 1
elif vh > uh:
uf[ur][0] = vr
uf[vr][2] |= us
for g in vs:
gs[g].discard(ur)
gs[g].add(vr)
if res[g] < 0 and len(gs[g]) == 1:
res[g] = ix + 1
else:
uf[vr][0] = ur
uf[ur][1] += 1
uf[ur][2] |= vs
for g in vs:
gs[g].discard(vr)
gs[g].add(ur)
if res[g] < 0 and len(gs[g]) == 1:
res[g] = ix + 1
for ix in range(q):
u, v = map(lambda x: x - 1, read())
union(u, v, ix)
for r in res:
print r
C Jim and his LAN Party HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int end_val;
struct _node *left;
struct _node *right;
} node;
typedef struct _tree_node{
enum {red,black} colour;
int data;
struct _tree_node *left,*right,*parent;
} tree_node;
void MM1(int x,int y);
void MM2(int x,int y);
void tra(tree_node *t2,tree_node **t1,int big);
int QQ(int x,int y);
void dfs(node *temp);
int search(tree_node *root,int data);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
int insert(tree_node **root,tree_node *x);
void delete(tree_node **root,tree_node *head,int data);
int p[100000],a[100000],ans[100000],sort_a[100000],q1[100000],q2[100000],game_left[100000],game_right[100000],group_left[100000],c=0,edge;
node *table[100000];
tree_node *tree_table[100000]={0},all_nodes1[100000],all_nodes2[100000];
int main(){
int N,M,Q,i;
node *temp;
scanf("%d%d%d",&N,&M,&Q);
for(i=0;i<N;i++)
scanf("%d",a+i);
for(i=0;i<Q;i++)
scanf("%d%d",q1+i,q2+i);
for(i=0;i<N;i++){
p[i]=i;
temp=(node*)malloc(sizeof(node));
temp->end_val=i;
temp->left=temp->right=NULL;
table[i]=temp;
}
for(i=0;i<M;i++){
game_left[i]=game_right[i]=-1;
all_nodes1[i].data=i;
all_nodes1[i].parent=all_nodes1[i].left=all_nodes1[i].right=NULL;
all_nodes2[i].data=i;
all_nodes2[i].parent=all_nodes2[i].left=all_nodes2[i].right=NULL;
}
for(i=0;i<Q;i++)
if(!QQ(q1[i]-1,q2[i]-1))
MM1(q1[i]-1,q2[i]-1);
for(i=0;i<N;i++)
if(p[i]==i){
temp=table[i];
dfs(temp);
}
for(i=0;i<N;i++){
p[i]=i;
group_left[sort_a[i]]=i;
}
for(i=0;i<N;i++){
if(game_left[a[i]-1]==-1 || group_left[i]<game_left[a[i]-1])
game_left[a[i]-1]=group_left[i];
if(game_right[a[i]-1]==-1 || group_left[i]>game_right[a[i]-1])
game_right[a[i]-1]=group_left[i];
}
for(i=0;i<M;i++)
if(game_left[i]==game_right[i])
ans[i]=0;
else{
ans[i]=-1;
insert(tree_table+sort_a[game_left[i]],all_nodes1+i);
insert(tree_table+sort_a[game_right[i]],all_nodes2+i);
}
for(i=0;i<N;i++)
if(tree_table[i])
sort_a[i]=1;
else
sort_a[i]=0;
for(edge=0;edge<Q;edge++)
if(!QQ(q1[edge]-1,q2[edge]-1))
MM2(q1[edge]-1,q2[edge]-1);
for(i=0;i<M;i++)
printf("%d\n",ans[i]);
return 0;
}
void MM1(int x,int y){
int p1,p2;
node *temp,*t1,*t2;
p1=x;
while(p[p1]!=p1)
p1=p[p1];
while(p[x]!=x){
p2=p[x];
p[x]=p1;
x=p2;
}
t1=table[p1];
p2=y;
while(p[p2]!=p2)
p2=p[p2];
t2=table[p2];
if(p2!=p1){
p[p2]=p1;
temp=(node*)malloc(sizeof(node));
temp->left=t1;
temp->right=t2;
table[p1]=temp;
}
while(p[y]!=y){
p2=p[y];
p[y]=p1;
y=p2;
}
return;
}
void MM2(int x,int y){
int p1,p2,big;
tree_node **t1,*t2;
p1=x;
while(p[p1]!=p1)
p1=p[p1];
while(p[x]!=x){
p2=p[x];
p[x]=p1;
x=p2;
}
p2=y;
while(p[p2]!=p2)
p2=p[p2];
if(p2!=p1){
p[p2]=p1;
t1=(sort_a[p1]>sort_a[p2])?&tree_table[p1]:&tree_table[p2];
t2=(sort_a[p1]>sort_a[p2])?tree_table[p2]:tree_table[p1];
big=(sort_a[p1]>sort_a[p2])?p1:p2;
tra(t2,t1,big);
if(big!=p1){
tree_table[p1]=tree_table[p2];
sort_a[p1]=sort_a[p2];
}
}
while(p[y]!=y){
p2=p[y];
p[y]=p1;
y=p2;
}
return;
}
void tra(tree_node *t2,tree_node **t1,int big){
if(!t2)
return;
tra(t2->left,t1,big);
tra(t2->right,t1,big);
t2->parent=t2->left=t2->right=NULL;
if(insert(t1,t2))
sort_a[big]++;
else{
ans[t2->data]=edge+1;
delete(t1,*t1,t2->data);
sort_a[big]--;
}
return;
}
int QQ(int x,int y){
int p1,p2,ans;
p1=x;
while(p[p1]!=p1)
p1=p[p1];
ans=p1;
while(p[x]!=x){
p2=p[x];
p[x]=p1;
x=p2;
}
p1=y;
while(p[p1]!=p1)
p1=p[p1];
ans=(ans==p1);
while(p[y]!=y){
p2=p[y];
p[y]=p1;
y=p2;
}
return ans;
}
void dfs(node *temp){
if(!temp)
return;
if(temp->left==NULL && temp->right==NULL){
sort_a[c++]=temp->end_val;
return;
}
dfs(temp->left);
dfs(temp->right);
return;
}
int search(tree_node *root,int data){
if(!root)
return 0;
if(root->data==data)
return 1;
if(data<root->data)
return search(root->left,data);
return search(root->right,data);
}
void left_rotate(tree_node **root,tree_node *x){
tree_node *y;
y=x->right;
if(!y) return;
x->right=y->left;
if(y->left)
y->left->parent=x;
y->parent=x->parent;
if(x->parent==NULL) *root=y;
else
if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
return;
}
void right_rotate(tree_node **root,tree_node *y){
tree_node *x;
x=y->left;
if(!x) return;
y->left=x->right;
if(x->right)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==NULL) *root=x;
else
if(y==y->parent->right)
y->parent->right=x;
else
y->parent->left=x;
x->right=y;
y->parent=x;
return;
}
void reconstruct(tree_node **root,tree_node *x){
tree_node *y,*z;
y=x->parent;
z=x->parent->parent;
x->colour=black;
z->colour=red;
x->parent=z->parent;
if(z->parent==NULL)
*root=x;
else if(z==z->parent->left)
z->parent->left=x;
else
z->parent->right=x;
if(z->left==y){
x->left=y;
x->right=z;
}
else{
x->left=z;
x->right=y;
}
y->parent=z->parent=x;
y->left=y->right=z->left=z->right=NULL;
return;
}
int normal_insert(tree_node **root,tree_node *x){
if(*root==NULL)
*root=x;
else if((*root)->data==x->data)
return 0;
else{
x->parent=*root;
if((*root)->data>x->data)
return normal_insert(&((*root)->left),x);
else
return normal_insert(&((*root)->right),x);
}
return 1;
}
int insert(tree_node **root,tree_node *x){
if(!normal_insert(root,x))
return 0;
tree_node *y;
x->colour=red;
while(x!=*root && x->parent->colour==red){
if(x->parent==x->parent->parent->left){
y=x->parent->parent->right;
if(!y)
if(x==x->parent->left){
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->right){
x=x->parent;
left_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
}
else{
y=x->parent->parent->left;
if(!y)
if(x==x->parent->right){
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->left){
x=x->parent;
right_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
}
}
(*root)->colour=black;
return 1;
}
void delete(tree_node **root,tree_node *head,int data){
tree_node *db,*parent,*brother,*child,none;
if(!head)
return;
if(data<head->data){
delete(root,head->left,data);
return;
}
if(data>head->data){
delete(root,head->right,data);
return;
}
if(data==head->data){
if(head->left && head->right){
db=head->right;
while(db->left)
db=db->left;
head->data=db->data;
head=db;
}
if(head->left==NULL && head->right==NULL){
parent=head->parent;
if(!parent){
*root=NULL;
return;
}
brother=(parent->left==head)?parent->right:parent->left;
if(head->colour==red){
if(parent->left==head)
parent->left=NULL;
else
parent->right=NULL;
return;
}
if(parent->left==head)
parent->left=&none;
else
parent->right=&none;
none.parent=parent;
none.colour=black;
db=&none;
}
else{
parent=head->parent;
child=(!head->left)?head->right:head->left;
if(!parent){
*root=child;
child->parent=NULL;
child->colour=black;
return;
}
if(parent->left==head)
parent->left=child;
else
parent->right=child;
child->parent=parent;
db=child;
}
}
while(db){
if(db->colour==red){
db->colour=black;
return;
}
if(db==*root)
return;
parent=db->parent;
brother=(parent->left==db)?parent->right:parent->left;
if(!brother)
db=parent;
else if(brother==parent->right){
if(brother->colour==black && brother->right && brother->right->colour==red){
brother->colour=parent->colour;
brother->right->colour=black;
parent->colour=black;
left_rotate(root,parent);
if(db==&none)
parent->left=NULL;
return;
}
else if(brother->colour==black && brother->left && brother->left->colour==red){
brother->left->colour=parent->colour;
parent->colour=black;
right_rotate(root,brother);
left_rotate(root,parent);
if(db==&none)
parent->left=NULL;
return;
}
else if(brother->colour==black){
brother->colour=red;
if(db==&none)
parent->left=NULL;
db=parent;
}
else{
brother->colour=black;
parent->colour=red;
left_rotate(root,parent);
}
}
else{
if(brother->colour==black && brother->left && brother->left->colour==red){
brother->colour=parent->colour;
brother->left->colour=black;
parent->colour=black;
right_rotate(root,parent);
if(db==&none)
parent->right=NULL;
return;
}
else if(brother->colour==black && brother->right && brother->right->colour==red){
brother->right->colour=parent->colour;
parent->colour=black;
left_rotate(root,brother);
right_rotate(root,parent);
if(db==&none)
parent->right=NULL;
return;
}
else if(brother->colour==black){
brother->colour=red;
if(db==&none)
parent->right=NULL;
db=parent;
}
else{
brother->colour=black;
parent->colour=red;
right_rotate(root,parent);
}
}
}
return;
}
Leave a comment below
