Term
| Four different ways a binary tree can be stored. |
|
Definition
| _info, left pointer, right pointer; _info, left index, right index; generalized list; in-order, pre-order representation |
|
|
Term
| Preorder traversal of a binary tree |
|
Definition
| Start at root, go down left subtree first, then right subtree |
|
|
Term
| Postorder traversal of a binary tree |
|
Definition
| traverse left subtree, traverse right subtree, visit root |
|
|
Term
| inorder traversal of binary tree |
|
Definition
| traverse left subtree, visit root, traverse right subtree |
|
|
Term
| How can a remove operation be performed on a binary search tree? |
|
Definition
| Let x be the node to be deleted. 1. If x is a leaf node set _info = NULL 2. If x has only one child, copy the contents of that child into x. 3. If x has two children, replace the _info field with the smallest value in the right subtree of x and perform a remove operation on the node containing this smallest value. |
|
|
Term
|
Definition
| Move the node to the root by rotations |
|
|
Term
|
Definition
| BST, height balance - balance factor, height of left subtree minus height of right subtree. For an AVL tree the balance factor of every node is either a -1, 0, or 1. If it is an AVL tree, then height is no more than O(log_2 n) |
|
|
Term
| Red-Black tree description |
|
Definition
| BST which keeps itself balanced in height by labeling each tree(or subtree) as either red or black, and restricting the red/black relationships between parents and children |
|
|
Term
| Complexity of sorting using AVL tree and why? |
|
Definition
| O(NlogN), where N is the number of numbers to be sorted; insert one number at a time, each insertion will cost O(logN) time since, O(logN) is the height of an AVL tree. After inserting all the elements, perform an inorder traversal which will take O(N) time and hence the total time complexity is O(NlogN) |
|
|
Term
| Which is better, red-black tree or AVL tree? Why? |
|
Definition
| Red-black is better in terms of storage since it requires one bit for color and AVL tree requires two bits for storing the balance factor. AVL has smaller hidden constant in the O(logN) |
|
|
Term
| Height-balanced conditions for R/B tree |
|
Definition
1. An empty tree is black
2. An empty tree that becomes non-empty becomes red
3. A red tree never has a red subtree
4. The number of black trees along a path from root to a leaf is the same along the path from the root to any other leaf. |
|
|
Term
| Infix to postfix algortim |
|
Definition
1. S <- createStack()
2. get first token T
3.while T is a valid token
4. if T is an operand then
5. print T
6. else
7. while S not empty and (precendence(T) <= precedence(element at top of S))
8. pop and print the element
9. endwhile
10. push T on the stck
11. endif
12. get the next token T
13.endwhile
14.while stack not empty
15. pop and print the element
16.endwhile |
|
|
Term
|
Definition
| circle, enqueue increments the end, wrapping to front if necessary, dequeue increments first |
|
|
Term
|
Definition
Algorithm Radix_Sort (S)
//S is array of int to be sorted
1. Create an array of queues A of size 10
2. d <- number of digits in number from S that contains most digits
3. k <- 1
4.for i from 1 to d
5. for j from 0 to S.length-1
6. A[(S[j] / k) mod 10 ].enQueue(S[j]);
7. endfor
8. k <- k*10
9. p <- 0
10. for j from 0 to 9
11. while A[j] is not empty
12. S[p++] <- A[j].deQueue
13. endwhile
14. endfor
15.endfor |
|
|
Term
|
Definition
Max height of a BT with n nodes = n
Min height of a BT with n nodes = log_2 n |
|
|
Term
|
Definition
| has operations as nodes as well |
|
|
Term
|
Definition
| splay the node you found, otherwise splay the leaf node |
|
|
Term
|
Definition
| splay the node you inserted |
|
|
Term
|
Definition
| splay the parent of the node you removed |
|
|
Term
|
Definition
h <= 2xlog_2(n+1) + 1
height <= O(log_2 n) |
|
|
Term
| Red-Black number of nodes |
|
Definition
| Minimum number of nodes in the tree is 2^b - 1 (b is the black height) |
|
|
Term
|
Definition
BST: self-adjusting BST
find - O(h) ~ O(n) O(log_2 n)
insert - O(h) ~ O(n) O(log_2 n)
remove- O(h) ~ O(n) O(log_2 n) |
|
|
