Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var node = {
- value: 0,
- left: null,
- right: null
- }
- var create_node = function(val, l, r) {
- return {value: val, left: l, right: r}
- }
- var n3 = {
- value: 15,
- left: null,
- right: null
- }
- var n2 = {
- value: 13,
- left: null,
- right: n3
- }
- var n1 = {
- value: 5,
- left: null,
- right: null
- }
- var n0 = {
- value: 10,
- left: n1,
- right: n2
- }
- console.log('tree: ', n0)
- function print_tree(root) {
- if (root != null) {
- print_tree(root.left)
- console.log(root.value)
- print_tree(root.right)
- }
- }
- function find(k, root) {
- // base
- if (root != null) {
- if (root.value == k) {
- return root
- } else if (k < root.value) {
- return find(k, root.left)
- } else {
- return find(k, root.right)
- }
- } else {
- return null
- }
- }
- function pretty_print(root) {
- if (root != null) {
- console.log(root.value)
- }
- }
- function insert(k, root) {
- // base case
- if (root.left === null && k < root.value) {
- root.left = {
- value: k,
- left: null,
- right: null,
- }
- return
- }
- if (root.right === null && k > root.value) {
- root.right = {
- value: k,
- left: null,
- right: null,
- }
- return
- }
- // recursive case
- if (k < root.value) {
- insert(k, root.left)
- } else if (k > root.value) {
- insert(k, root.right)
- }
- }
- function test_insert() {
- insert(8, n0)
- insert(9, n0)
- print_tree(n0)
- console.log(n0)
- }
- function delete_node(k, root, parent) {
- if (k < root.value) {
- // left
- console.log('go left')
- delete_node(k, root.left, root)
- } else if (k > root.value) {
- // right
- console.log('go right')
- delete_node(k, root.right, root)
- } else {
- console.log('time to delete')
- // base
- if (root.left === null && root.right === null) {
- // 1. no children
- if (root.value < parent.value) {
- parent.left = null
- } else {
- parent.right = null
- }
- } else if (root.left !== null && root.right !== null) {
- // 2. two children
- console.log('two children')
- // find successor
- var current_parent = root
- var current = root.right
- while (current.left !== null) {
- current_parent = current
- current = current.left
- }
- console.log('current: ', current)
- // delete successor and attach successor's children
- if (current_parent == root) {
- current_parent.right = current.right
- } else {
- current_parent.left = current.right
- }
- // swap successor and delete root
- current.left = root.left
- current.right = root.right
- if (parent !== null) {
- if (root.value < parent.value) {
- parent.left = current
- } else {
- parent.right = current
- }
- }
- // replace root
- root = current
- console.log('done')
- } else {
- // 3. one child
- console.log('one child')
- if (root.left !== null && root.right === null) {
- if (root.value < parent.value) {
- parent.left = root.left
- } else {
- parent.right = root.left
- }
- } else if (root.left === null && root.right !== null) {
- if (root.value < parent.value) {
- parent.left = root.right
- } else {
- parent.right = root.right
- }
- }
- }
- }
- return root
- }
- function test_delete_node() {
- var new_tree = delete_node(10, n0, null)
- console.log(new_tree)
- print_tree(new_tree)
- }
- console.log('test_delete_node')
- test_delete_node()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement