Binary Trees¶

class pydatastructs.BinaryTree(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Abstract binary tree.

Parameters

key – Required if tree is to be instantiated with root otherwise not needed.
root_data – Optional, the root node of the binary tree. If not of type TreeNode, it will consider root as data and a new root node will be created.
comp (lambda/function) – Optional, A lambda function which will be used for comparison of keys. Should return a bool value. By default it implements less than operator.
is_order_statistic (bool) – Set it to True, if you want to use the order statistic features of the tree.

References

1: https://en.wikipedia.org/wiki/Binary_tree

insert(key, data=None)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

delete(key, **kwargs)¶

Deletes the data with the passed key using iterative algorithm.

Parameters

key – The key of the node which is to be deleted.
balancing_info (bool) – Optional, by default, False The information needed for updating the tree is returned if this parameter is set to True. It is not meant for user facing APIs.

Returns

True – If the node is deleted successfully.
None – If the node to be deleted doesn’t exists.

Note

The node is deleted means that the connection to that node are removed but the it is still in three. This is being done to keep the complexity of deletion, O(logn).

search(key, **kwargs)¶

Searches for the data in the binary search tree using iterative algorithm.

Parameters

key – The key for searching.
parent (bool) – If true then returns index of the parent of the node with the passed key. By default, False

Returns

int – If the node with the passed key is in the tree.
tuple – The index of the searched node and the index of the parent of that node.
None – In all other cases.

__str__()¶: Return str(self).

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.BinarySearchTree(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Represents binary search trees.

Examples

>>> from pydatastructs.trees import BinarySearchTree as BST
>>> b = BST()
>>> b.insert(1, 1)
>>> b.insert(2, 2)
>>> child = b.tree[b.root_idx].right
>>> b.tree[child].data
2
>>> b.search(1)
0
>>> b.search(-1) is None
True
>>> b.delete(1) is True
True
>>> b.search(1) is None
True
>>> b.delete(2) is True
True
>>> b.search(2) is None
True

References

1: https://en.wikipedia.org/wiki/Binary_search_tree

See also

pydatastructs.trees.binary_tree.BinaryTree

left_size(node)¶

right_size(node)¶

insert(key, data=None)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

search(key, **kwargs)¶

Searches for the data in the binary search tree using iterative algorithm.

Parameters

key – The key for searching.
parent (bool) – If true then returns index of the parent of the node with the passed key. By default, False

Returns

int – If the node with the passed key is in the tree.
tuple – The index of the searched node and the index of the parent of that node.
None – In all other cases.

delete(key, **kwargs)¶

Deletes the data with the passed key using iterative algorithm.

Parameters

key – The key of the node which is to be deleted.
balancing_info (bool) – Optional, by default, False The information needed for updating the tree is returned if this parameter is set to True. It is not meant for user facing APIs.

Returns

True – If the node is deleted successfully.
None – If the node to be deleted doesn’t exists.

Note

The node is deleted means that the connection to that node are removed but the it is still in three. This is being done to keep the complexity of deletion, O(logn).

select(i)¶

Finds the i-th smallest node in the tree.

Parameters: i (int) – A positive integer
Returns: n – The node with the i-th smallest key
Return type: TreeNode

References

1: https://en.wikipedia.org/wiki/Order_statistic_tree

rank(x)¶

Finds the rank of the given node, i.e. its index in the sorted list of nodes of the tree.

Parameters: x (key) – The key of the node whose rank is to be found out.

lowest_common_ancestor(j, k, algorithm=1)¶

Computes the lowest common ancestor of two nodes.

Parameters

j (Node.key) – Key of first node
k (Node.key) – Key of second node
algorithm (int) –
The algorithm to be used for computing the lowest common ancestor. Optional, by default uses algorithm 1.

1 -> Determines the lowest common ancestor by finding
the first intersection of the paths from v and w to the root.

2 -> Modifed version of the algorithm given in the
following publication, D. Harel. A linear time algorithm for the lowest common ancestors problem. In 21s Annual Symposium On Foundations of Computer Science, pages 308-319, 1980.

Returns

The key of the lowest common ancestor in the tree. if both the nodes are present in the tree.

Return type

Node.key

References

1: https://en.wikipedia.org/wiki/Lowest_common_ancestor
2: https://pdfs.semanticscholar.org/e75b/386cc554214aa0ebd6bd6dbdd0e490da3739.pdf

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.AVLTree(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Represents AVL trees.

References

1: https://courses.cs.washington.edu/courses/cse373/06sp/handouts/lecture12.pdf
2: https://en.wikipedia.org/wiki/AVL_tree
3: http://faculty.cs.niu.edu/~freedman/340/340notes/340avl2.htm

left_height(node)¶

right_height(node)¶

balance_factor(node)¶

insert(key, data=None)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

delete(key, **kwargs)¶

Deletes the data with the passed key using iterative algorithm.

Parameters

key – The key of the node which is to be deleted.
balancing_info (bool) – Optional, by default, False The information needed for updating the tree is returned if this parameter is set to True. It is not meant for user facing APIs.

Returns

True – If the node is deleted successfully.
None – If the node to be deleted doesn’t exists.

Note

The node is deleted means that the connection to that node are removed but the it is still in three. This is being done to keep the complexity of deletion, O(logn).

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.BinaryIndexedTree(array)¶

Represents binary indexed trees a.k.a fenwick trees.

Parameters: array (list/tuple) – The array whose elements are to be considered for the queries.

Examples

>>> from pydatastructs import BinaryIndexedTree
>>> bit = BinaryIndexedTree([1, 2, 3])
>>> bit.get_sum(0, 2)
6
>>> bit.update(0, 100)
>>> bit.get_sum(0, 2)
105

References

1: https://en.wikipedia.org/wiki/Fenwick_tree

update(index, value)¶

Updates value at the given index.

Parameters

index (int) – Index of element to be updated.
value – The value to be inserted.

get_prefix_sum(index)¶

Computes sum of elements from index 0 to given index.

Parameters: index (int) – Index till which sum has to be calculated.
Returns: sum – The required sum.
Return type: int

get_sum(left_index, right_index)¶

Get sum of elements from left index to right index.

Parameters

left_index (int) – Starting index from where sum has to be computed.
right_index (int) – Ending index till where sum has to be computed.

Returns

sum – The required sum

Return type

int

tree¶

array¶

flag¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.CartesianTree(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Represents cartesian trees.

Examples

>>> from pydatastructs.trees import CartesianTree as CT
>>> c = CT()
>>> c.insert(1, 4, 1)
>>> c.insert(2, 3, 2)
>>> child = c.tree[c.root_idx].left
>>> c.tree[child].data
1
>>> c.search(1)
0
>>> c.search(-1) is None
True
>>> c.delete(1) is True
True
>>> c.search(1) is None
True
>>> c.delete(2) is True
True
>>> c.search(2) is None
True

References

1: https://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/geo-st.pdf

See also

pydatastructs.trees.binary_trees.SelfBalancingBinaryTree

insert(key, priority, data=None)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

delete(key, **kwargs)¶

Deletes the data with the passed key using iterative algorithm.

Parameters

key – The key of the node which is to be deleted.
balancing_info (bool) – Optional, by default, False The information needed for updating the tree is returned if this parameter is set to True. It is not meant for user facing APIs.

Returns

True – If the node is deleted successfully.
None – If the node to be deleted doesn’t exists.

Note

The node is deleted means that the connection to that node are removed but the it is still in three. This is being done to keep the complexity of deletion, O(logn).

__str__()¶: Return str(self).

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.Treap(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Represents treaps.

Examples

>>> from pydatastructs.trees import Treap as T
>>> t = T()
>>> t.insert(1, 1)
>>> t.insert(2, 2)
>>> t.search(1)
0
>>> t.search(-1) is None
True
>>> t.delete(1) is True
True
>>> t.search(1) is None
True
>>> t.delete(2) is True
True
>>> t.search(2) is None
True

References

1: https://en.wikipedia.org/wiki/Treap

insert(key, data=None)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.SplayTree(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Represents Splay Trees.

References

1: https://en.wikipedia.org/wiki/Splay_tree

splay(x, p)¶

insert(key, x)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

delete(x)¶

Deletes the data with the passed key using iterative algorithm.

Parameters

key – The key of the node which is to be deleted.
balancing_info (bool) – Optional, by default, False The information needed for updating the tree is returned if this parameter is set to True. It is not meant for user facing APIs.

Returns

True – If the node is deleted successfully.
None – If the node to be deleted doesn’t exists.

Note

The node is deleted means that the connection to that node are removed but the it is still in three. This is being done to keep the complexity of deletion, O(logn).

join(other)¶

Joins two trees current and other such that all elements of the current splay tree are smaller than the elements of the other tree.

Parameters: other (SplayTree) – SplayTree which needs to be joined with the self tree.

split(x)¶

Splits current splay tree into two trees such that one tree contains nodes with key less than or equal to x and the other tree containing nodes with key greater than x.

Parameters: x (key) – Key of the element on the basis of which split is performed.
Returns: other – SplayTree containing elements with key greater than x.
Return type: SplayTree

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.RedBlackTree(key=None, root_data=None, comp=None, is_order_statistic=False)¶

Represents Red Black trees.

Examples

>>> from pydatastructs.trees import RedBlackTree as RB
>>> b = RB()
>>> b.insert(1, 1)
>>> b.insert(2, 2)
>>> child = b.tree[b.root_idx].right
>>> b.tree[child].data
2
>>> b.search(1)
0

References

1: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

See also

pydatastructs.trees.binary_trees.SelfBalancingBinaryTree

insert(key, data=None)¶

Inserts data by the passed key using iterative algorithm.

Parameters

key – The key for comparison.
data – The data to be inserted.

Returns

Return type

None

delete(key, **kwargs)¶

Deletes the data with the passed key using iterative algorithm.

Parameters

key – The key of the node which is to be deleted.
balancing_info (bool) – Optional, by default, False The information needed for updating the tree is returned if this parameter is set to True. It is not meant for user facing APIs.

Returns

True – If the node is deleted successfully.
None – If the node to be deleted doesn’t exists.

Note

The node is deleted means that the connection to that node are removed but the it is still in three. This is being done to keep the complexity of deletion, O(logn).

root_idx¶

comparator¶

tree¶

size¶

is_order_statistic¶

__module__ = 'pydatastructs.trees.binary_trees'¶

class pydatastructs.BinaryTreeTraversal(tree)¶

Represents the traversals possible in a binary tree.

Parameters

tree (BinaryTree) – The binary tree for whose traversal is to be done.
Traversals –
========== –
Search (- Breadth First) – In Order, Post Order, Pre Order Out Order
Search –

Examples

>>> from pydatastructs import BinarySearchTree as BST
>>> from pydatastructs import BinaryTreeTraversal as BTT
>>> b = BST(2, 2)
>>> b.insert(1, 1)
>>> b.insert(3, 3)
>>> trav = BTT(b)
>>> dfs = trav.depth_first_search()
>>> [str(n) for n in dfs]
['(None, 1, 1, None)', '(1, 2, 2, 2)', '(None, 3, 3, None)']
>>> bfs = trav.breadth_first_search()
>>> [str(n) for n in bfs]
['(1, 2, 2, 2)', '(None, 1, 1, None)', '(None, 3, 3, None)']

References

1: https://en.wikipedia.org/wiki/Tree_traversal

depth_first_search(order='in_order', node=None)¶

Computes the depth first search traversal of the binary trees.

Parameters

order (str) – One of the strings, ‘in_order’, ‘post_order’, ‘pre_order’, ‘out_order’. By default, it is set to, ‘in_order’.
node (int) – The index of the node from where the traversal is to be instantiated.

Returns

Each element is of type ‘TreeNode’.

Return type

list

breadth_first_search(node=None, strategy='queue')¶

Computes the breadth first search traversal of a binary tree.

Parameters

node (int) – The index of the node from where the traversal has to be instantiated. By default, set to, root index.
strategy (str) – The strategy using which the computation has to happen. By default, it is set ‘queue’.

Returns

Each element of the list is of type TreeNode.

Return type

list

tree¶

__module__ = 'pydatastructs.trees.binary_trees'¶

Binary Trees¶

Related Topics

This Page