Apr 28, 2021

Binary Tree

Data Structure 2028 views

A binary tree is an important type of structure which is characterized by the fact that any node can have at most two branches, there is no node with degree greater than two.

The distinguish between the subtree on the left and on the right, whereas for trees the order of the subtree was irrelevant. Also a binary tree may have zero nodes. Thus a binary tree is really a different object than a tree. From a graph theory perspective, binary trees as defined here are actually arborescences.

/* Insertion */
if x = nil then return "Error"
y = x
while true do {
	if key[y] < k
		then z = left[y]
	else z = right[y]
		if z = nil break
}
if key[y] > k then left[y] = z
else right[p[y]] = z


/* Search */
y = x
while y != nil do
	if key[y] = k then return y
	else if key[y] < k then y = right[y]
	else y = left[y]
return ("NOT FOUND")

    
/* Minimum */
if x = nil then return ("Empty Tree")
y = x
while left[y] != nil do y = left[y]
return (key[y])

  
/* Maximum */
if x = nil then return ("Empty Tree")
y = x
while right[y] != nil do y = right[y]
return (key[y])

  
/* Delete */
if left[z] = nil or right[z] = nil
	then y = z
else y = BST-Successor(z)
	y is the node that's actually removed.
	Here y does not have two children.
if left[y] != nil
	then x = left[y]
else x = right[y]
	x is the node that's moving to y's position.
if x != nil then p[x] = p[y]
	p[x] is reset If x isn't NIL.
	Resetting is unnecessary if x is NIL.
if p[y] = nil then root[T] = x
	if y is the root, then x becomes the root.
	Otherwise, do the following.
else if y = left[p[y]]
	then left[p[y]] = x
	if y is the left child of its parent, then
		Set the parent's left child to x.
	else right[p[y]] = x
		If y is the right child of its parent, then
		Set the parent's right child to x.
	if y != z then {
		key[z] = key[y]
		Move other data from y to z
	}
return (y)

Binary Tree

Author: Geekboots