-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
120 lines (111 loc) · 4.53 KB
/
index.html
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
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Trees</title>
<script
src="https://code.jquery.com/jquery-3.1.1.min.js"
integrity="sha256-hVVnYaiADRTO2PzUGmuLJr8BLUSjGIZsDYGmIJLv2b8="
crossorigin="anonymous"></script>
<script src="./dist/bundle.js" charset="utf-8"></script>
<link rel="stylesheet" href="css/reset.css">
<link rel="stylesheet" href="css/style.css">
</head>
<body>
<div class="the-world">
<div class="heading group">
<div class="title">
BST JS
</div>
<div class="subtitle">
O(logN) lookup, Ө(N!) fun.
</div>
<div class="heading-right group">
<div class="heading-right-item">
<a href="http://lizha.ng/">Website</a>
</div>
<div class="heading-right-item">
<a href="https://github.com/vorpus/">Github</a>
</div>
<div class="heading-right-item">
<a href="https://www.linkedin.com/in/zhangio">Linkedin</a>
</div>
</div>
</div>
<div class="all-forms group">
<div class="node-form">
<form class="add-node">
<input class="val-to val-to-add" type="number" name="" value="">
<input class="val-to-submit val-to-add-submit" type="submit" name="" value="Add">
</form>
</div>
<div class="node-form">
<form class="delete-node hidden">
<input class="val-to val-to-delete" type="number" name="" value="">
<input class="val-to-submit val-to-delete-submit" type="submit" name="" value="Delete">
</form>
</div>
<div class="clear button">
Clear
</div>
<div class="bst-toggle button">
<div class="bst-display bst-btn hidden">
Binary Search Tree
</div>
<div class="bst-display rbt-btn">
Red/Black Tree
</div>
</div>
</div>
<div class="forest"></div>
<div class="forest-diagram"></div>
<div class="below-canvas">
<div class="about">
The default trees have the following elements inserted
in order: [2, 1, 4, 5, 9, 3, 6, 7]
<br>
Try it out yourself! Watch how the Red-Black tree rearranges
itself to maintain a shorter height than the vanilla BST.
<div class="heading">
What's going on here?
</div>
<p>A <b>Binary Search Tree</b> (BST) is a data structure that is
known for its quick and generally predictable behavior in
searching, sorting, insertion, and deletion. It differs
a Binary Tree in that the value of an element's left child
is lesser and the value of an element's right child is
always greater.
</p>
<br>
<p>If BST nodes are inserted in a specific order, the tree
will essentially become a linked list and lose its
quick lookup properties. Tree rotations allow us to maintain
a reasonable tree height while maintaing its BST properties.
Some BST's with special properties have been created to
use rotations to solve this problem. The most common are
listed below.
<ol>
<li><b>AVL trees</b> require all nodes be balanced, where the
difference in heights of child nodes is no more than 1.
This results in guaranteed O(logN) lookup.
</li>
<li><b>Red-Black trees</b> (implemented here) require
all nodes to be approximately balanced using specific
<a href="https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties">properties</a>.
The less rigorous balance constraints result in slower
lookup than AVL trees but faster insertion and deletion operations.
</li>
<li><b>Splay trees</b> rotate recently added or searched
elements to the root of the BST. This results in extremely
fast lookup for data that is frequently accessed.
</li>
</ol>
Find more on my <a href="https://github.com/vorpus/TreeJS" target="_blank">Github (readme)</a>!
<br>
Try running the <a href="https://vorpus.github.io/TreeJS/SpecRunner.html">Jasmine tests</a>!
</p>
</div>
</div>
</div>
</body>
</html>