-
Notifications
You must be signed in to change notification settings - Fork 0
/
avl_tree_other_solution.js
107 lines (97 loc) · 3.47 KB
/
avl_tree_other_solution.js
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
class Node {
constructor(value, left=null, right=null){
this.value = value;
this.right = right;
this.left = left;
this.height = 1;
}
}
class AVL {
constructor(){
this.root = null;
}
// yukseklik donderme
height(N){
if(N === null) return 0;
return N.height;
}
// saga donderme : sol -> sol dengesizligini cozer
singleRightRotate(N){
let ll = N.left; // N'nin solu ll oldu
let T2 = ll.right;// N'nin soluna' ll'nin sagini ekle
ll.right = N; // N artik ll'nin sag dugumu oldu
N.left = T2
N.height = Math.max(this.height(N.left) - this.height(N.right))+1;
ll.height = Math.max(this.height(ll.left) - this.height(ll.right))+1;
return ll;
}
// sola sonra saga donderme : sol -> sag dengesizligini cozer
doubleRotateRight(N){
N.left = this.singleLeftRotate(N.left);// agacin "sagini" sola donerme yapar
return this.singleRightRotate(N); // "agaci" saga donderme yapar
}
// sola donderme : sag -> sag dengesizligini cozer
singleLeftRotate(N){
let rr = N.right;// N'nin sagi rr
let T2 = rr.left;// N'nin sagin'a rr'nin solunu ekle
rr.left = N; // N artik rr'nin sol durumu oldu
N.right = T2;
N.height = Math.max(this.height(N.left) - this.height(N.right))+1;
rr.height = Math.max(this.height(rr.left) - this.height(rr.right))+1;
}
// saga sonra sola donderme : sag -> sol dengesizligini cozer
dobuleRotateLeft(N){
N.right = this.singleRightRotate(N.right);// agacin "solunu" saga donderme yapar
return this.singleLeftRotate(N); // agaci sola donderir.
}
// ekleme
insert(current,data){
if(current === null){
return (new Node(data));
}
if(data < current.value){
current.left = this.insert(current.left);
if(this.height(current.left) - this.height(current.right) === 2){
if(data < current.left.value)// sol -> sol dengesizligi
current = singleRotateRight(current);// saga tek donderme
current = doubleRotateRight(current);// once sola sonra saga donderme(cift sag)
}
}
else if(data > current.value){
current.right = this.insert(current.right);
if(this.height(current.left) - this.height(current.right) === -2){
if(data > current.right.value)// sag -> sag dengesizlig
current = singleLeftRotate(current);// saga tek donderme
current = dobuleRotateLeft(current);//once saga sonra sola donderme(cift sol)
}
}
// agacin yukseklik durumu : hangisi daha fazla ise ordaki degeri 1 arrtidik
current.height = Math.max(this.height(current.left) , this.height(current.right)) +1;
return current;
}
// node ekle
insertNode(data){
this.root = this.insert(this.root, data);
}
// preOrder ile ekrana bastirma node -> left -> right || node -> right -> left
preOrder(){
this.preOrderHelper(this.root)
}
preOrderHelper(node) {
if (node) {
console.log(node.value);
this.preOrderHelper(node.left);
this.preOrderHelper(node.right);
}
}
}
const avl = new AVL();
avl.insertNode(33);
avl.insertNode(12);
avl.insertNode(35);
avl.insertNode(34);
avl.insertNode(36);
avl.insertNode(37);
avl.insertNode(40);
avl.preOrder();
console.log(avl);