In this HackerRank Travel in HackerLand problem solution, You will be given q queries. Each query takes the form of 3 space-separated integers, x, y, and k, denoting the respective values for starting city, destination city, and a minimum number of unique buildings that David wants to see along the way. For each query, you must print the minimum crowd value for a path between x and y that has at least k different buildings along the route. If there is no such path, print -1.
Problem solution in Python.
from collections import defaultdict
import heapq
def root(ids, i):
while ids[i] != i:
ids[i] = ids[ids[i]]
i = ids[i]
return i
def union(queries, blds, ids, p, q):
i = root(ids, p)
j = root(ids, q)
if i == j:
return i, j
if len(blds[i]) > len(blds[j]):
bigb, smb = blds[i], blds[j]
else:
bigb, smb = blds[j], blds[i]
for b in smb:
bigb.add(b)
del smb
if len(queries[i][0]) + len(queries[i][1]) > len(queries[j][0]) + len(queries[j][1]):
ids[j] = i
blds[i] = bigb
blds[j] = None
return j, i
else:
ids[i] = j
blds[j] = bigb
blds[i] = None
return i, j
n, m, q = map(int, input().split())
T = list(map(int, input().split()))
edges = []
for i in range(m):
x, y, u = map(int, input().split())
edges.append((u, x-1, y-1))
edges.sort()
queries = [[set([]), []] for _ in range(n)]
res = [-1 for i in range(q)]
for qi in range(q):
x, y, k = map(int, input().split())
x, y = sorted([x-1, y-1])
if x == y and k <= 1:
res[qi] = 0
else:
qr = (k, x, y, qi)
if x == y:
heapq.heappush(queries[x][1], qr)
else:
queries[x][0].add(qr)
queries[y][0].add(qr)
ids = [i for i in range(n)]
blds = [set([T[i]]) for i in range(n)]
for u, x, y in edges:
i, j = union(queries, blds, ids, x, y)
if i == j:
continue
tot_blds = len(blds[j])
#print u, x, y, i, j, queries[i], queries[j], tot_blds
for qr in queries[i][0]:
if root(ids, qr[1]) != root(ids, qr[2]):
queries[j][0].add(qr)
else:
queries[j][0].discard(qr)
if tot_blds >= qr[0]:
res[qr[-1]] = u
else:
heapq.heappush(queries[j][1], qr)
while queries[i][1] and queries[i][1][0][0] <= tot_blds:
res[queries[i][1][0][-1]] = u
heapq.heappop(queries[i][1])
for qr in queries[i][1]:
heapq.heappush(queries[j][1], qr)
queries[i][0] = None
queries[i][1] = None
while queries[j][1] and queries[j][1][0][0] <= tot_blds:
res[queries[j][1][0][-1]] = u
heapq.heappop(queries[j][1])
for r in res:
print(r)
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static TreeSet<Integer>[] all;
static int ind;
static void swapAll(int root_A, int root_B) {
TreeSet<Integer> tmp = all[root_A];
all[root_A] = all[root_B];
all[root_B] = tmp;
}
static class DisjointUnionSets {
int[] parent;
int[] rank;
public DisjointUnionSets(int n) {
parent = new int[n];
rank = new int[n];
}
int findset(int x) {
return x == parent[x] ? x : findset(parent[x]);
}
void union(int x, int y) {
int xRoot = findset(x);
int yRoot = findset(y);
if (xRoot == yRoot) {
return;
}
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = parent[yRoot];
rank[yRoot] += rank[xRoot];
if (all[xRoot].size() > all[yRoot].size()) {
swapAll(xRoot, yRoot);
}
while (all[xRoot].size() > 0) {
int tmp = all[xRoot].pollFirst();
all[yRoot].add(tmp);
}
} else {
parent[yRoot] = parent[xRoot];
rank[xRoot] += rank[yRoot];
if (all[xRoot].size() < all[yRoot].size()) {
swapAll(xRoot, yRoot);
}
while (all[yRoot].size() > 0) {
int tmp = all[yRoot].pollFirst();
all[xRoot].add(tmp);
}
}
}
}
static class QS {
int x, y, k, id;
public QS(int x, int y, int k, int id) {
this.x = x;
this.y = y;
this.k = k;
this.id = id;
}
}
static class Edge {
int u;
int v;
public Edge(int xx, int yy) {
this.u = xx;
this.v = yy;
}
}
static class EdgeW {
int w;
Edge edge;
public EdgeW(int xx, Edge yy) {
this.w = xx;
this.edge = yy;
}
}
static EdgeW[] edges;
static void apply(DisjointUnionSets dus, int k) {
while (ind < edges.length) {
if (edges[ind].w > k) {
break;
} else {
dus.union(edges[ind].edge.u, edges[ind].edge.v);
ind++;
}
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
Map<Integer, Integer> map = new HashMap<>();
int cntb = 0;
int[] revmp1 = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
int item = Integer.parseInt(st.nextToken());
if (!map.containsKey(item)) {
map.put(item, ++cntb);
}
revmp1[i] = map.get(item);
}
edges = new EdgeW[m];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[i] = new EdgeW(w, new Edge(u, v));
}
Arrays.sort(edges, (a, b) -> a.w - b.w);
int[] revmp2 = new int[m+1];
int cnte = 0;
map.clear();
for (int k = 0; k < edges.length; k++) {
EdgeW i = edges[k];
if (!map.containsKey(i.w)) {
map.put(i.w, ++cnte);
revmp2[cnte] = i.w;
}
edges[k].w = map.get(i.w);
}
int tot = 0;
int[] ans = new int[q];
QS[] qs = new QS[q+1];
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
if (w > cntb) {
ans[i] = -1;
} else {
tot++;
qs[tot] = new QS(u, v, w, i);
}
}
int[] lo = new int[tot + 1];
int[] hi = new int[tot + 1];
for (int i = 1; i <= tot; i++) {
lo[i] = 1;
hi[i] = cnte + 1;
}
Stack<Integer>[] check = new Stack[Math.max(n + 1, m)];
all = new TreeSet[n + 1];
for (int i = 0; i <= n; i++) {
all[i] = new TreeSet<>();
}
for (int i = 0; i < check.length; i++) {
check[i] = new Stack<>();
}
DisjointUnionSets dus = new DisjointUnionSets(n + 1);
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= n; i++) {
all[i].clear();
all[i].add(revmp1[i]);
dus.parent[i] = i;
dus.rank[i] = 1;
}
int upto = 0;
for (int i = 1; i <= tot; i++) {
if (lo[i] != hi[i]) {
check[(lo[i] + hi[i]) >> 1].add(i);
upto = Math.max(upto, (lo[i] + hi[i]) >> 1);
}
}
ind = 0;
for (int i = 1; i <= upto; i++) {
apply(dus, i);
while (check[i].size() > 0) {
changed = true;
int id = check[i].pop();
int rootx = dus.findset(qs[id].x);
int rooty = dus.findset(qs[id].y);
if (rootx != rooty) {
lo[id] = i + 1;
} else {
if (all[rootx].size() >= qs[id].k) {
hi[id] = i;
} else {
lo[id] = i + 1;
}
}
}
}
}
for (int i = 1; i <= tot; i++) {
if (lo[i] <= cnte) {
ans[qs[i].id] = revmp2[lo[i]];
} else {
ans[qs[i].id] = -1;
}
}
for (int i = 0; i < q; i++) {
bw.write(ans[i] + "n");
}
bw.newLine();
bw.close();
br.close();
}
}
Problem solution in C++.
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define sz2 200001
#define ii pair<int, int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
int qq, N, M, Q, K, C, max_edge = 1000000001;
vector<ii > G[100001];
vector<pair<int, ii > > E;
priority_queue<pair<int, ii > > pq;
pair <int, ii > q[2000001];
int lvl[sz2],T[100001],a[1000001],L[sz2],
R[sz2],p[sz2],parent[sz2][20],col[100001],
ll[sz2],rr[sz2],weight[sz2],dis[sz2],
ans[2000001],st[5000005],used[10000001];
bool vis[100001];
int mycmp(pair <int, ii > a, pair <int, ii > b)
{
if (a.ss.ff != b.ss.ff) return a.ss.ff < b.ss.ff;
return a.ff < b.ff;
}
// DisjointSet
int find_parent(int i) {
if (p[i] == i) return i;
return p[i] = find_parent(p[i]);
}
void set_lvl(int v, int l) {
lvl[v] = l;
if (v > N) {
set_lvl(ll[v], l + 1);
set_lvl(rr[v], l + 1);
}
}
// LeastCommonAncestor
void build_lca() {
for (int i = 1; i < 20; i++)
for (int v = 1; v <= K; v++) {
parent[v][i] = parent[parent[v][i - 1]][i - 1];
}
}
int LCA(int u, int v) {
if (lvl[u] > lvl[v]) swap(u, v);
for (int i = 20; i > 0; i--)
if (lvl[parent[v][i-1]] >= lvl[u]) v = parent[v][i-1];
if (u == v) return u;
for (int i = 20; i > 0; i--)
if (parent[u][i-1] != parent[v][i-1]) {
u = parent[u][i-1]; v = parent[v][i-1];
}
return parent[u][0];
}
class STO {
public:
int n, m;
STO() { n = m = 0; }
void add_color(int x) { a[++n] = x; }
void add_query(pair<int, ii > query) { q[++m] = query; }
void solve() {
sort(q + 1, q + m + 1, mycmp);
for (int i=1,j=1; i<=m; i++)
{
while(j <= q[i].ss.ff)
{
if (!used[a[j]]) {
Update(1, 1, n, j, 1);
used[a[j]] = j;
} else {
Update(1, 1, n, used[a[j]], 0);
Update(1, 1, n, j, 1);
used[a[j]] = j;
}
j++;
}
ans[q[i].ss.ss] = Find(1, 1, n, q[i].ff, q[i].ss.ff);
}
}
int get_ans(int i) {
return ans[i];
}
int Find(int ind, int A, int B, int l, int r)
{
if (l > B || r < A) return 0;
if (A == l && B == r) return st[ind];
int mid = (A + B) / 2;
return Find(ind * 2, A, mid, l, min(mid, r)) + Find(ind * 2 + 1, mid + 1, B, max(mid + 1, l), r);
}
void Update(int ind, int l, int r, int x, int d)
{
if (l == r) st[ind] = d;
else {
int mid = (l + r) / 2;
if (x <= mid) Update(ind * 2, l, mid, x, d);
else Update(ind * 2 + 1, mid + 1, r, x, d);
st[ind] = st[ind * 2] + st[ind * 2 + 1];
}
}
};
STO seg_tree;
void dfs(int v) {
if (v > N) {
dfs(ll[v]);
dfs(rr[v]);
L[v] = L[ll[v]];
R[v] = R[rr[v]];
seg_tree.add_query(mp(L[v], mp(R[v], qq))); qq++;
} else {
C++;
seg_tree.add_color(col[v]);
L[v] = C;
R[v] = C;
}
}
void dfs1(int v) {
if (v == 0) return;
if (v > N) {
dfs1(ll[v]);
dfs1(rr[v]);
weight[v] = seg_tree.get_ans(qq); qq++;
} else weight[v] = 1;
}
void color_solve() {
vector<int> v1, v2;
for (int i = 1; i <= N; i++)
v1.pb(T[i]);
sort(v1.begin(), v1.end());
v2.pb(v1[0]);
for (int i = 1, sz = 0; i<v1.size(); i++)
if (v2[sz - 1] != v1[i]) {
v2.pb(v1[i]); sz++;
}
for (int i = 1; i <= N; i++)
col[i] = lower_bound(v2.begin(), v2.end(), T[i]) - v2.begin() + 1;
}
int main() {
int u, v, e, k, x, y;
scanf("%d%d%d",&N,&M,&Q);
for (int i = 1; i <= N; i++) {
scanf("%d",&T[i]);
G[0].pb(mp(i, -max_edge));
G[i].pb(mp(0, -max_edge));
}
for (int j = 0; j < M; j++) {
scanf("%d%d%d",&u,&v,&e);
G[u].pb(mp(v, -e));
G[v].pb(mp(u, -e));
}
pq.push(mp(0, mp(0, -1)));
while (!pq.empty()) {
e = pq.top().ff;
x = pq.top().ss.ff;
y = pq.top().ss.ss;
pq.pop();
if (!vis[x]) {
vis[x] = true;
if (y != -1) E.pb(mp(-e, mp(x, y)));
for (int i = 0; i < G[x].size(); i++)
if (!vis[G[x][i].ff]) pq.push(mp(G[x][i].ss, mp(G[x][i].ff, x)));
}
}
sort(E.begin(), E.end());
for (int i = 0; i < 2 * N; i++)
p[i] = i;
K = N;
for (int i = 0; i < E.size(); i++) {
K++;
int X = find_parent(E[i].ss.ff), Y = find_parent(E[i].ss.ss);
p[X] = p[Y] = parent[X][0] = parent[Y][0] = K;
dis[K] = E[i].ff == max_edge?-1:E[i].ff;
ll[K] = X;
rr[K] = Y;
}
color_solve(); qq=1; dfs (K);
seg_tree.solve(); qq=1; dfs1(K);
set_lvl(K, 1);
lvl[0] = parent[0][0] = 0;
build_lca();
while (Q--) {
scanf("%d%d%d",&x,&y,&k);
if (weight[K] < k) {
printf("-1n");
continue;
}
x = LCA(x, y);
if (weight[x] >= k) printf("%dn",dis[x]);
else {
for (int i = 19; i >= 0; i--) {
y = parent[x][i];
if (y && weight[y] < k) x = y;
}
printf("%dn",dis[parent[x][0]]);
}
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
typedef struct _tree_node{
enum {red,black} colour;
int data;
int idx;
struct _tree_node *left,*right,*parent;
}tree_node;
tree_node *get_min(tree_node *root);
void merge(tree_node *root,tree_node **m,int *s,int f);
int get_group(int x);
void update_group(int x,int y);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
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 f);
int insert(tree_node **root,tree_node *x,int f);
void delete(tree_node **root,tree_node *head,int data);
int t[100000],x[100000],y[100000],u[100000],q1[100000],q2[100000],q3[100000],ans[100000],g[100000],s[100000],s2[100000],s3[100000],qf[100000];
tree_node *color[100000],*head[100000],*query[100000];
int main(){
int n,m,q,g1,g2,g3,g4,temp,temp2,temp3,i;
tree_node *p,*p2,**p3,*p4,*nxt;
scanf("%d%d%d",&n,&m,&q);
for(i=0;i<n;i++)
scanf("%d",t+i);
for(i=0;i<m;i++){
scanf("%d%d%d",x+i,y+i,u+i);
x[i]--;
y[i]--;
}
for(i=0;i<q;i++){
scanf("%d%d%d",q1+i,q2+i,q3+i);
q1[i]--;
q2[i]--;
ans[i]=-1;
}
sort_a3(u,x,y,m);
for(i=0;i<n;i++){
g[i]=i;
p=(tree_node*)malloc(sizeof(tree_node));
p->data=t[i];
p->left=p->right=p->parent=NULL;
insert(color+i,p,0);
s[i]=1;
}
for(i=0;i<q;i++)
if(q1[i]==q2[i]){
p=(tree_node*)malloc(sizeof(tree_node));
p->data=q3[i];
p->idx=i;
p->left=p->right=p->parent=NULL;
insert(&query[q1[i]],p,0);
s3[q1[i]]++;
}
else{
p=(tree_node*)malloc(sizeof(tree_node));
p->data=q3[i];
p->idx=i;
p->left=head[q1[i]];
head[q1[i]]=p;
s2[q1[i]]++;
p=(tree_node*)malloc(sizeof(tree_node));
p->data=q3[i];
p->idx=i;
p->left=head[q2[i]];
head[q2[i]]=p;
s2[q2[i]]++;
}
for(i=0;i<m;i++){
g1=get_group(x[i]);
g2=get_group(y[i]);
if(g1==g2)
continue;
if(s[g1]<s[g2]){
merge(color[g1],&color[g2],&s[g2],1);
p=color[g2];
temp=s[g2];
}
else{
merge(color[g2],&color[g1],&s[g1],1);
p=color[g1];
temp=s[g1];
}
if(s2[g1]<s2[g2]){
for(p2=head[g1];p2;p2=nxt){
nxt=p2->left;
g3=get_group(q1[p2->idx]);
g4=get_group(q2[p2->idx]);
if(!qf[p2->idx]){
if((g3==g1 && g4==g2) || (g3==g2 && g4==g1)){
qf[p2->idx]=1;
p2->left=p2->right=p2->parent=NULL;
insert(&query[g1],p2,0);
s3[g1]++;
}
else{
p2->left=head[g2];
head[g2]=p2;
s2[g2]++;
}
}
}
p2=head[g2];
temp2=s2[g2];
}
else{
for(p2=head[g2];p2;p2=nxt){
nxt=p2->left;
g3=get_group(q1[p2->idx]);
g4=get_group(q2[p2->idx]);
if(!qf[p2->idx]){
if((g3==g1 && g4==g2) || (g3==g2 && g4==g1)){
qf[p2->idx]=1;
p2->left=p2->right=p2->parent=NULL;
insert(&query[g2],p2,0);
s3[g2]++;
}
else{
p2->left=head[g1];
head[g1]=p2;
s2[g1]++;
}
}
}
p2=head[g1];
temp2=s2[g1];
}
if(s3[g1]<s3[g2]){
merge(query[g1],&query[g2],&s3[g2],0);
p3=&query[g2];
temp3=s3[g2];
}
else{
merge(query[g2],&query[g1],&s3[g1],0);
p3=&query[g1];
temp3=s3[g1];
}
while(1){
if(!temp3)
break;
p4=get_min(*p3);
if(p4->data>temp)
break;
ans[p4->idx]=u[i];
delete(p3,*p3,p4->data);
temp3--;
}
update_group(x[i],g1);
update_group(y[i],g1);
s[g1]=temp;
s2[g1]=temp2;
s3[g1]=temp3;
color[g1]=p;
head[g1]=p2;
query[g1]=*p3;
}
for(i=0;i<q;i++){
if(q1[i]==q2[i] && q3[i]==1)
ans[i]=0;
printf("%dn",ans[i]);
}
return 0;
}
tree_node *get_min(tree_node *root){
if(!root)
return NULL;
if(root->left)
return get_min(root->left);
return root;
}
void merge(tree_node *root,tree_node **m,int *s,int f){
if(!root)
return;
merge(root->left,m,s,f);
merge(root->right,m,s,f);
root->left=root->right=root->parent=NULL;
(*s)+=insert(m,root,f);
return;
}
int get_group(int x){
while(g[x]!=x)
x=g[x];
return x;
}
void update_group(int x,int y){
int z=-1;
while(1){
if(x==z)
break;
z=x;
x=g[x];
g[z]=y;
}
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
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,int f){
if(*root==NULL)
*root=x;
else if(f && (*root)->data==x->data)
return 0;
else{
x->parent=*root;
if((*root)->data>x->data)
return normal_insert(&((*root)->left),x,f);
else
return normal_insert(&((*root)->right),x,f);
}
return 1;
}
int insert(tree_node **root,tree_node *x,int f){
if(!normal_insert(root,x,f))
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 || (data==head->data && head->left)){
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; // Do node copy here.
head->idx=db->idx;
head=db;
}
if(head->left==NULL && head->right==NULL){
parent=head->parent;
if(!parent){
*root=NULL;
free(head);
return;
}
brother=(parent->left==head)?parent->right:parent->left;
if(head->colour==red){
if(parent->left==head)
parent->left=NULL;
else
parent->right=NULL;
free(head);
return;
}
if(parent->left==head)
parent->left=&none;
else
parent->right=&none;
none.parent=parent;
none.colour=black;
db=&none;
free(head);
}
else{
parent=head->parent;
child=(!head->left)?head->right:head->left;
if(!parent){
*root=child;
child->parent=NULL;
child->colour=black;
free(head);
return;
}
if(parent->left==head)
parent->left=child;
else
parent->right=child;
child->parent=parent;
db=child;
free(head);
}
}
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;
}