text:
Apple II

The Apple II series of microcomputers was initially designed by Steve Wozniak, manufactured by Apple Computer (now Apple Inc.), and launched in 1977 with the Apple II model that gave the series its name. It was followed by the Apple II Plus, Apple IIe, Apple IIc, and Apple IIc Plus, with the 1983 IIe being the most popular. The name is trademarked with square brackets as Apple ][, then, beginning with the IIe, as Apple //. In terms of ease of use, features, and expandability, the Apple II was a major advancement over its predecessor, the Apple I, a limited-production bare circuit board computer for electronics hobbyists.

The Apple II computers are based on the 6502 8-bit processor and can display text and two resolutions of color graphics. A software-controlled speaker provides one channel of low-fidelity audio. A model with more advanced graphics and sound and a 16-bit processor, the Apple II GS, was added in 1986. It remained compatible with earlier Apple II models, but the II GS has more in common with mid-1980s systems like the Atari ST, Amiga, and Acorn Archimedes.

The Apple II was first sold on June 10, 1977. By the end of production in 1993, somewhere between five and six million Apple II series computers (including about 1.25 million Apple II GS models) had been produced. The Apple II was one of the longest running mass-produced home computer series, with models in production for just under 17 years.

The Apple II became one of several recognizable and successful computers during the 1980s and early 1990s, although this was mainly limited to the US. It was aggressively marketed through volume discounts and manufacturing arrangements to educational institutions, which made it the first computer in widespread use in American secondary schools, displacing the early leader Commodore PET. The effort to develop educational and business software for the Apple II, including the 1979 release of the popular VisiCalc spreadsheet, made the computer especially popular with business users and families.

Despite the introduction of the Motorola 68000-based Macintosh in 1984, the Apple II series still reportedly accounted for 85% of the company's hardware sales in the first quarter of fiscal 1985. Apple continued to sell Apple II systems alongside the Macintosh until terminating the II GS in December 1992 and the IIe in November 1993. The last II-series Apple in production, the IIe card for Macintoshes, was discontinued on October 15, 1993. The total Apple II sales of all of its models during its 16-year production run were about 6 million units, with the peak occurring in 1983 when 1 million were sold.

Hardware

Unlike preceding home microcomputers, The Apple II was sold as a finished consumer appliance rather than as a kit (unassembled or preassembled). Apple marketed the Apple II as a durable product, including a 1981 ad in which an Apple II survived a fire started when a cat belonging to one early user knocked over a lamp.

All the machines in the series, except the IIc, share similar overall design elements. The plastic case was designed to look more like a home appliance than a piece of electronic equipment, and the case can be opened without the use of tools. All models in the Apple II series have a built-in keyboard, with the exception of the II GS which has a separate keyboard.

Apple IIs have color and high-resolution graphics modes, sound capabilities and a built-in BASIC programming language. The motherboard holds eight expansion slots and an array of random access memory (RAM) sockets that can hold up to 48 kilobytes. Over the course of the Apple II series' life, an enormous amount of first- and third-party hardware was made available to extend the capabilities of the machine. The IIc was designed as a compact, portable unit, not intended to be disassembled, and cannot use most of the expansion hardware sold for the other machines in the series.

Software
The original Apple II has the operating system in ROM along with a BASIC variant called Integer BASIC. Apple eventually released Applesoft BASIC, a more advanced variant of the language which users can run instead of Integer BASIC. The Apple II series eventually supported over 1,500 software programs.

When the Disk II floppy disk drive was released in 1978, a new operating system, Apple DOS, was commissioned from Shepardson Microsystems and developed by Paul Laughton, adding support for the disk drive. The final and most popular version of this software was Apple DOS 3.3.

Apple DOS was superseded by ProDOS, which supported a hierarchical filesystem and larger storage devices. With an optional third-party Z80-based expansion card, the Apple II could boot into the CP/M operating system and run WordStar, dBase II, and other CP/M software. With the release of MousePaint in 1984 and the Apple II GS in 1986, the platform took on the look of the Macintosh user interface, including a mouse.

Much commercial Apple II software shipped on self-booting disks and does not use standard DOS disk formats. This discouraged the copying or modifying of the software on the disks, and improved loading speed.

Apple II

The first Apple II computers went on sale on June 10, 1977 with a MOS Technology 6502 (later Synertek) microprocessor running at 1.023 MHz, 4 KB of RAM, an audio cassette interface for loading programs and storing data, and the Integer BASIC programming language built into the ROMs. The video controller displayed 40 columns by 24 lines of monochrome, upper-case-only (the original character set matches ASCII characters 0x20 to 0x5F) text on the screen, with NTSC composite video output suitable for display on a TV monitor, or on a regular TV set by way of a separate RF modulator. The original retail price of the computer was US$1298 (with 4 KB of RAM) and US$2638 (with the maximum 48 KB of RAM). To reflect the computer's color graphics capability, the Apple logo on the casing was represented using rainbow stripes, which remained a part of Apple's corporate logo until early 1998. The earliest Apple IIs were assembled in Silicon Valley, and later in Texas; printed circuit boards were manufactured in Ireland and Singapore.

An external $5 1/4$-inch floppy disk drive, the Disk II, attached via a controller card that plugged into one of the computer's expansion slots (usually slot 6), was used for data storage and retrieval to replace cassettes. The Disk II interface, created by Steve Wozniak, was regarded as an engineering masterpiece for its economy of electronic components.

Rather than having a dedicated sound-synthesis chip, the Apple II had a toggle circuit that could only emit a click through a built-in speaker or a line out jack; all other sounds (including two, three and, eventually, four-voice music and playback of audio samples and speech synthesis) were generated entirely by software that clicked the speaker at just the right times.

The Apple II's multiple expansion slots permitted a wide variety of third-party devices, including Apple II peripheral cards such as serial controllers, display controllers, memory boards, hard disks, networking components, and realtime clocks. There were plug-in expansion cards – such as the Z-80 SoftCard – that permitted the Apple to use the Z80 processor and run a multitude of programs developed under the CP/M operating system, including the dBase II database and the WordStar word processor. There was also a third-party 6809 card that would allow OS-9 Level One to be run. Third-party sound cards greatly improved audio capabilities, allowing simple music synthesis and text-to-speech functions. Eventually, Apple II accelerator cards were created to double or quadruple the computer's speed.

Rod Holt designed the Apple II's power supply. He employed a switched-mode power supply design, which was far smaller and generated less unwanted heat than the linear power supply some other home computers used.

The original Apple II was discontinued at the start of 1981, superseded by the Apple II+.

Apple II Plus

The Apple II Plus, introduced in June 1979,   included the Applesoft BASIC programming language in ROM. This Microsoft-authored dialect of BASIC, which was previously available as an upgrade, supported floating-point arithmetic, and became the standard BASIC dialect on the Apple II series (though it ran at a noticeably slower speed than Steve Wozniak's Integer BASIC).

Except for improved graphics and disk-booting support in the ROM, and the removal of the 2k 6502 assembler to make room for the floating point BASIC, the II+ was otherwise identical to the original II in terms of electronic functionality. There were small differences in the physical appearance and keyboard. RAM prices fell during 1980–81 and all II+ machines came from the factory with a full 48k of memory already installed.

Apple II Europlus and J-Plus

After the success of the first Apple II in the United States, Apple expanded its market to include Europe, Australia and the Far East in 1979, with the Apple II Europlus (Europe, Australia) and the Apple II J-Plus (Japan). In these models, Apple made the necessary hardware, software and firmware changes in order to comply to standards outside of the US.

Apple IIe
The Apple II Plus was followed in 1983 by the Apple IIe, a cost-reduced yet more powerful machine that used newer chips to reduce the component count and add new features, such as the display of upper and lowercase letters and a standard 64 KB of RAM.

The IIe RAM was configured as if it were a 48 KB Apple II Plus with a language card. The machine had no slot 0, but instead had an auxiliary slot that could accept a 1 KB memory card to enable the 80-column display. This card contained only RAM; the hardware and firmware for the 80-column display was built into the Apple IIe. An "extended 80-column card" with more memory increased the machine's RAM to 128 KB.

The Apple IIe was the most popular machine in the Apple II series. It has the distinction of being the longest-lived Apple computer of all time—it was manufactured and sold with only minor changes for nearly 11 years. The IIe was the last Apple II model to be sold, and was discontinued in November 1993.

During its lifespan two variations were introduced: the Apple IIe Enhanced (four replacement chips to give it some of the features of the later model Apple IIc) and the Apple IIe Platinum (a modernized case color to match other Apple products of the era, along with the addition of a numeric keypad).

Some of the feature of the IIe were carried over from the less successful Apple III, among them the ProDOS operating system.

Apple IIc

The Apple IIc was released in April 1984, billed as a portable Apple II because it could be easily carried due to its size and carrying handle, which could be flipped down to prop the machine up into a typing position. Unlike modern portables, it lacked a built-in display and battery. It was the first of three Apple II models to be made in the Snow White design language, and the only one that used its unique creamy off-white color.

The Apple IIc was the first Apple II to use the 65C02 low-power variant of the 6502 processor, and featured a built-in 5.25-inch floppy drive and 128 KB RAM, with a built-in disk controller that could control external drives, composite video (NTSC or PAL), serial interfaces for modem and printer, and a port usable by either a joystick or mouse. Unlike previous Apple II models, the IIc had no internal expansion slots at all.

Two different monochrome LC displays were sold for use with the IIc's video expansion port, although both were short-lived due to high cost and poor legibility. The IIc had an external power supply that converted AC power to 15 V DC, though the IIc itself will accept between 12 V and 17 V DC, allowing third parties to offer battery packs and automobile power adapters that connected in place of the supplied AC adapter.

Apple II GS

The Apple II GS, released on September 15, 1986, is the penultimate and most advanced model in the Apple II series, and a radical departure from prior models. It uses a 16-bit microprocessor, the 65C816 operating at 2.8 MHz with 24-bit addressing, allowing expansion up to 8 MB of RAM. The graphics are significantly improved, with 4096 colors and new modes with resolutions of 320×200 and 640×400. The audio capabilities are vastly improved, with a built-in music synthesizer that far exceeded any other home computer.

The Apple II GS evolved the platform while still maintaining near-complete backward compatibility. Its Mega II chip contains the functional equivalent of an entire Apple IIe computer (sans processor). This, combined with the 65816's ability to execute 65C02 code directly, provides full support for legacy software, while also supporting 16-bit software running under a new OS.

The OS eventually included a Macintosh-like graphical Finder for managing disks and files and opening documents and applications, along with desk accessories. Later, the II GS gained the ability to read and write Macintosh disks and, through third-party software, a multitasking Unix-like shell and TrueType font support.

The GS includes a 32-voice Ensoniq 5503 DOC sample-based sound synthesizer chip with 64 KB dedicated RAM, 256 KB (or later 1.125 MB) of standard RAM, built-in peripheral ports (switchable between IIe-style card slots and IIc-style onboard controllers for disk drives, mouse, RGB video, and serial devices) and, built-in AppleTalk networking.

Apple IIc Plus

The final Apple II model was the Apple IIc Plus introduced in 1988. It was the same size and shape as the IIc that came before it, but the 5.25-inch floppy drive had been replaced with a $3 1/2$-inch drive, the power supply was moved inside the case, and the processor was a fast 4 MHz 65C02 processor that actually ran 8-bit Apple II software faster than the II GS.

The IIc Plus also featured a new keyboard layout that matched the Platinum IIe and II GS. Unlike the IIe IIc and II GS, the IIc Plus came only in one version (American) and was not officially sold anywhere outside the US. The Apple IIc Plus ceased production in 1990, with its two-year production run being the shortest of all the Apple II computers.

Apple IIe Card
Although not an extension of the Apple II line, in 1990 the Apple IIe Card, an expansion card for the Macintosh LC, was released. Essentially a miniaturized Apple IIe computer on a card (using the Mega II chip from the Apple II GS ), it allowed the Macintosh to run 8-bit Apple IIe software through hardware emulation, with an option to run at roughly double the speed of the original IIe (about 1.8 MHz). However, the video output was emulated in software, and, depending on how much of the screen the currently running program was trying to update in a single frame, performance could be much slower compared to a real IIe. This is due to the fact that writes from the 65C02 on the IIe Card to video memory were caught by the additional hardware on the card, so the video emulation software running on the Macintosh side could process that write and update the video display. But, while the Macintosh was processing video updates, execution of Apple II code would be temporarily halted.

With a breakout cable which connected to the back of the card, the user could attach up to two UniDisk or Apple 5.25 Drives, up to one UniDisk 3.5 drive, and a DE-9 Apple II joystick. Many of the LC's built-in Macintosh peripherals could also be "borrowed" by the card when in Apple II mode, including extra RAM, the Mac's internal 3.5-inch floppy drives, AppleTalk networking, any ProDOS-formatted hard disk partitions, the serial ports, mouse, and real-time clock. The IIe card could not, however, run software intended for the 16-bit Apple II GS.

Advertising, marketing, and packaging
Mike Markkula, a retired Intel marketing manager, provided the early critical funding for Apple Computer. From 1977 to 1981, Apple used the Regis McKenna agency for its advertisements and marketing. In 1981, Chiat-Day acquired Regis McKenna's advertising operations and Apple used Chiat-Day. At Regis McKenna Advertising, the team assigned to launch the Apple II consisted of Rob Janoff, art director, Chip Schafer, copywriter and Bill Kelley, account executive. Janoff came up with the Apple logo with a bite out of it. The design was originally an olive green with matching company logotype all in lower case. Steve Jobs insisted on promoting the color capability of the Apple II by putting rainbow stripes on the Apple logo. In its letterhead and business card implementation, the rounded "a" of the logotype echoed the "bite" in the logo. This logo was developed simultaneously with an advertisement and a brochure; the latter being produced for distribution initially at the first West Coast Computer Faire.

Since the original Apple II, Apple has paid high attention to its quality of packaging, partly because of Steve Jobs' personal preferences and opinions on packaging and final product appearance. All of Apple's packaging for the Apple II series looked similar, featuring much clean white space and showing the Apple rainbow logo prominently. For several years up until the late 1980s, Apple used the Motter Tektura font for packaging, until changing to the Apple Garamond font.

Apple ran the first advertisement for the Apple II, a two-page spread ad titled "Introducing Apple II", in BYTE in July 1977. The first brochure, was entitled "Simplicity" and the copy in both the ad and brochure pioneered "demystifying" language intended to make the new idea of a home computer more "personal." The Apple II introduction ad was later run in the September 1977 issue of Scientific American.

Apple later aired eight television commercials for the Apple II GS, emphasizing its benefits to education and students, along with some print ads.

Clones
The Apple II was frequently cloned, both in the United States and abroad, in a similar way to the IBM PC. According to some sources (see below), more than 190 different models of Apple II clones were manufactured. Most could not be legally imported into the United States. Apple sued and sought criminal charges against clone makers in more than a dozen countries.

Cassette
Originally the Apple II used Compact Cassette tapes for program and data storage. A dedicated tape recorder along the lines of the Commodore Datasette was never produced; Apple recommended using the Panasonic RQ309 in some of its early printed documentation. The uses of common consumer cassette recorders and a standard video monitor or television set (with a third-party RF modulator) made the total cost of owning an Apple II less expensive and helped contribute to the Apple II's success.

Cassette storage may have been inexpensive, but it was also slow and unreliable. The Apple II's lack of a disk drive was "a glaring weakness" in what was otherwise intended to be a polished, professional product. Recognizing that the II needed a disk drive to be taken seriously, Apple set out to develop a disk drive and a DOS to run it. Wozniak spent the 1977 Christmas holidays designing a disk controller that reduced the number of chips used by a factor of 10 compared to existing controllers. Still lacking a DOS, and with Wozniak inexperienced in operating system design, Jobs approached Shepardson Microsystems with the project. On April 10, 1978, Apple signed a contract for $13,000 with Sheperdson to develop the DOS.

Even after disk drives made the cassette tape interfaces obsolete they were still used by enthusiasts as simple one-bit audio input-output ports. Ham radio operators used the cassette input to receive slow scan TV (single frame images). A commercial speech recognition Blackjack program was available, after some user-specific voice training it would recognize simple commands (Hit, stand). Bob Bishop's "Music Kaleidoscope" was a simple program that monitored the cassette input port and based on zero-crossings created color patterns on the screen, a predecessor to current audio visualization plug-ins for media players. Music Kaleidoscope was especially popular on projection TV sets in dance halls.

The OS Disk
Apple and many third-party developers made software available on tape at first, but after the Disk II became available in 1978, tape-based Apple II software essentially disappeared from the market. The initial price of the Disk II drive and controller was US$595, although a $100 off coupon was available through the Apple newsletter "Contact". The controller could handle two drives and a second drive (without controller) retailed for $495.

The Disk II single-sided floppy drive used 5.25-inch floppy disks; double-sided disks could be used, one side at a time, by turning them over and notching a hole for the write protect sensor. The first disk operating systems for the Apple II were DOS 3.1 and DOS 3.2, which stored 113.75 KB on each disk, organized into 35 tracks of 13 256-byte sectors each. After about two years, DOS 3.3 was introduced, storing 140 KB thanks to a minor firmware change on the disk controller that allowed it to store 16 sectors per track. (This upgrade was user-installable as two PROMs on older controllers.) After the release of DOS 3.3, the user community discontinued use of DOS 3.2 except for running legacy software. Programs that required DOS 3.2 were fairly rare; however, as DOS 3.3 was not a major architectural change aside from the number of sectors per track, a program called MUFFIN was provided with DOS 3.3 to allow users to copy files from DOS 3.2 disks to DOS 3.3 disks. It was possible for software developers to create a DOS 3.2 disk which would also boot on a system with DOS 3.3 firmware.

Later, double-sided drives, with heads to read both sides of the disk, became available from third-party companies. (Apple only produced double-sided 5.25-inch disks for the Lisa 1 computer).

On a DOS 3.x disk, tracks 0, 1, and most of track 2 were reserved to store the operating system. (It was possible, with a special utility, to reclaim most of this space for data if a disk did not need to be bootable.) A short ROM program on the disk controller had the ability to seek to track zero – which it did without regard for the read/write head's current position, resulting in the characteristic "chattering" sound of a Disk II boot, which was the read/write head hitting the rubber stop block at the end of the rail – and read and execute code from sector 0. The code contained in there would then pull in the rest of the operating system. DOS stored the disk's directory on track 17, smack in the middle of the 35-track disks, in order to reduce the average seek time to the frequently used directory track. The directory was fixed in size and could hold a maximum of 105 files. Subdirectories were not supported.

Most game publishers did not include DOS on their floppy disks, since they needed the memory it occupied more than its capabilities; instead, they often wrote their own boot loaders and read-only file systems. This also served to discourage "crackers" from snooping around in the game's copy-protection code, since the data on the disk was not in files that could be accessed easily.

Some third-party manufacturers produced floppy drives that could write 40 tracks to most 5.25-inch disks, yielding 160 KB of storage per disk, but the format did not catch on widely, and no known commercial software was published on 40-track media. Most drives, even Disk IIs, could write 36 tracks; a two byte modification to DOS to format the extra track was common.

The Apple Disk II stored 140 KB on single-sided, "single-density" floppy disks, but it was very common for Apple II users to extend the capacity of a single-sided floppy disk to 280 KB by cutting out a second write-protect notch on the side of the disk using a "disk notcher" or hole puncher and inserting the disk flipped over. Double-sided disks, with notches on both sides, were available at a higher price, but in practice the magnetic coating on the reverse of nominally single-sided disks was usually of good enough quality to be used (both sides were coated in the same way to prevent warping, although only one side was certified for use). Early on, diskette manufacturers routinely warned that this technique would damage the read/write head of the drives or wear out the disk faster, and these warnings were frequently repeated in magazines of the day. In practice, however, this method was an inexpensive way to store twice as much data for no extra cost, and was widely used for commercially released floppies as well.

Later, Apple IIs were able to use 3.5-inch disks with a total capacity of 800 KB and hard disks. DOS 3.3 did not support these drives natively; third-party software was required, and disks larger than about 400 KB had to be split up into multiple "virtual disk volumes."

DOS 3.3 was succeeded by ProDOS, a 1983 descendant of the Apple ///'s SOS. It added support for subdirectories and volumes up to 32 MB in size. ProDOS became the Apple II DOS of choice; AppleWorks and other newer programs required it.

Legacy

The Apple II series of computers had an enormous impact on the technology industry and expanded the role of microcomputers in society. The Apple II was the first personal computer many people ever saw. Its price was within the reach of many middle-class families, and a partnership with MECC helped make the Apple II popular in schools. By the end of 1980 Apple had already sold over 100,000 Apple IIs, and at the introduction of the II GS, 3 million models in the range had been sold. However, in other markets, the range saw rather more limited adoption, with only 120,000 units selling in the UK over this nine year period.

The Apple II's popularity bootstrapped the computer game and educational software markets and began the boom in the word processor and computer printer markets. The first spreadsheet application, VisiCalc, was initially released for the Apple II, and many businesses bought them just to run VisiCalc. Its success drove IBM in part to create the IBM PC, which many businesses purchased to run spreadsheet and word processing software, at first ported from Apple II versions.

The Apple II's slots, allowing any peripheral card to take control of the bus and directly access memory, enabled an independent industry of card manufacturers who together created a flood of hardware products that let users build systems that were far more powerful and useful (at a lower cost) than any competing system, most of which were not nearly as expandable and were universally proprietary. The first peripheral card was a blank prototyping card intended for electronics enthusiasts who wanted to design their own peripherals for the Apple II.

Specialty peripherals kept the Apple II in use in industry and education environments for many years after Apple Computer stopped supporting the Apple II. Well into the 1990s every clean-room (the super-clean facility where spacecraft are prepared for flight) at the Kennedy Space Center used an Apple II to monitor the environment and air quality. Most planetariums used Apple IIs to control their projectors and other equipment.

Even the game port was unusually powerful and could be used for digital and analog input and output. The early manuals included instructions for how to build a circuit with only four commonly available components (one transistor and three resistors) and a software routine to drive a common Teletype Model 33 machine. Don Lancaster used the game I/O to drive a LaserWriter printer.

Modern use
Today, emulators for various Apple II models are available to run Apple II software on macOS, Linux, Microsoft Windows, homebrew enabled Nintendo DS and other operating systems. Numerous disk images of Apple II software are available free over the Internet for use with these emulators. AppleWin and MESS are among the best emulators compatible with most Apple II images. The MESS emulator supports recording and playing back of Apple II emulation sessions, as does Home Action Replay Page (a.k.a. HARP).

There is still a small annual convention, KansasFest, dedicated to the platform.

In 2017, the band 8 Bit Weapon released the world's first 100% Apple II-based music album entitled, "Class Apples". The album featured dance-oriented cover versions of classical music by Bach, Beethoven, and Mozart recorded directly off the Apple II motherboard.

title: Apple II


text:
Apple III

The Apple III (styled as apple /// or Apple ]|[) is a business-oriented personal computer produced by Apple Computer and released in 1980. Running the Apple SOS operating system, it was intended as the successor to the Apple II, but was largely considered a failure in the market. It was designed to provide key features business users wanted in a personal computer: a true typewriter-style upper/lowercase keyboard (the Apple II only supported uppercase) and an 80-column display.

Work on the Apple III started in late 1978 under the guidance of Dr. Wendell Sander. It had the internal code name of "Sara", named after Sander's daughter. The system was announced on May 19, 1980 and released in late November that year. Serious stability issues required a design overhaul and a recall of the first 14,000 machines produced. The Apple III was formally reintroduced on November 9, 1981.

Damage to the computer's reputation had already been done, however, and it failed to do well commercially. Development stopped, and the Apple III was discontinued on April 24, 1984. Its last successor, the III Plus, was dropped from the Apple product line in September 1985.

An estimated 65,000–75,000 Apple III computers were sold. The Apple III Plus brought this up to approximately 120,000. Apple co-founder Steve Wozniak stated that the primary reason for the Apple III's failure was that the system was designed by Apple's marketing department, unlike Apple's previous engineering-driven projects. The Apple III's failure led Apple to reevaluate its plan to phase out the Apple II, prompting the eventual continuation of development of the older machine. As a result, later Apple II models incorporated some hardware and software technologies of the Apple III.

Design
Steve Wozniak and Steve Jobs expected hobbyists to purchase the Apple II, but because of VisiCalc and Disk II, small businesses purchased 90% of the computers. The Apple III was designed to be a business computer and successor. Though the Apple II contributed to the inspirations of several important business products, such as VisiCalc, Multiplan, and Apple Writer, the computer's hardware architecture, operating system, and developer environment are limited. Apple management intended to clearly establish market segmentation by designing the Apple III to appeal to the 90% business market, leaving the Apple II to home and education users. Management believed that "once the Apple III was out, the Apple II would stop selling in six months", Wozniak said.

The Apple III is powered by a 1.8-megahertz Synertek 6502A or 6502B 8-bit CPU and, like some of the later machines in the Apple II family, uses bank switching techniques to address memory beyond the 6502's traditional 64 KB limit, up to 256 KB in the III's case. Third-party vendors produced memory upgrade kits that allow the Apple III to reach up to 512 KB of random-access memory (RAM). Other Apple III built-in features include an 80-column, 24-line display with upper and lowercase characters, a numeric keypad, dual-speed (pressure-sensitive) cursor control keys, 6-bit (DAC) audio, and a built-in 140-kilobyte 5.25-inch floppy disk drive. Graphics modes include 560x192 in black and white, and 280x192 with 16 colors or shades of gray. Unlike the Apple II, the Disk III controller is part of the logic board.

The Apple III is the first Apple product to allow the user to choose both a screen font and a keyboard layout: either QWERTY or Dvorak. These choices cannot be changed while programs were running, unlike the Apple IIc, which has a keyboard switch directly above the keyboard, allowing the user to switch on the fly.

Software

The Apple III introduced an advanced operating system called Apple SOS, pronounced "apple sauce". Its ability to address resources by name allows the Apple III to be more scalable than the Apple II's addressing by physical location such as. Apple SOS allows the full capacity of a storage device to be used as a single volume, such as the Apple ProFile hard disk drive, and it supports a hierarchical file system. Some of the features and code base of Apple SOS were later adopted into the Apple II's ProDOS and GS/OS operating systems, as well as Lisa 7/7 and Mac OS.

With a starting price of $4,340 (equivalent to $17,356 as of 2024) and a maximum price of $7,800 (equivalent to $31,194 as of 2024), the Apple III was more expensive than many of the CP/M-based business computers that were available at the time. Few software applications other than VisiCalc are available for the computer; according to a presentation at KansasFest 2012, fewer than 50 Apple III-specific software packages were ever published, most shipping when the III Plus was released. Because Apple did not view the Apple III as suitable for hobbyists, it did not provide much of the technical software information that accompanies the Apple II. Originally intended as a direct replacement to the Apple II, it was designed to be backward compatible with Apple II software. However, since Apple did not want to encourage continued development of the II platform, Apple II compatibility exists only in a special Apple II Mode which is limited in its capabilities to the emulation of a basic Apple II Plus configuration with $5 1/4$ of RAM. Special chips were intentionally added to prevent access from Apple II Mode to the III's advanced features such as its larger amount of memory.

Peripherals
The Apple III has four expansion slots, a number that inCider in 1986 called "miserly". , also saying Apple II cards are compatible but risk violating government RFI regulations, and require Apple III-specific device drivers; BYTE stated that "Apple provides virtually no information on how to write them". As with software, Apple provided little hardware technical information with the computer but Apple III-specific products became available, such as one that made the computer compatible with the Apple IIe. Several new Apple-produced peripherals were developed for the Apple III. The original Apple III has a built-in real-time clock, which is recognized by Apple SOS. The clock was later removed from the "revised" model, and was instead made available as an add-on.

Along with the built-in floppy drive, the Apple III can also handle up to three additional external Disk III floppy disk drives. The Disk III is only officially compatible with the Apple III. The Apple III Plus requires an adaptor from Apple to use the Disk III with its DB-25 disk port.

With the introduction of the revised Apple III a year after launch, Apple began offering the ProFile external hard disk system. Priced at $3,499 for 5 MB of storage, it also required a peripheral slot for its controller card.

Backward compatibility
The Apple III has the built-in hardware capability to run Apple II software. In order to do so, an emulation boot disk is required that functionally turns the machine into a standard 48-kilobyte Apple II Plus, until it is powered off. The keyboard, internal floppy drive (and one external Disk III), display (color is provided through the 'B/W video' port) and speaker all act as Apple II peripherals. The paddle and serial ports can also function in Apple II mode, however with some limitations and compatibility issues.

Apple engineers added specialized circuitry with the sole purpose of blocking access to its advanced features when running in Apple II emulation mode. This was done primarily to discourage further development and interest in the Apple II line, and to push the Apple III as its successor. For example, no more than 48 KB of RAM can be accessed, even if the machine has 128 KB of RAM or higher present. Many Apple II programs require a minimum of 64 KB of RAM, making them impossible to run on the Apple III. Similarly, access to lowercase support, 80 columns text, or its more advanced graphics and sound are blocked by this hardware circuitry, making it impossible for even skilled software programmers to bypass Apple's lockout. A third-party company, Titan Technologies, sold an expansion board called the III Plus II that allows Apple II mode to access more memory, a standard game port, and with a later released companion card, even emulate the Apple IIe.

Certain Apple II slot cards can be installed in the Apple III and used in native III-mode with custom written SOS device drivers, including Grappler Plus and Liron 3.5 Controller.

Revisions

After overheating issues were attributed to serious design flaws, a redesigned logic board was introduced in mid-December 1981 – which included a lower power supply requirement, wider circuit traces and better-designed chip sockets. The $3,495 revised model also includes 256 KB of RAM as the standard configuration. The 14,000 units of the original Apple III sold were returned and replaced with the entirely new revised model.

Apple III Plus
Apple discontinued the III in October 1983 because it violated FCC regulations, and the FCC required the company to change the redesigned computer's name. It introduced the Apple III Plus in December 1983 at a price of US$2,995. This newer version includes a built-in clock, video interlacing, standardized rear port connectors, 55-watt power supply, 256 KB of RAM as standard, and a redesigned, Apple IIe-like keyboard.

Owners of the Apple III could purchase individual III Plus upgrades, like the clock and interlacing feature, and obtain the newer logic board as a service replacement. A keyboard upgrade kit, dubbed "Apple III Plus upgrade kit" was also made available – which included the keyboard, cover, keyboard encoder ROM, and logo replacements. This upgrade had to be installed by an authorized service technician.

Design flaws
According to Wozniak, the Apple III "had 100 percent hardware failures". Former Apple executive Taylor Pohlman stated that:

"There was way too short a time frame in manufacturing and development. When the decision was made to announce, there were only three Apple IIIs in existence, and they were all wire-wrapped boards.

The case of the Apple III had long since been set in concrete, so they had a certain size logic board to fit the circuits on ... They went to three different outside houses and nobody could get a layout that would fit on the board.

They used the smallest line circuit boards that could be used. They ran about 1,000 of these boards as preproduction units to give to the dealers as demonstration units. They really didn't work ... Apple swapped out the boards. The problem was, at this point there were other problems, things like chips that didn't fit. There were a million problems that you would normally take care of when you do your preproduction and pilot run. Basically, customers were shipped the pilot run."

Jobs insisted on the idea of having no fan or air vents, in order to make the computer run quietly. He would later push this same ideology onto almost all Apple models he had control of, from the Apple Lisa and Macintosh 128K to the iMac. To allow the computer to dissipate heat, the base of the Apple III was made of heavy cast aluminum, which supposedly acts as a heat sink. One advantage to the aluminum case was a reduction in RFI (Radio Frequency Interference), a problem which had plagued the Apple II series throughout its history. Unlike the Apple II, the power supply was mounted – without its own shell – in a compartment separate from the logic board. The decision to use an aluminum shell ultimately led to engineering issues which resulted in the Apple III's reliability problems. The lead time for manufacturing the shells was high, and this had to be done before the motherboard was finalized. Later, it was realized that there was not enough room on the motherboard for all of the components unless narrow traces were used.

Many Apple IIIs were thought to have failed due to their inability to properly dissipate heat. inCider stated in 1986 that "Heat has always been a formidable enemy of the Apple ///", and some users reported that their Apple IIIs became so hot that the chips started dislodging from the board, causing the screen to display garbled data or their disk to come out of the slot "melted". BYTE wrote, "the integrated circuits tended to wander out of their sockets". It has been rumored Apple advised customers to tilt the front of the Apple III six inches above the desk and then drop it to reseat the chips as a temporary solution. Other analyses blame a faulty automatic chip insertion process, not heat.

Case designer Jerry Manock denied the design flaw charges, insisting that tests proved that the unit adequately dissipated the internal heat. The primary cause, he claimed, was a major logic board design problem. The logic board used "fineline" technology that was not fully mature at the time, with narrow, closely spaced traces. When chips were "stuffed" into the board and wave-soldered, solder bridges would form between traces that were not supposed to be connected. This caused numerous short circuits, which required hours of costly diagnosis and hand rework to fix. Apple designed a new circuit board with more layers and normal-width traces. The new logic board was laid out by one designer on a huge drafting board, rather than using the costly CAD-CAM system used for the previous board, and the new design worked.

Earlier Apple III units came with a built-in real time clock. The hardware, however, would fail after prolonged use. Assuming that National Semiconductor would test all parts before shipping them, Apple did not perform this level of testing. Apple was soldering chips directly to boards and could not easily replace a bad chip if one was found. Eventually, Apple solved this problem by removing the real-time clock from the Apple III's specification rather than shipping the Apple III with the clock pre-installed, and then sold the peripheral as a level 1 technician add-on.

BASIC
Microsoft and Apple each developed their own versions of BASIC for the Apple III. Apple III Microsoft BASIC was designed to run on the CP/M platform available for the Apple III. Apple Business BASIC shipped with the Apple III. Donn Denman ported Applesoft BASIC to SOS and reworked it to take advantage of the extended memory of the Apple III.

Both languages introduced a number of new or improved features over Applesoft BASIC. Both languages replaced Applesoft's single-precision floating-point variables using 5-byte storage with the somewhat-reduced-precision 4-byte variables, while also adding a larger numerical format. Apple III Microsoft BASIC provides double-precision floating-point variables, taking 8 bytes of storage, while Apple Business BASIC offers an extra-long integer type, also taking 8 bytes for storage. Both languages also retain 2-byte integers, and maximum 255-character strings.

Other new features common to both languages include:
 * Incorporation of disk-file commands within the language.
 * Operators for MOD and for integer-division.
 * An optional ELSE clause in IF...THEN statements.
 * HEX$ function for hexadecimal-format output.
 * INSTR function for finding a substring within a string.
 * PRINT USING statement to control format of output. Apple Business BASIC had an option, in addition to directly specifying the format with a string expression, of giving the line number where an IMAGE statement gave the formatting expression, similar to a FORMAT statement in FORTRAN.

Some features work differently in each language:

Microsoft BASIC additional features

 * INPUT$ function to replace Applesoft's GET command.
 * LINE INPUT statement to input an entire line of text, regardless of punctuation, into a single string variable.
 * LPRINT and LPRINT USING statements to automatically direct output to paper.
 * LSET and RSET statements to left- or right-justify a string expression within a given string variable's character length.
 * OCT$ function for output, and "&"- or "&O"-formatted expressions, for manipulating octal notation.
 * SPACE$ function for generating blank spaces outside of a PRINT statement, and STRING$ function to do likewise with any character.
 * WHILE...WEND statements, for loop structures built on general Boolean conditions without an index variable.
 * Bitwise Boolean (16-bit) operations (AND, OR, NOT), with additional operators XOR, EQV, IMP.
 * Line number specification in the RESTORE command.
 * RESUME options of NEXT (to skip to the statement after that which caused the error) or a specified line number (which replaces the idea of exiting error-handling by GOTO-line, thus avoiding Applesoft II's stack error problem).
 * Multiple parameters in user-defined (DEF FN) functions.
 * A return to the old Applesoft One concept of having multiple USR functions at different addresses, by establishing ten different USR functions, numbered USR0 to USR9, with separate DEF USRx statements to define the address of each. The argument passed to a USRx function can be of any specific type, including string. The returned value can also be of any type, by default the same type as the argument passed.

There is no support for graphics provided within the language, nor for reading analog controls or buttons; nor is there a means of defining the active window of the text screen.

Business BASIC additional features
Apple Business BASIC eliminates all references to absolute memory addresses. Thus, the POKE command and PEEK function were not included in the language, and new features replaced the CALL statement and USR function. The functionality of certain features in Applesoft that had been achieved with various PEEK and POKE locations is now provided by:
 * BUTTON function to read game-controller buttons
 * WINDOW statement to define the active window of the text screen by its coordinates
 * KBD, HPOS, and VPOS system variables

External binary subroutines and functions are loaded into memory by a single INVOKE disk-command that loads separately-assembled code modules. A PERFORM statement is then used to call an INVOKEd procedure by name, with an argument-list. INVOKEd functions would be referenced in expressions by EXFN. (floating-point) or EXFN%. (integer), with the function name appended, plus the argument-list for the function.

Graphics are supported with an INVOKEd module, with features including displaying text within graphics in various fonts, within four different graphics modes available on the Apple III.

Reception
"[W]e probably put $100 million in advertising, promotion, and research and development into a product that was 3 percent of our revenues. In that same time frame, think what we could have done to improve the Apple II, or how much could have been done by Apple to give us products in IBM's market."

Despite devoting the majority of its R&D to the Apple III and so ignoring the II that for a while dealers had difficulty in obtaining the latter, the III's technical problems made marketing the computer difficult. Ed Smith, who after designing the APF Imagination Machine worked as a distributor's representative, described the III as "a complete disaster". He recalled that he "was responsible for going to every dealership, setting up the Apple III in their showroom, and then explaining to them the functions of the Apple III, which in many cases didn't really work".

Sales
Pohlman reported that Apple was only selling 500 units a month by late 1981, mostly as replacements. The company was able to eventually raise monthly sales to 5,000, but the IBM PC's successful launch had encouraged software companies to develop for it instead, prompting Apple to shift focus to the Lisa and Macintosh. The PC almost ended sales of the Apple III, the most closely comparable Apple computer model. By early 1984, sales were primarily to existing III owners, Apple itself—its 4,500 employees were equipped with some 3,000-4,500 units—and some small businesses. Apple finally discontinued the Apple III series on April 24, 1984, four months after introducing the III Plus, after selling only 65,000-75,000 units and replacing 14,000 defective units.

Jobs said that the company lost "infinite, incalculable amounts" of money on the Apple III. Wozniak estimated that Apple had spent $100 million on the III, instead of improving the II and better competing against IBM. Pohlman claimed that there was a "stigma" at Apple associated with having contributed to the computer. Most employees who worked on the III reportedly left Apple.

Legacy
The file system and some design ideas from Apple SOS, the Apple III's operating system, were part of Apple ProDOS and Apple GS/OS, the major operating systems for the Apple II following the demise of the Apple III, as well as the Apple Lisa, which was the de facto business-oriented successor to the Apple III. The hierarchical file system influenced the evolution of the Macintosh: while the original Macintosh File System (MFS) was a flat file system designed for a floppy disk without subdirectories, subsequent file systems were hierarchical. By comparison, the IBM PC's first file system (again designed for floppy disks) was also flat and later versions (designed for hard disks) were hierarchical.

In popular culture
At the start of the Walt Disney Pictures film TRON, lead character Kevin Flynn (played by Jeff Bridges) is seen hacking into the ENCOM mainframe using an Apple III.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Apple III


text:
AVL tree

In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take $O(log n)$ time in both the average and worst cases, where $$n$$ is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information". It is the oldest self-balancing binary search tree data structure to be invented.

AVL trees are often compared with red–black trees because both support the same set of operations and take $$\text{O}(\log n)$$ time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither weight-balanced nor $$\mu$$-balanced for any $$\mu\leq\tfrac{1}{2}$$; that is, sibling nodes can have hugely differing numbers of descendants.

Balance factor
In a binary tree the balance factor of a node X is defined to be the height difference

 * $$ \text{BF}(X) := \text{Height}(\text{RightSubtree}(X)) - \text{Height}(\text{LeftSubtree}(X)) $$

of its two child sub-trees rooted by node X.

A node X with $$\text{BF}(X)<0$$ is called "left-heavy", one with $$\text{BF}(X)>0$$ is called "right-heavy", and one with $$\text{BF}(X)=0$$ is sometimes simply called "balanced".

Properties
Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height – it is not necessary to know the absolute height. For holding the AVL balance information, two bits per node are sufficient.

The height $$h$$ (counted as the maximal number of levels) of an AVL tree with $$n$$ nodes lies in the interval:
 * $$\log_2(n+1) \le h < \log_\varphi(n+2) + b$$

where $$\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618$$ is the golden ratio and $$b := \frac{\log_2 5}{2 \log_2 \varphi} - 2 \approx \; -0.3277 .$$ This is because an AVL tree of height $$h$$ contains at least $$F_{h+2}-1$$ nodes where $$\{F_n\}_{n\in\N}$$ is the Fibonacci sequence with the seed values $$F_1=F_2=1 .$$

Operations
Read-only operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications have to observe and restore the height balance of the sub-trees.

Searching
Searching for a specific key in an AVL tree can be done the same way as that of any balanced or unbalanced binary search tree. In order for search to work effectively it has to employ a comparison function which establishes a total order (or at least a total preorder) on the set of keys. The number of comparisons required for successful search is limited by the height $h$ and for unsuccessful search is very close to $h$, so both are in $O(log n)$.

Traversal
As a read-only operation the traversal of an AVL tree functions the same way as on any other binary tree. Exploring all $n$ nodes of the tree visits each link exactly twice: one downward visit to enter the subtree rooted by that node, another visit upward to leave that node's subtree after having explored it.

Once a node has been found in an AVL tree, the next or previous node can be accessed in amortized constant time. Some instances of exploring these "nearby" nodes require traversing up to $h ∝ log(n)$ links (particularly when navigating from the rightmost leaf of the root's left subtree to the root or from the root to the leftmost leaf of the root's right subtree; in the AVL tree of figure 1, navigating from node P to the next-to-the-right node Q takes 3 steps). Since there are $n−1$ links in any tree, the amortized cost is $2×(n−1)/n$, or approximately 2.

Insert
When inserting a node into an AVL tree, you initially follow the same process as inserting into a Binary Search Tree. If the tree is empty, then the node is inserted as the root of the tree. If the tree is not empty, then we go down the root, and recursively go down the tree searching for the location to insert the new node. This traversal is guided by the comparison function. In this case, the node always replaces a NULL reference (left or right) of an external node in the tree i.e., the node is either made a left-child or a right-child of the external node.

After this insertion, if a tree becomes unbalanced, only ancestors of the newly inserted node are unbalanced. This is because only those nodes have their sub-trees altered. So it is necessary to check each of the node's ancestors for consistency with the invariants of AVL trees: this is called "retracing". This is achieved by considering the balance factor of each node.

Since with a single insertion the height of an AVL subtree cannot increase by more than one, the temporary balance factor of a node after an insertion will be in the range [–2,+2]. For each node checked, if the temporary balance factor remains in the range from –1 to +1 then only an update of the balance factor and no rotation is necessary. However, if the temporary balance factor is ±2, the subtree rooted at this node is AVL unbalanced, and a rotation is needed. With insertion as the code below shows, the adequate rotation immediately perfectly rebalances the tree.

In figure 1, by inserting the new node Z as a child of node X the height of that subtree Z increases from 0 to 1.

The height of the subtree rooted by Z has increased by 1. It is already in AVL shape.
 * Invariant of the retracing loop for an insertion

In order to update the balance factors of all nodes, first observe that all nodes requiring correction lie from child to parent along the path of the inserted leaf. If the above procedure is applied to nodes along this path, starting from the leaf, then every node in the tree will again have a balance factor of −1, 0, or 1.

The retracing can stop if the balance factor becomes 0 implying that the height of that subtree remains unchanged.

If the balance factor becomes ±1 then the height of the subtree increases by one and the retracing needs to continue.

If the balance factor temporarily becomes ±2, this has to be repaired by an appropriate rotation after which the subtree has the same height as before (and its root the balance factor 0).

The time required is $O(log n)$ for lookup, plus a maximum of $O(log n)$ retracing levels ($O(1)$ on average) on the way back to the root, so the operation can be completed in $O(log n)$ time.

Delete
The preliminary steps for deleting a node are described in section Binary search tree. There, the effective deletion of the subject node or the replacement node decreases the height of the corresponding child tree either from 1 to 0 or from 2 to 1, if that node had a child.

Starting at this subtree, it is necessary to check each of the ancestors for consistency with the invariants of AVL trees. This is called "retracing".

Since with a single deletion the height of an AVL subtree cannot decrease by more than one, the temporary balance factor of a node will be in the range from −2 to +2. If the balance factor remains in the range from −1 to +1 it can be adjusted in accord with the AVL rules. If it becomes ±2 then the subtree is unbalanced and needs to be rotated. (Unlike insertion where a rotation always balances the tree, after delete, there may be BF(Z) ≠ 0 (see figures 2 and 3), so that after the appropriate single or double rotation the height of the rebalanced subtree decreases by one meaning that the tree has to be rebalanced again on the next higher level.) The various cases of rotations are described in section Rebalancing.

The height of the subtree rooted by N has decreased by 1. It is already in AVL shape.
 * Invariant of the retracing loop for a deletion

The retracing can stop if the balance factor becomes ±1 (it must have been 0) meaning that the height of that subtree remains unchanged.

If the balance factor becomes 0 (it must have been ±1) then the height of the subtree decreases by one and the retracing needs to continue.

If the balance factor temporarily becomes ±2, this has to be repaired by an appropriate rotation. It depends on the balance factor of the sibling Z (the higher child tree in figure 2) whether the height of the subtree decreases by one –and the retracing needs to continue– or does not change (if Z has the balance factor 0) and the whole tree is in AVL-shape.

The time required is $O(log n)$ for lookup, plus a maximum of $O(log n)$ retracing levels ($O(1)$ on average) on the way back to the root, so the operation can be completed in $O(log n)$ time.

Set operations and bulk operations
In addition to the single-element insert, delete and lookup operations, several set operations have been defined on AVL trees: union, intersection and set difference. Then fast bulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, Split and Join. With the new operations, the implementation of AVL trees can be more efficient and highly-parallelizable.

The function Join on two AVL trees $t_{1}$ and $t_{2}$ and a key $k$ will return a tree containing all elements in $t_{1}$, $t_{2}$ as well as $k$. It requires $k$ to be greater than all keys in $t_{1}$ and smaller than all keys in $t_{2}$. If the two trees differ by height at most one, Join simply create a new node with left subtree $t_{1}$, root $k$ and right subtree $t_{2}$. Otherwise, suppose that $t_{1}$ is higher than $t_{2}$ for more than one (the other case is symmetric). Join follows the right spine of $t_{1}$ until a node $c$ which is balanced with $t_{2}$. At this point a new node with left child $c$, root $k$ and right child $t_{2}$ is created to replace c. The new node satisfies the AVL invariant, and its height is one greater than $c$. The increase in height can increase the height of its ancestors, possibly invalidating the AVL invariant of those nodes. This can be fixed either with a double rotation if invalid at the parent or a single left rotation if invalid higher in the tree, in both cases restoring the height for any further ancestor nodes. Join will therefore require at most two rotations. The cost of this function is the difference of the heights between the two input trees.

function JoinRightAVL(TL, k, TR) (l, k', c) = expose(TL) if (Height(c) <= Height(TR)+1) T' = Node(c, k, TR) if (Height(T') <= Height(l)+1) then return Node(l, k', T') else return rotateLeft(Node(l, k', rotateRight(T'))) else T' = JoinRightAVL(c, k, TR) T '' = Node(l, k', T') if (Height(T') <= Height(l)+1) return T '' else return rotateLeft(T '' )

function JoinLeftAVL(TL, k, TR) /* symmetric to JoinRightAVL */

function Join(TL, k, TR) if (Height(TL)>Height(TR)+1) return JoinRightAVL(TL, k, TR) if (Height(TR)>Height(TL)+1) return JoinLeftAVL(TL, k, TR) return Node(TL, k, TR) Here Height(v) is the height of a subtree (node) $v$. (l,k,r) = expose(v) extracts $v$'s left child $l$, the key $k$ of $v$'s root, and the right child $r$. Node(l,k,r) means to create a node of left child $l$, key $k$, and right child $r$.

To split an AVL tree into two smaller trees, those smaller than key $k$, and those greater than key $k$, first draw a path from the root by inserting $k$ into the AVL. After this insertion, all values less than $k$ will be found on the left of the path, and all values greater than $k$ will be found on the right. By applying Join, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is asymmetric. The cost of Split is $O(log n)$, order of the height of the tree.

function Split(T, k)    if (T = nil) return (nil, false, nil) (L,m,R) = expose(T) if (k = m) return (L, true, R)    if (km) (L',b,R') = Split(R, k)       return (Join(L, m, L'), b, R'))

The union of two AVL trees $t_{1}$ and $t_{2}$ representing sets $A$ and $B$, is an AVL $t$ that represents $A ∪ B$.

function Union(t1, t2): if t1 = nil: return t2    if t2 = nil: return t1    (t<, b, t>) = Split(t2, t1.root) return Join(Union(left(t1), t<), t1.root, Union(right(t1), t>))

Here, Split is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is non-destructive, but an in-place destructive version exists as well.)

The algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the AVL tree. Since Split calls Join but does not deal with the balancing criteria of AVL trees directly, such an implementation is usually called the "join-based" implementation.

The complexity of each of union, intersection and difference is $$\text{O}\left(m \log \left({n\over m}+1\right)\right)$$ for AVL trees of sizes $$m$$ and $$n \; (\ge m)$$. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed in parallel with a parallel depth $$\text{O}(\log m\log n)$$. When $$m=1$$, the join-based implementation has the same computational DAG as single-element insertion and deletion.

Rebalancing
If during a modifying operation the height difference between two child subtrees changes, this may, as long as it is < 2, be reflected by an adaption of the balance information at the parent. During insert and delete operations a (temporary) height difference of 2 may arise, which means that the parent subtree has to be "rebalanced". The given repair tools are the so-called tree rotations, because they move the keys only "vertically", so that the ("horizontal") in-order sequence of the keys is fully preserved (which is essential for a binary-search tree).

Let X be the node that has a (temporary) balance factor of −2 or +2. Its left or right subtree was modified. Let Z be the child with the higher subtree (see figures 2 and 3). Note that both children are in AVL shape by induction hypothesis.

In case of insertion this insertion has happened to one of Z's children in a way that Z's height has increased. In case of deletion this deletion has happened to the sibling t1 of Z in a way so that t1's height being already lower has decreased. (This is the only case where Z's balance factor may also be 0.)

There are four possible variants of the violation:

And the rebalancing is performed differently:

Thereby, the situations are denoted as C B, where C (= child direction) and B (= balance) come from the set { Left, Right } with Right := −Left. The balance violation of case C == B is repaired by a simple rotation (−C), whereas the case C != B is repaired by a double rotation CB.

The cost of a rotation, either simple or double, is constant.

Simple rotation
Figure 2 shows a Right Right situation. In its upper half, node X has two child trees with a balance factor of +2. Moreover, the inner child t23 of Z (i.e., left child when Z is right child, or right child when Z is left child) is not higher than its sibling t4. This can happen by a height increase of subtree t4 or by a height decrease of subtree t1. In the latter case, also the pale situation where t23 has the same height as t4 may occur.

The result of the left rotation is shown in the lower half of the figure. Three links (thick edges in figure 2) and two balance factors are to be updated.

As the figure shows, before an insertion, the leaf layer was at level h+1, temporarily at level h+2 and after the rotation again at level h+1. In case of a deletion, the leaf layer was at level h+2, where it is again, when t23 and t4 were of same height. Otherwise the leaf layer reaches level h+1, so that the height of the rotated tree decreases.

 * Code snippet of a simple left rotation

Double rotation
Figure 3 shows a Right Left situation. In its upper third, node X has two child trees with a balance factor of +2. But unlike figure 2, the inner child Y of Z is higher than its sibling t4. This can happen by the insertion of Y itself or a height increase of one of its subtrees t2 or t3 (with the consequence that they are of different height) or by a height decrease of subtree t1. In the latter case, it may also occur that t2 and t3 are of the same height.

The result of the first, the right, rotation is shown in the middle third of the figure. (With respect to the balance factors, this rotation is not of the same kind as the other AVL single rotations, because the height difference between Y and t4 is only 1.) The result of the final left rotation is shown in the lower third of the figure. Five links (thick edges in figure 3) and three balance factors are to be updated.

As the figure shows, before an insertion, the leaf layer was at level h+1, temporarily at level h+2 and after the double rotation again at level h+1. In case of a deletion, the leaf layer was at level h+2 and after the double rotation it is at level h+1, so that the height of the rotated tree decreases.

 * Code snippet of a right-left double rotation

Comparison to other structures
Both AVL trees and red–black (RB) trees are self-balancing binary search trees and they are related mathematically. Indeed, every AVL tree can be colored red–black, but there are RB trees which are not AVL balanced. For maintaining the AVL (or RB) tree's invariants, rotations play an important role. In the worst case, even without rotations, AVL or RB insertions or deletions require $Height(LeftSubtree($ inspections and/or updates to AVL balance factors (or RB colors). RB insertions and deletions and AVL insertions require from zero to three tail-recursive rotations and run in amortized $))+2$ time, thus equally constant on average. AVL deletions requiring $Height(LeftSubtree($ rotations in the worst case are also $))+2$ on average. RB trees require storing one bit of information (the color) in each node, while AVL trees mostly use two bits for the balance factor, although, when stored at the children, one bit with meaning «lower than sibling» suffices. The bigger difference between the two data structures is their height limit.

For a tree of size $O(log n)$ \begin{array}{ll} h & \leqq \; c \log_2 (n + d) + b \\ & < \; c \log_2 (n + 2) + b \end{array} $$
 * an AVL tree's height is at most
 * where $$\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618$$ the golden ratio, $$c := \tfrac 1{\log_2 \varphi} \approx 1.440,$$   $$b := \tfrac{c}2 \log_2 5 - 2 \approx \; -0.328,$$ and  $$d:=1+\tfrac{1}{\varphi^4\sqrt{5}} \approx 1.065$$.

\begin{array}{ll} h & \leqq \; 2\log_2(n+1) \end{array} $$.
 * a RB tree's height is at most

AVL trees are more rigidly balanced than RB trees with an asymptotic relation AVL/RB ≈0.720 of the maximal heights. For insertions and deletions, Ben Pfaff shows in 79 measurements a relation of AVL/RB between 0.677 and 1.077 with median ≈0.947 and geometric mean ≈0.910.

title: AVL tree


text:
Aliphatic compound

In organic chemistry, hydrocarbons (compounds composed solely of carbon and hydrogen) are divided into two classes: aromatic compounds and aliphatic compounds (G. aleiphar, fat, oil). Aliphatic compounds can be saturated (in which all the C-C bonds are single requiring the structure to be completed, or 'saturated', by hydrogen) like hexane, or unsaturated, like hexene and hexyne. Open-chain compounds, whether straight or branched, and which contain no rings of any type, are always aliphatic. Cyclic compounds can be aliphatic if they are not aromatic.

Structure
Aliphatic compounds can be saturated, joined by single bonds (alkanes), or unsaturated, with double bonds (alkenes) or triple bonds (alkynes). If other elements (heteroatoms) are bound to the carbon chain, the most common being oxygen, nitrogen, sulfur, and chlorine, it is no longer a hydrocarbon, and therefore no longer an aliphatic compound. However, such compounds may still be referred to as aliphatic if the hydrocarbon portion of the molecule is aliphatic, e.g. aliphatic amines, to differentiate them from aromatic amines.

The least complex aliphatic compound is methane (CH4).

Properties
Most aliphatic compounds are flammable, allowing the use of hydrocarbons as fuel, such as methane in natural gas for stoves or heating; butane in torches and lighters; various aliphatic (as well as aromatic) hydrocarbons in liquid transportation fuels like petrol/gasoline, diesel, and jet fuel; and other uses such as ethyne (acetylene) in welding.

Examples of aliphatic compounds
The most important aliphatic compounds are:

 * n-, iso- and cyclo-alkanes (saturated hydrocarbons)
 * n-, iso- and cyclo-alkenes and -alkynes (unsaturated hydrocarbons).

Important examples of low-molecular aliphatic compounds can be found in the list below (sorted by the number of carbon-atoms):

title: Aliphatic compound