CP164 Final: Binary Search Trees
Binary Search Trees
A binary tree is a non-linear data structure. A binary tree is either the empty tree or a node
that has left and right subtrees that are binary trees. (This is a recursive definition.)
A binary search tree (BST) is a special form of a binary tree. Its properties are:
• a BST is a binary tree
• every node in a BST has a key value
• for each node N, the keys in the left subtree of N are less than the key of N, and the keys in
the right subtree of N are greater than the key of N
• keys are unique
•
Although BSTs can be implemented with an array, it is generally easier conceptually to
implement them with a linked structure. Each node in the linked structure contains two
links, left and right, which point to the left and right subtrees of any given node. The node
also contains the height of the node's subtree.
Sample BST
Note that the empty left and right pointers actually point to None. They have been left out so
as not to clutter the drawing.
The _BSTNode Class
Each BST node is only slightly more complex than a singly linked node. Instead of a next
node pointer, each node contains a copy of the value it stores, pointers to its left and right
children, if any, and the height of its subtree. (The height of any subtree is defined as the
maximum height of its children, plus one.)
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
A binary tree is a non-linear data structure. A binary tree is either the empty tree or a node that has left and right subtrees that are binary trees. (this is a recursive definition. ) A binary search tree (bst) is a special form of a binary tree. Although bsts can be implemented with an array, it is generally easier conceptually to implement them with a linked structure. Each node in the linked structure contains two links, left and right, which point to the left and right subtrees of any given node. The node also contains the height of the node"s subtree. Note that the empty left and right pointers actually point to none. They have been left out so as not to clutter the drawing. Each bst node is only slightly more complex than a singly linked node. Preconditions: value - data for the node (?)
