Binary Tree data-structure

A binary tree is a tree data structure in which each node has at most two children (referred to as the left child and the right child). In a binary tree, the degree of each node can be at most two. Binary trees are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting.

Introduced classes

class BinTreeMap[K: Comparable, E: nullable Object]

trees :: BinTreeMap

Binary Tree Map
class BinTreeNode[K: Comparable, E: nullable Object]

trees :: BinTreeNode

TreeNode used by BinTree

All class definitions

class BinTreeMap[K: Comparable, E: nullable Object]

trees $ BinTreeMap

Binary Tree Map
class BinTreeNode[K: Comparable, E: nullable Object]

trees $ BinTreeNode

TreeNode used by BinTree
package_diagram trees::bintree bintree trees::abstract_tree abstract_tree trees::bintree->trees::abstract_tree core core trees::abstract_tree->core ...core ... ...core->core trees::rbtree rbtree trees::rbtree->trees::bintree trees::trees trees trees::trees->trees::rbtree trees::trees... ... trees::trees...->trees::trees

Ancestors

module abstract_collection

core :: abstract_collection

Abstract collection classes and services.
module abstract_text

core :: abstract_text

Abstract class for manipulation of sequences of characters
module array

core :: array

This module introduces the standard array structure.
module bitset

core :: bitset

Services to handle BitSet
module bytes

core :: bytes

Services for byte streams and arrays
module circular_array

core :: circular_array

Efficient data structure to access both end of the sequence.
module codec_base

core :: codec_base

Base for codecs to use with streams
module codecs

core :: codecs

Group module for all codec-related manipulations
module collection

core :: collection

This module define several collection classes.
module core

core :: core

Standard classes and methods used by default by Nit programs and libraries.
module environ

core :: environ

Access to the environment variables of the process
module error

core :: error

Standard error-management infrastructure.
module exec

core :: exec

Invocation and management of operating system sub-processes.
module file

core :: file

File manipulations (create, read, write, etc.)
module fixed_ints

core :: fixed_ints

Basic integers of fixed-precision
module fixed_ints_text

core :: fixed_ints_text

Text services to complement fixed_ints
module flat

core :: flat

All the array-based text representations
module gc

core :: gc

Access to the Nit internal garbage collection mechanism
module hash_collection

core :: hash_collection

Introduce HashMap and HashSet.
module iso8859_1

core :: iso8859_1

Codec for ISO8859-1 I/O
module kernel

core :: kernel

Most basic classes and methods.
module list

core :: list

This module handle double linked lists
module math

core :: math

Mathematical operations
module native

core :: native

Native structures for text and bytes
module numeric

core :: numeric

Advanced services for Numeric types
module protocol

core :: protocol

module queue

core :: queue

Queuing data structures and wrappers
module range

core :: range

Module for range of discrete objects.
module re

core :: re

Regular expression support for all services based on Pattern
module ropes

core :: ropes

Tree-based representation of a String.
module sorter

core :: sorter

This module contains classes used to compare things and sorts arrays.
module stream

core :: stream

Input and output streams of characters
module text

core :: text

All the classes and methods related to the manipulation of text entities
module time

core :: time

Management of time and dates
module union_find

core :: union_find

union–find algorithm using an efficient disjoint-set data structure
module utf8

core :: utf8

Codec for UTF-8 I/O

Parents

module abstract_tree

trees :: abstract_tree

Introduce tree structures abstraction

Children

module rbtree

trees :: rbtree

A red–black tree is a data structure which is a type of self-balancing binary search tree.

Descendants

module a_star-m

a_star-m

module puzzle

ai :: puzzle

The N-puzzle problem, modeled naively as a SearchProblem.
module search

ai :: search

Basic framework for search problems and solver.
module trees

trees :: trees

General module for tree data structures
module trie

trees :: trie

A trie (or prefix tree) is a datastructure used to perform prefix searches.
# Binary Tree data-structure
# A binary tree is a tree data structure in which each node has at most two children
# (referred to as the left child and the right child).
# In a binary tree, the degree of each node can be at most two.
# Binary trees are used to implement binary search trees and binary heaps,
# and are used for efficient searching and sorting.
module bintree

import abstract_tree

# Binary Tree Map
#
# Properties:
#  * unique root
#  * node.left.key < node.key
#  * node.right.key > node.key
#  * no duplicates allowed
#
# Operations:
#  * search average O(lg n) worst O(n)
#  * insert average O(lg n) worst O(n)
#  * delete average O(lg n) worst O(n)
#
# Usage:
#
#     var tree = new BinTreeMap[Int, String]
#     tree[1] = "n1"
#     assert tree.min == "n1"
class BinTreeMap[K: Comparable, E]
	super TreeMap[K, E]

	redef type N: BinTreeNode[K, E]

	private var len = 0
	private var first_node: nullable BinTreeNode[K, E] = null
	private var last_node: nullable BinTreeNode[K, E] = null

	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     assert tree.is_empty
	#     tree[1] = "n1"
	#     assert not tree.is_empty
	redef fun is_empty do return root == null

	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     assert not tree.has_key(1)
	#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
	#     assert not tree.has_key(0)
	#     assert tree.has_key(2)
	#     assert not tree.has_key(6)
	redef fun has_key(key) do
		if is_empty then return false
		var res = search_down(root.as(not null), key)
		if res != null then
			cache_node = res
			return true
		end
		return false
	end

	private var cache_node: nullable N = null

	# Get the node value associated to `key`
	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
	#     assert tree.has_key(1)
	#     assert tree[1] == "n1"
	#     assert tree.has_key(1)
	#     assert tree[2] == "n2"
	redef fun [](key) do
		assert not_empty: not is_empty
		if cache_node != null and cache_node.key == key then return cache_node.value
		var res = search_down(root.as(not null), key)
		assert has_key: res != null
		return res.value
	end

	# Search `key` in `from` and its children nodes.
	protected fun search_down(from: N, key: nullable Object): nullable N do
		if not key isa Comparable then return null
		var cmp = key <=> from.key
		if cmp == 0 then return from
		if from.left != null and cmp < 0 then
			return search_down(from.left.as(not null), key)
		else if from.right != null then
			return search_down(from.right.as(not null), key)
		end
		return null
	end

	# Get the node with the minimum key
	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
	#     assert tree.min == "n1"
	fun min: E do
		assert not_empty: root != null
		return min_from(root.as(not null)).value
	end

	# Get the left-most child from `node`.
	protected fun min_from(node: N): N do
		if node.left == null then return node
		return min_from(node.left.as(not null))
	end

	# Get the node with the maximum key
	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     for i in [4, 2, 1, 5, 3, 6, 7, 8] do tree[i] = "n{i}"
	#     assert tree.max == "n8"
	fun max: E do
		assert not_empty: root != null
		return max_from(root.as(not null)).value
	end

	# Get the right-most child from `node`.
	protected fun max_from(node: N): N do
		if node.right == null then return node
		return max_from(node.right.as(not null))
	end

	# Insert a new node in tree using `key` and `item`
	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     tree[1] = "n1"
	#     assert tree.max == "n1"
	#     tree[3] = "n3"
	#     assert tree.max == "n3"
	redef fun []=(key, item) do
		insert_node(new BinTreeNode[K, E](key, item))
	end

	# Add `node` in the tree.
	protected fun insert_node(node: N) do
		len += 1
		if root == null then
			root = node
		else
			shift_down(root.as(not null), node)
		end
		if first_node == null then
			first_node = node
		end
		if last_node != null then
			last_node.next = node
			node.prev = last_node
		end
		last_node = node
	end

	# Push down the `node` in tree from a specified `from` index
	protected fun shift_down(from, node: N) do
		var cmp = node.key <=> from.key
		if cmp < 0 then
			if from.left == null then
				from.left = node
				node.parent = from
			else
				shift_down(from.left.as(not null), node)
			end
		else if cmp > 0 then
			if from.right == null then
				from.right = node
				node.parent = from
			else
				shift_down(from.right.as(not null), node)
			end
		end
	end

	# Delete node at `key` (also return the deleted node value)
	# O(n) in worst case, average is O(h) with h: tree height
	#
	#     var tree = new BinTreeMap[Int, String]
	#     tree[1] = "n1"
	#     assert tree.max == "n1"
	#     tree[3] = "n3"
	#     assert tree.max == "n3"
	#     tree.delete(3)
	#     assert tree.max == "n1"
	fun delete(key: K): nullable E do
		assert is_empty: root != null
		len -= 1
		var node = search_down(root.as(not null), key)
		if node == null then return null
		if node.left == null then
			transplant(node, node.right)
		else if node.right == null then
			transplant(node, node.left)
		else
			var min = min_from(node.right.as(not null))
			if min.parent != node then
				transplant(min, min.right)
				min.right = node.right
				min.right.parent = min
			end
			transplant(node, min)
			min.left = node.left
			min.left.parent = min
		end
		if first_node == node then
			first_node = null
		end
		if last_node == node then
			last_node = node.prev
			last_node.next = null
		else
			node.prev.next = node.next
			node.next.prev = node.prev
		end
		return node.value
	end

	# Swap a `node` with the `other` in this Tree
	# note: Nodes parents are updated, children still untouched
	protected fun transplant(node, other: nullable N) do
		if node == null then return
		if node.parent == null then
			root = other
		else if node == node.parent.left then
			node.parent.left = other
		else
			node.parent.right = other
		end
		if other != null then other.parent = node.parent
	end

	# Perform left rotation on `node`
	#
	# ~~~raw
	#     N             Y
	#    / \     >     / \
	#   a   Y         N   c
	#      / \   <   / \
	#     b   c     a   b
	# ~~~
	#
	protected fun rotate_left(node: N) do
		var y = node.right
		node.right = y.left
		if y.left != null then
			y.left.parent = node
		end
		y.parent = node.parent
		if node.parent == null then
			root = y
		else if node == node.parent.left then
			node.parent.left = y
		else
			node.parent.right = y
		end
		y.left = node
		node.parent = y
	end

	# Perform right rotation on `node`
	#
	# ~~~raw
	#     N             Y
	#    / \     >     / \
	#   a   Y         N   c
	#      / \   <   / \
	#     b   c     a   b
	# ~~~
	#
	protected fun rotate_right(node: N) do
		var y = node.left
		node.left = y.right
		if y.right != null then
			y.right.parent = node
		end
		y.parent = node.parent
		if node.parent == null then
			root = y
		else if node == node.parent.right then
			node.parent.right = y
		else
			node.parent.left = y
		end
		y.right = node
		node.parent = y
	end

	# Sort the tree into an array
	# O(n)
	#
	#     var tree = new BinTreeMap[Int, String]
	#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
	#     assert tree.sort == ["n1", "n2", "n3", "n4", "n5"]
	fun sort: Array[E] do
		var sorted = new Array[E]
		if root == null then return sorted
		sort_down(root.as(not null), sorted)
		return sorted
	end

	# Sort the tree from `node` and place results in `sorted`.
	protected fun sort_down(node: N, sorted: Array[E]) do
		if node.left != null then sort_down(node.left.as(not null), sorted)
		sorted.add(node.value)
		if node.right != null then sort_down(node.right.as(not null), sorted)
	end

	redef fun to_s do
		var root = self.root
		if root == null then return "[]"
		return "[{print_tree(root)}]"
	end

	# Print the tree starting from `node`.
	protected fun print_tree(node: N): String do
		var s = new FlatBuffer
		s.append(node.to_s)
		if node.left != null then s.append(print_tree(node.left.as(not null)))
		if node.right != null then s.append(print_tree(node.right.as(not null)))
		return s.to_s
	end

	redef fun show_dot do
		assert not_empty: root != null
		var f = new ProcessWriter("dot", "-Txlib")
		f.write "digraph \{\n"
		dot_down(root.as(not null), f)
		f.write "\}\n"
		f.close
	end

	# Translate the tree in dot format starting from `node`.
	protected fun dot_down(node: N, f: ProcessWriter) do
		if node.left != null then dot_down(node.left.as(not null), f)
		f.write node.to_dot
		if node.right != null then dot_down(node.right.as(not null), f)
	end

	# O(n)
	#
	#     var tree = new BinTreeMap[Int, String]
	#     assert tree.length == 0
	#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
	#     assert tree.length == 5
	redef fun length do return len

	# Nodes are iterated in the same order in which they were added to the tree.
	# O(n)
	#
	#     var tree = new BinTreeMap[Int, String]
	#     for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
	#     var keys = new Array[Int]
	#     for k, v in tree do
	#         keys.add k
	#     end
	#     assert keys == [4, 2, 1, 5, 3]
	redef fun iterator do return new BinTreeMapIterator[K, E](self)
end

# TreeNode used by BinTree
class BinTreeNode[K: Comparable, E]
	super TreeNode[K, E]

	private var prev: nullable BinTreeNode[K, E] = null
	private var next: nullable BinTreeNode[K, E] = null

	redef type N: BinTreeNode[K, E]

	private var left_node: nullable N = null

	# `left` tree node child (null if node has no left child)
	fun left: nullable N do return left_node

	# set `left` child for this node (or null if left no child)
	# ENSURE: node.key < key (only if node != null)
	fun left=(node: nullable N) do
		#assert node != null implies node.key < key
		left_node = node
	end

	private var right_node: nullable N = null

	# `right` tree node child (null if node has no right child)
	fun right: nullable N do return right_node

	# set `right` child for this node (or null if right no child)
	# ENSURE: node.key < key (only if node != null)
	fun right=(node: nullable N) do
		#assert node != null implies node.key > key
		right_node = node
	end

	# `parent` of the `parent` of this node (null if root)
	fun grandparent: nullable N do
		if parent == null then
			return null
		else
			return parent.parent
		end
	end

	# Other child of the `grandparent`
	# `left` or `right` depends on the position of the current node against its parent
	fun uncle: nullable N do
		var g = grandparent
		if g == null then
			return null
		else
			if parent == g.left then
				return g.right
			else
				return g.left
			end
		end
	end

	# Other child of the parent
	# `left` or `right` depends on the position of the current node against its parent
	fun sibling: nullable N do
		if parent == null then
			return null
		else if self == parent.left then
			return parent.right
		else if self == parent.right then
			return parent.left
		else
			return null
		end
	end

	redef fun to_s do return "\{{key}: {value or else ""}\}"
end

private class BinTreeMapIterator[K: Comparable, E]
	super MapIterator[K, E]

	var tree: BinTreeMap[K, E]
	var current: nullable BinTreeNode[K, E] = null

	init do current = tree.first_node

	redef fun is_ok do return not current == null
	redef fun next do current = current.next
	redef fun item do return current.value
	redef fun key do do return current.key
end
lib/trees/bintree.nit:15,1--465,3