-
Notifications
You must be signed in to change notification settings - Fork 0
/
BSTNode.java
153 lines (147 loc) · 3.41 KB
/
BSTNode.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//Clase tomada de http://www.sanfoundry.com
public class BSTNode <E extends Comparable<E>>{
private Node<E> root;
public BSTNode(){
this.root = null;
}
public E find(E id){
Node<E> current = root;
while(current!=null){
if(current.data.equals(id)){
return current.data;
}else if(current.data.compareTo(id)>0){
current = current.left;
}else{
current = current.right;
}
}
return null;
}
public Node<E> getRoot() {
return root;
}
public void setRoot(Node<E> root) {
this.root = root;
}
public boolean delete(E id){
Node<E> parent = root;
Node<E> current = root;
boolean isLeftChild = false;
while(!current.data.equals(id)){
parent = current;
if(current.data.compareTo(id)>0){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){
//now we have found the minimum element in the right sub tree
Node<E> successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node<E> getSuccessor(Node<E> deleleNode){
Node<E> successsor =null;
Node<E> successsorParent =null;
Node<E> current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(E id){
Node<E> newNode = new Node<E>(id);
if(root==null){
root = newNode;
return;
}
Node<E> current = root;
Node<E> parent = null;
while(true){
parent = current;
if(id.compareTo(current.data)<0){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node<E> root){
if(root!=null){
display(root.left);
System.out.print(root.data + " ");
display(root.right);
}
}
}
class Node<E>{
E data;
Node<E> left;
Node<E> right;
public Node(E data){
this.data = data;
left = null;
right = null;
}
}