13-15 Flashcards
What is a BST and what are some key functions?
BSTs are pointer based data structures that lend themselves to storing fluctuating data, it is either the empty tree or a root node containing a key field and datat fiels, a left and a right subtree. They can be efficient to search as long as they are balanced, hence a self-balancing feature is useful.
A BST should support the operations of insert, search, and delete, but also many other useful operations. E.g BST to sort data, priority queue, in-order successor/processor of a key, traversal of the data in various orders.
How does deletion in a BST work?
For BST deletion a recursive algorithm is used. If the deleted node has no children or one child this is easy as we can just delete it and move the subtree up. We need to change the links when we do this.
If there are two children we go either right or left and then the opposite direction until we hit the first root with no children in the second direction. (e.g smallest element on the right, or largest on the left.
What is the in-order predecessor in a BST
If it exists, the in-order predecessor will usually be in the left subtree of a root x, and will have the maximum key value of that subtree. If this subtree is empty however it will be the first node in which x is in the right subtree.
What are some examples of self balancing BSTs?
RBTs, AVL, splay, tries.
What properties does a RBT have?
A RBT has the following properties :
1. Every node is either red or black
2. The root is black.
3. All dummy leaves are black (null subtrees).
4. 4.If a node is red, the roots of both its subtrees are black.
5. For each node all paths from the node to the leaves contains the same number of black nodes (includes the dummy leaves).
As long as these properties are maintained the tree is typically balanced.
What is the black height of a node?
The black height of a node is the number of black nodes on the path of that node to the leaf, not including the node, but including the dummy leaves.
What is the maximum number of nodes in an RBT?
The maximum number of nodes in a red black tree is greater than or equal to (2^k) -1, where k is the maximum black height.
What can we do if the red black nature of a tree is ruined?
If adding an item to the red black tree ruins the red black nature we can do a rotation, this involves moving a root so that it keeps its left subtree but its right rubtree becomes the left subtree of a neighbouring subtree, this neighbouring subtree keeps its right subtree and the parents of the two nodes changes. (This could be the opposite way around).
When are Hash tables useful? When are they not?
If maximum size of the table is known beforehand, and if emphasis is on insertion and retrieval.
If we need to do lots of deletions/traversals, or dynamic storage allocation then pointer based structures are better.
what are inorder, preorder and postorder traversals?
Inorder: left, root, right
preorder: root, left , right
postorder: left, right, root
What is sorting using a BST similar to?
quicksort. Once built we can use in-order traversal to print the data in sorted order.
