The order statistic tree for use in arrays allows you to append a new element to the array, to insert an element before any element in the array, and to remove any element from the array, so that the relative order of the array remains unchanged.
A = {4,9,8,5,5}
Remove A[3], A = {4,9,8,5}
The tree can be skewed, but the red black rules work just as well on
this tree as they do on a regular tree.
We normally use red-black trees on data we wanted to keep sorted (a binary search tree). Nodes with smaller key values are on the left. nodes with larger key values are on the right.
However, the red-black rules DO NOT even look at the key value of a node. You can implement a red black structure on a tree without key fields, such as an order statistic tree. So, the tree will never get too skewed. Inserting, appending, removing, lookup all take lg (n) time.
Now a REAL array does lookup in constant time. Inserting, and removing take n time. However, a REAL array is not adaptive for space. If you initialize it for 50 items, and you only use 30, you have 20 wasted elements. If you need 51 items, you're out of luck.
Since lg n time is essentially unnoticeable unless n is quite large, this is almost as efficient as a regular array, and since trees can be implemented as linked lists, a list-based programming language can handle arrays "almost" as efficiently as one using arrays directly.
C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe" -K full
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Welcome to GNU CLISP 2.49 (2010-07-07)
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010
Type :h and hit Enter for context help.
[1]> (load "split.lisp")
*** - LOAD: A file with name split.lisp does not exist
The following restarts are available:
ABORT :R1 Abort main loop
Break 1 [2]> abort
[3]> (quit)
Bye.
C:\Users\apoe\Desktop\cs556-01-24w>dir
Volume in drive C is Windows
Volume Serial Number is ECD8-6666
Directory of C:\Users\apoe\Desktop\cs556-01-24w
03/13/2024 11:26 AM .
03/13/2024 11:26 AM ..
02/26/2024 01:44 PM 7,616 notes20240226.txt
03/11/2024 12:41 PM notes20240311
02/26/2024 01:28 PM 2,261 tree.lisp
03/13/2024 11:26 AM 750 Unconfirmed 753019.crdownload
03/01/2024 11:12 AM 157,659,013 video1177366364.mp4
03/13/2024 08:33 AM 146,059,542 video1494951903.mp4
5 File(s) 303,729,182 bytes
3 Dir(s) 358,361,407,488 bytes free
C:\Users\apoe\Desktop\cs556-01-24w>clisp
C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe" -K full
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Welcome to GNU CLISP 2.49 (2010-07-07)
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010
Type :h and hit Enter for context help.
[1]> (load "split.lisp")
;; Loading file split.lisp ...
;; Loaded file split.lisp
T
[2]> (setf mylist (list 4 8 2 1 0 -1 4 5 6 8 3 2 1))
(4 8 2 1 0 -1 4 5 6 8 3 2 1)
[3]> (full-merge-sort (list mylist))
NIL
[4]> mylist
(4 4 5 6 8 8)
[5]> (quit)
Bye.
C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe" -K full
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Welcome to GNU CLISP 2.49 (2010-07-07)
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010
Type :h and hit Enter for context help.
[1]> (setf arr1 (make-array (list 5)))
#(NIL NIL NIL NIL NIL)
[2]> (setf (aref arr1 3) 17)
17
[3]> arr1
#(NIL NIL NIL 17 NIL)
[4]> (setf arr1 (make-array (list 8 8)))
#2A((NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL))
[5]> (setf (aref arr2 6 1) "HEY")
*** - LET*: variable ARR2 has no value
The following restarts are available:
USE-VALUE :R1 Input a value to be used instead of ARR2.
STORE-VALUE :R2 Input a new value for ARR2.
ABORT :R3 Abort main loop
Break 1 [6]> abort
[7]> (setf (aref arr1 6 1) "HEY")
"HEY"
[8]> arr1
#2A((NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL "HEY" NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL))
[9]> (setf arr2 (make-array (list 3 2 4)))
#3A(((NIL NIL NIL NIL) (NIL NIL NIL NIL))
((NIL NIL NIL NIL) (NIL NIL NIL NIL))
((NIL NIL NIL NIL) (NIL NIL NIL NIL)))
[10]>