![]() The implementation of the methods uses the pseudocode from Cormens "Introduction to Algorithms". transplant(self, u, v) replaces subtree u with subtree v and is needed as helper method when deleting nodes.delete(k) deletes the node with key k in the tree. ![]() insert(k) inserts a node with key k in the tree.The class BST implements the methods to create a binary search tree. The method _init_ initializes the class on construction, the methods to_string and print are used for testing.Ĭlass TreeNode: def _init_(self, key): self.key = key self.parent = None self.left = None self.right = None def to_string(self): return str(self.key) def print(self): print("TreeNode: %d" % (self.key)) n10 = TreeNode(10) n5 = TreeNode(5) n14 = TreeNode(14) # Create tree by linking the tree nodes n5.parent = n10 n14.parent = n10 n10.left = n5 # left child n10.right = n14 # right child print() The parent pointer is useful when deleting nodes. right: a pointer to the right child of a nodeĪ binary search tree is created by linking nodes through the left and right pointers either to a left or to a right child.Ī node carries data, these are stored in the key attribute.left: a pointer to the left child of a node.parent: a pointer to the parent of a node.key: the key for the node, which in our case is an integer number.Import numpy as np from numpy.random import seed, randint import ipywidgets as widgets from ipywidgets import interact, interactive_output, HBox, VBox, Layout from IPython.display import display, clear_output, SVG, HTML import graphviz as gv # for visualizing a tree using Digraph from graphviz import Digraph import pydotįirst, the implementation requires a class TreeNode that implements a node of the tree and has four attributes: The packages can be installed as usually using pip or conda commands,įor example pip install graphviz or conda install graphviz. Graphviz is open source graph visualization software, that describes graphs in a simple text language ("DOT"),Īnd creates graph and tree visualizations in a number of image formats and as PDF.įor creating an interactive GUI in Jupyter Notebook we need the classes and methods of the ipywidgets-package,Īs well as graphviz and pydot for the tree visualization. Python, Anaconda (with Jupyter Notebook), Graphviz. The nodes of a binary search tree are created using the class TreeNode.īinary search trees are created, modified and visualized using the methods of the class BST.īefore you start, the following tools must be installed on your computer: Single nodes are deleted using the Delete button, the entire tree is reset by using the Reset button. Or by creating an entire tree from random numbers using the button Random. You can create a new tree either step by step, by entering new keys in the Enter key field and then clicking "Insert", (self-balancing trees constructed by using a balancing factor and rotating the tree as needed to restore the balance), the The BSTLearner app / Jupyter Notebook visualization has three tabs, the first one for binary search trees, the second one for AVL trees ![]()
0 Comments
Leave a Reply. |